7-LinkedHashSet底层结构和源码分析

7-LinkedHashSet底层结构和源码分析

介绍汇总：

• LinkedHashSet全面说明
  
• LinkedHashSet底层机制说明
  

1-LinkedHashSet全面说明

• LinkedHashSet 底层是一个 LinkedHashMap ，底层维护了一个数组 + 双向链表 。由于 LinkedHashMap 是继承 HashMap 的全部特性的，其双向链表是在原本的数据结点上加上了 before 和 after 指针，并且也不破坏原来 HashMap 中链表和红黑树的结构，来完成实现双向链表的。
  
• LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，同时利用链表维护元素的次序，这就保证元素看起来是以插入次序保存的。
  
• LinkedHashSet 不允许添加重复元素，这点与 HashSet 一致。
  

2-LinkedHashSet底层机制说明

• 在 LinkedHashSet 中维护了一个 hash 表和双向链表（ LinkedHashSet （LinkedHashMap） 有 head 和 tail ）
  
• 每一个数据结点在原本的基础上（通过继承 HashMap 的数据结点 Node ，拥有 Node 全部特性）有 before 和 after 属性，这样就可以形成双向链表（before 和 after 属性类型为 Entry ，这个类是继承 Node，这也是为啥 LinkedHashSet 中表的类型为 Node，却可以存放 Entry 类型数据结点）
  
• 在添加一个元素时，先求 hash 值，再求索引；确定该元素在 table 的位置，然后将添加的元素加入到双向链表（若已存在，不添加【原则和 HashSet 一样】）
  

1. // 添加示意代码
2. tail.next = newElement
3. newElement.pre = tail
4. tail = newElement

复制代码

<ol start="4">这样的话，遍历 LinkedHashSet 也能确保插入次序和遍历次序一致
LinkedHashSet 继承了 HashSet 的全部特性，并且基本上都是调用其父类的方法举行。而其内部是维护了一个 LinkedHashMap，并且 LinkedHashMap 也继承了 HashMap 的全部特性，并且扩容流程也是和父类一致大概就是直接调用父类的扩容流程，只是此中有一些关键类和方法举行了重写。例如，数据结点 Entry （继承 HashMap 的内部类 Node ）。还有创建新数据结点方法 newNode 方法举行了重写，创建 Entry 结点，并且增长了维护的双向链表的增长机制。还有一个就是 newTreeNode 方法，创建好后树结点，举行链表添加，并且该 TreeNode 结点是继承了 Entry 全部特性。
最主要就是 LinkedHashSet 与 HashSet 多维护了双向链表，可以按添加次序举行遍历。
当前仅是介绍了添加元素的底层。
实践练习

• 测试链表树化
  

[code]package set.linkedhashset;import java.util.LinkedHashSet;public class LinkedHashSetSource {    @SuppressWarnings({"all"})    public static void main(String[] args) {        // 测试链表树化        // 与 HashMap 中的树化流程基本一致，满足两个条件才可树化        // 只是多了双向链表        LinkedHashSet linkedHashSet = new LinkedHashSet();        for (int i = 1; i