HashSet与LinkedHashSet

Question

他们之间有什么区别？我知道

LinkedHashSet是HashSet的有序版本,它维护所有元素的双向链接列表.在关心迭代顺序时,请使用此类而不是HashSet.当您遍历HashSet时,顺序是不可预测的,而LinkedHashSet允许您按照插入顺序迭代元素.

但是在LinkedHashSet的源代码中,只有HashSet的调用构造函数.那么双链接列表和插入顺序在哪里？

Answer 1

答案在于构造者LinkedHashSet用于构造基类的用法:

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);      // <-- boolean dummy argument
}

...

public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);            // <-- boolean dummy argument
}

...

public LinkedHashSet() {
    super(16, .75f, true);                         // <-- boolean dummy argument
}

...

public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);   // <-- boolean dummy argument
    addAll(c);
}

并且(一个例子)HashSet描述了一个带有布尔参数的构造函数,如下所示:

/**
 * Constructs a new, empty linked hash set.  (This package private
 * constructor is only used by LinkedHashSet.) The backing
 * HashMap instance is a LinkedHashMap with the specified initial
 * capacity and the specified load factor.
 *
 * @param      initialCapacity   the initial capacity of the hash map
 * @param      loadFactor        the load factor of the hash map
 * @param      dummy             ignored (distinguishes this
 *             constructor from other int, float constructor.)
 * @throws     IllegalArgumentException if the initial capacity is less
 *             than zero, or if the load factor is nonpositive
 */
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}

Answer 2

LinkedHashSet的构造函数调用以下基类构造函数:

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
  map = new LinkedHashMap<E, Object>(initialCapacity, loadFactor);
}

如您所见,内部地图是一个LinkedHashMap.如果您查看内部LinkedHashMap,您将发现以下字段:

private transient Entry<K, V> header;

这是有问题的链表.

Answer 3

HashSet是无序和未排序的Set.LinkedHashSet是HashSet的有序版本.HashSet和LinkedHashSet之间的唯一区别是LinkedHashSet维护插入顺序.当我们遍历HashSet时,顺序是不可预测的,而在LinkedHashSet的情况下它是可预测的.LinkedHashSet维护插入顺序的原因是底层数据结构是双向链表.

Answer 4

你应该看看源HashSet调用构造函数...这是一个特殊的构造,使背Map一个LinkedHashMap,而不是仅仅一个HashMap.

Answer 5

我建议你LinkedHashSet大部分时间都使用,因为它总体上有更好的表现):

1. 可预测的 迭代顺序LinkedHashSet(Oracle)
2. LinkedHashSet的插入比HashSet更昂贵;
3. 一般来说性能稍好一些HashMap,因为大多数时候我们使用Set结构进行迭代.

性能测试:

------------- TreeSet -------------
 size       add  contains   iterate
   10       746       173        89
  100       501       264        68
 1000       714       410        69
10000      1975       552        69
------------- HashSet -------------
 size       add  contains   iterate
   10       308        91        94
  100       178        75        73
 1000       216       110        72
10000       711       215       100
---------- LinkedHashSet ----------
 size       add  contains   iterate
   10       350        65        83
  100       270        74        55
 1000       303       111        54
10000      1615       256        58

您可以在此处查看源测试页面:最终性能测试示例