java - 在 JRE 中使用什么算法将 ArrayList 转换为 LinkedHashSet

Question

我想得到一个 list来自 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;
}

这个算法需要 O(n)时间 O(n)额外空间(用于 HashMap)。

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

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

Java 中的上述语法用于获取 set来自 list 的独特元素元素出现顺序与list相同.然后将此集合转换为列表。 ( ArrayList<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: }
here是来源。

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类的祖 parent )，函数定义为:


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();
}
here .

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

Answer 1

对于寻找整个故事的人

基于LinkedHashSet的源代码, HashSet , LinkedHashMap .当构造一个 LinkedHashSet 扩展 HashSet 与其他集合(LinkedHashSet.java line 143)时，

public LinkedHashSet(Collection<? extends T> c)  
{  
  super(c);  
}

它将调用(HashSet.java 第 136 行):

public HashSet(Collection<? extends T> c)
{
  this(Math.max(2 * c.size(), HashMap.DEFAULT_CAPACITY));
  addAll(c);
}

然后调用(HashSet.java 第 122 行):

public HashSet(int initialCapacity, float loadFactor)
{
  map = init(initialCapacity, loadFactor);
}

由于 init 方法在 LinkedHashSet 中被重写了

HashMap<T, String> init(int capacity, float load)
{
 return new LinkedHashMap<T, String>(capacity, load);
}

支持 map 是一个 LinkedHashMap。

根据 LinkedHashMap 的 java 文档

This class provides all of the optional Map operations, and permits null elements. Like HashMap, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashMap, due to the added expense of maintaining the linked list, with one exception: Iteration over the collection-views of a LinkedHashMap requires time proportional to the size of the map, regardless of its capacity. Iteration over a HashMap is likely to be more expensive, requiring time proportional to its capacity.

而HashSet的add方法是

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

因此，构建的平均时间复杂度为 O(n)。算法方面，我想你可以去看看LinkedHashMap的代码了解一下。进一步阅读 How is the internal implementation of LinkedHashMap different from HashMap implementation? , HashSet vs LinkedHashSet