死磕-java集合之LinkedHashSet源码分析

jiezi

5 年前

（1）LinkedHashSet 的底层使用什么存储元素？

（2）LinkedHashSet 与 HashSet 有什么不同？

（3）LinkedHashSet 是有序的吗？

（4）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); 这个方法。

这个方法长什么样呢？

还记得我们上一节说过一个不是 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 的，还记得吗？传送门【死磕 java 集合之 LinkedHashMap 源码分析】

那么，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 是不支持按访问顺序对元素排序的，只能按插入顺序排序。

欢迎关注我的公众号“彤哥读源码”，查看更多源码系列文章, 与彤哥一起畅游源码的海洋。

死磕-java集合之LinkedHashSet源码分析

问题

简介

源码分析

总结

彩蛋