LinkedHashSet 源码

问题

• LinkedHashSet 底层存储？
• LinkedHashSet 和 HashSet 的区别？
• LinkedHashSet 有序吗？
• LinkedHashSet 支持按照访问顺序对元素排序吗？

概括

LinkedHashSet 是 Set 接口的实现类，底层数据结构基于链表和哈希表，哈希表保证元素唯一，链表保证插入顺序。

继承结构

• 实现 Set 接口，有 Set 所有特性
• 继承 HashSet ，拥有 HashSet 的特性

源码实现

构造方法

View Code

/**
 * Constructs a new, empty linked hash set with the specified initial
 * capacity and load factor.
 *
 * @param      initialCapacity the initial capacity of the linked hash set
 * @param      loadFactor      the load factor of the linked hash set
 * @throws     IllegalArgumentException  if the initial capacity is less
 *               than zero, or if the load factor is nonpositive
 */
public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

/**
 * Constructs a new, empty linked hash set with the specified initial
 * capacity and the default load factor (0.75).
 *
 * @param   initialCapacity   the initial capacity of the LinkedHashSet
 * @throws  IllegalArgumentException if the initial capacity is less
 *              than zero
 */
public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}

/**
 * Constructs a new, empty linked hash set with the default initial
 * capacity (16) and load factor (0.75).
 */
public LinkedHashSet() {
    super(16, .75f, true);
}

/**
 * Constructs a new linked hash set with the same elements as the
 * specified collection.  The linked hash set is created with an initial
 * capacity sufficient to hold the elements in the specified collection
 * and the default load factor (0.75).
 *
 * @param c  the collection whose elements are to be placed into
 *           this set
 * @throws NullPointerException if the specified collection is null
 */
public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);
    addAll(c);
}

• 所有构造方法都调用了同一个父类的构造方法；
• 如果传入初始容量，则根据初始容量计算合适的容量；否则初始容量为 16；
• 如果传入加载因子，使用传入的加载因子；否则默认 0.75；

上述的构造方法，都调用了同一个父类构造方法。

View Code

/**
 * 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<>(initialCapacity, loadFactor);
}

• LinkedHashSet 继承自 HashSet，对元素的操作都是使用 HashSet 方法实现；
• LinkedHaseSet 使用 LinkedHashMap 存储元素；

View Code

/**
 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
 * with the specified initial capacity and load factor.
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

• LinkedHashSet 的构造方法，最终调用了 LinkedHashMap 中的构造方法；
• accessOrder 默认为 false，指定按照插入顺序排序；

总结

• LinedHashSet 使用 LinkedHashMap 存储元素；
• LinkedHashSet 是有序的，按照插入顺序排序；
• LinkedHashSet 不支持按照访问顺序排序；