时间戳

首页 > 解决方案 > 什么算法用于转换 ArrayList到 LinkedHashSet在 JRE

java - 什么算法用于转换 ArrayList到 LinkedHashSet在 JRE

问题描述

我想list从具有重复元素的 a 中获取一个独特的元素，list并且应该保持列表中出现的元素的顺序。

为此，我可以编写如下算法：

private ArrayList<T> getUnique(ArrayList<T> list)
{
    // maintain a hashmap of numbers and a uniqueList to be returned(ArrayList<T>)
    // Add element in result list and the hashmap if the element isn't already present in the hashmap, else just add in the hashmap

    HashMap<T, Boolean> map = new HashMap<>();
    ArrayList<T> uniqueList = new ArrayList<>();

    for (T t: list)
    {
        if (map.get(t) == null)
        {
            // t wasn't present so, adding them in map as well as in the list
            map.put(t, true);
            uniqueList.add(t);
        }
    }
    return uniqueList;
}

该算法需要额外的空间（对于 HashMap）O(n)。O(n)

或者简单地说，我可以使用以下语法：

Set<T> set = new LinkedHashSet<>(list);

Java中的上述语法用于从元素的出现顺序与的相同的元素中获取set唯一元素。然后将此集合转换为列表。( )listlistArrayList<T> uniqueList = new ArrayList<>(set);

我假设这里的时间复杂度也是O(n). 我想知道 Java 使用什么算法。

我看到这个类被命名为 LinkedHashSet，所以我认为他们可能使用了一些LinkedList概念来实现这一点，所以我查看了源代码，发现了这些东西：

  1. 在LinkedHashSet.java中，构造函数如下所示：

143: public LinkedHashSet(Collection<? extends T> c) 144: { 145: super(c); 146: } 这是来源。

  1. 所以，我查看了父类构造函数，即HashSet，我发现：

public HashSet(Collection<? extends E> c) { map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); addAll(c); }

  1. 接下来，我搜索addAll方法，我在AbstractCollection类（这是HashSet类的祖父母）中找到它，函数的定义是：

public boolean addAll(Collection<? extends E> c) { boolean modified = false; for (E e : c) if (add(e)) modified = true; return modified; }

这是调用add，就像：

public boolean add(E e) { throw new UnsupportedOperationException(); } 在这里。

我无法理解这一点。他们使用什么算法来完成这项任务？

标签： javaalgorithmhashmapsetlinkedhashset

解决方案

为了回答您的困惑，该add方法被覆盖HashSet如下：

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

请注意，LinkedHashSetextendsHashSet延伸AbstractSet延伸AbstractCollection。

总之，使用的算法是：

    for (E e : c)
        add(e);

这是O(N)for a因为forLinkedHashSet的平均复杂度是。addLinkedHashSetO(1)

推荐阅读