学习笔记Java集合10-Set-LinkedHashSet源码分析

介绍

上一节我们说 HashSet 中的元素是无序的，那么有没有什么办法保证 Set 中的元素是有序的呢？

答案是当然可以。LinkedHashSet 就有这个功能，它是怎么实现有序的呢？

源码分析

LinkedHashSet 继承自 HashSet，让我们直接上源码来看看它们有什么不同。

package java.util;

// LinkedHashSet 继承自 HashSet
public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = -2851667679971038690L;

    // 传入容量和装载因子
    public LinkedHashSet(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor, true);
    }

    // 只传入容量, 装载因子默认为 0.75
    public LinkedHashSet(int initialCapacity) {super(initialCapacity, .75f, true);
    }

    // 使用默认容量 16, 默认装载因子 0.75
    public LinkedHashSet() {super(16, .75f, true);
    }

    // 将集合 c 中的所有元素添加到 LinkedHashSet 中
    // 好奇怪, 这里计算容量的方式又变了
    // HashSet 中使用的是 Math.max((int) (c.size()/.75f) + 1, 16)
    // 这一点有点不得其解, 是作者偷懒？public LinkedHashSet(Collection<? extends E> c) {super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }

    // 可分割的迭代器, 主要用于多线程并行迭代处理时使用
    @Override
    public Spliterator<E> spliterator() {return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
    }
}

完了，这是全部源码了。

可以看到，LinkedHashSet 中一共提供了 5 个方法，其中 4 个是构造方法，还有一个是迭代器。

4 个构造方法都是调用父类的 super(initialCapacity, loadFactor, true); 这个方法。

这个方法就是我们上一节说过,HashSet 的一个不是 public 的构造方法。

   // HashSet 的构造方法
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

如上所示，这个构造方法里面使用了 LinkedHashMap 来初始化 HashSet 中的 map。

现在这个逻辑应该很清晰了，LinkedHashSet 继承自 HashSet，它的添加、删除、查询等方法都是直接用的 HashSet 的，唯一的不同就是它使用 LinkedHashMap 存储元素。

总结

（1）LinkedHashSet 的底层使用 LinkedHashMap 存储元素。

（2）LinkedHashSet 是有序的，它是按照插入的顺序排序的。

思考

通过上面的学习，我们知道 LinkedHashSet 底层使用 LinkedHashMap 存储元素，而 LinkedHashMap 是支持按元素访问顺序遍历元素的，也就是可以用来实现 LRU 的。

那么，LinkedHashSet 支持按元素访问顺序排序吗？

让我们一起来分析下。

首先，LinkedHashSet 所有的构造方法都是调用 HashSet 的同一个构造方法，如下：

  // HashSet 的构造方法
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
    
## 然后，通过调用 LinkedHashMap 的构造方法初始化 map，如下所示：public LinkedHashMap(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor);
        accessOrder = false;
    }

可以看到，这里把 accessOrder 写死为 false 了。

所以，LinkedHashSet 是不支持按访问顺序对元素排序的 ，只能按插入顺序排序。