java LinkedHashSet 源码分析（深度讲解）
目录
一、前言
大家好，本篇博文是对集合篇章——单列集合Set的内容补充。Set集合常见的实现类有两个——HashSet和TreeSet。上一篇博文中我们已经分析了HashSet的源码，知道了HashSet的底层其实就是HashMap。今天我们要解读的是HashSet的一个子类——LinkedHashSet。（）
注意 : ①解读源码需要扎实的基础，比较适合希望深究的同学； ②不要眼高手低，看会了不代表你会了，自己能全程Debug下来才算有收获； ③点击文章的侧边栏目录或者前面的目录可以进行跳转。良工不示人以朴，up所有文章都会适时改进。大家有问题都可以在评论区讨论交流，或者私信up。 感谢阅读！
二、LinkedHashSet简介
1.LinkedHashSet是HashSet的子类，而由于HashSet实现了Set接口，因此LinkedHashSet也间接实现了Set接口。LinkedHashSet类属于java.base模块，java.util包下，如下图所示 :
我们再来看一下LinkedHashSet的类图，如下 :
2.LinkedHashSet底层是一个LinkedHashMap，是"数组 + 双向链表"的结构。
3.LinkedHashSet也具有Set集合"不可重复"的特点。但由于LinkedHashSet根据元素的哈希值来决定元素的存储位置，同时使用双向链表来维护元素的次序，所以这就使得元素看起来是以插入顺序保存的。
三、LinkedHashSet的底层实现
1.LinkedHashSet在底层会用到一个HashMap$Node[]类型的table表（Node类是HashMap中维护的一个静态内部类），该table表即用来存储元素，这一点和HashSet是一样的(实际上在通过add方法添加元素时，它们底层都是走的HashMap的put方法)。table属性如下图所示 :
由于table属性是被HashMap类维护的，所以，无论是HashSet还是LinkedHashSet，都需要先成功访问到HashMap，以HashSet为例，HashSet中维护了一个HashMap<E,Object>类型的map属性，而HashSet的构造器中对该map属性进行了初始化，如此一来，HashSet借助该map对象即可访问到HashMap中维护的table属性。如下图所示 :
LinkedHashSet和HashSet的结构是类似的，都是通过HashSet中维护的private transient HashMap<E, Object> map 来间接调用HashMap中的内容，只不过HashSet的构造器中是直接将map置为了一个HashMap类型的对象，而在LinkedHashSet的构造器中，却是使用多态的方式（LinkedHashSet底层本质是LinkedHashMap，而LinkedHashMap又继承自HashMap，如此一来，亦可借助map对象访问到HashMap中维护的table数组，因为table数组是非私有的），如下图所示 :
2.LinkedHashSet通过head和tail维护了一个双向链表（本质上是用的LinkedHashMap中的这两个属性），注意，此处的Entry是LinkedHashMap的一个静态内部类，LinkedHashMap中的head和tail如下图所示 :
此外，LinkedHashMap$Entry类中又维护了before和after两个属性，用于形成双向链表。当然我们在HashSet的源码分析中已经见过它了。如下图所示 :
3.如上图所示，每个Entry结点中维护了before，after两个属性，其中通过before指向前一个结点，通过after指向后一个结点，从而实现双向链表。注意，LinkedHashMap$Entry类继承自HashMap$Node类，在Entry类的构造器中，通过super(hash,key,value,next)调用Node类的构造器，由此可知，在LinkedHashSet中，最终加入到集合中的元素存储在了Node类维护的key属性中（类比HashSet只用了key-value键值对的key来保存值），这一点同HashSet类是一致的，因此，在后文中的源码分析中，我们应该会再次遇到PRESENT占位符，即HashSet中维护的private static final Object PRESENT = new Object();属性。
4.LinkedHashSet在添加元素时的底层规则和HashSet高度一致（底层走了相同的方法，见下文“源码分析”），即先求该元素的hash值，根据特定算法求得该元素在table中应该存放的位置。如果该位置已经有相同元素，放弃添加；反之则将该元素加入到双向链表。
5.LinkedHashSet的底层其实就是LinkedHashMap，关于这一点，要类比HashSet的底层是HashMap。
6.LinkedHashSet的底层机制图示 :
四、LinkedHashSet的源码解读（断点调试）
0.准备工作 :
up以LinkedHashSet_Demo类为演示类，代码如下 : （main函数第一行设置断点）
package csdn.knowledge.api_tools.gather.set;
import java.util.LinkedHashSet;
import java.util.Objects;
/**
* @author : Cyan_RA9
* @version : 21.0
*/
public class LinkedHashSet_Demo {
public static void main(String[] args) {
LinkedHashSet linkedHashSet = new LinkedHashSet();
linkedHashSet.add(141);
linkedHashSet.add(141);
linkedHashSet.add("CSDN");
linkedHashSet.add(11);
linkedHashSet.add("Cyan");
linkedHashSet.add(new Apple("红富士"));
linkedHashSet.add(new Apple("红富士"));
}
}
class Apple {
private String name;
public Apple(String name) {
this.name = name;
}
@Override
public int hashCode() {
return 100;
}
}1.向集合中添加第一个元素 :
①跳入无参构造。
首先我们跳入LinkedHashSet的无参构造，如下图所示 :
底层调用了其父类HashSet 的一个带参构造，我们继续追进去看看，如下 :
可以看到，最终调用的还是LinkedHashMap的构造器。（LinkedHashMap是HashMap的子类，此处构成“多态”）
好的，接下来我们跳出构造器，回到演示类中，如下 :
可以看到，此时的map对象是LinkedHashMap类型。
②跳入resize方法。
准备向集合中添加第一个元素，注意，LinkedHashMap和HashMap在底层添加元素时，几乎完全一样，前面几步像是跳入add方法 ——> 跳入put方法 ——> 跳入putVal方法二者是完全一致的。up这里就不再赘述了，因为在之前的HashSet源码分析中我们已经非常详细地说过了，这里再长篇大论地给大家讲就真的有水博客的嫌疑了，虽然up蛮喜欢水博客的（bushi）。因此，为了大家的阅读体验，强烈建议大家在看本篇"LinkedHashSet"的源码分析之前，先去看看up写得"HashSet"源码分析。
我们直接从二者不一样的地方开始说起。在putVal方法中，第一个if语句满足判断，如下 :
可以看到，我们要进入resize方法对tab数组进行扩容，resize方法要返回一个Node类型的数组给tab数组。我们跳入resize方法，resize方法源码如下：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}好的，前面几步都还和HashSet添加第一个元素时一样，如下 :
定义Node数组类型的引用oldTabl，并将table数组赋值给oldTab引用，oldTab也为null；又用一个三目运算符最终将0赋值给了oldCap变量。
下一步开始就要不一样了，如下 :
注意看，不知道大家还记不记得，在HashSet的源码分析中，这里的threshold应该等于0呀。我们再次查看一下threshold的源码，如下 :
欸嘿，奇了怪了，int类型默认值应该为0呀，怎么这里也显示它为16了？
显然，在前面的某一个步骤中，threshold已经被作了修改。这时候可能会有p小将（personable小将，指风度翩翩的人）出来bb
③threshold发生改变的真正原因。
大家仔细想一想，到目前为止，有没有发觉到什么蹊跷的地方？
回顾目前执行过的步骤，呃，也就一个无参构造，后面跳入add方法几步都和HashSet一样我们也没再演示。没错！就是这个无参构造。请大家翻回去看看，我们一开始调用的明明是LinkedHashSet的无参构造，最后真正起到执行效果的却是LinkedHashMap的带参构造。还没发现么？带参构造！这肯定里面有东西呀。
所以，下一步我们直接重新Debug，并回到我们一开始追到HashSet构造器的界面，如下图所示:
注意看实参，初始容量和加载因子，都是老面孔了，这里不再赘述，但要记住它们此时的值——16和0.75。好的，接下来我们就继续追入LinkedHashMap的这个带参构造，看看里面究竟是什么牛马玩意儿，如下图所示 :
哎哟我趣，又是熟悉的复合包皮结构。没想到啊，LinkedHashMap的带参构造，最终却又调用了其父类HashMap的带参构造，不得不说，java语言里面的"啃老"现象，属实有丶严重了。
好的，看个玩笑。我们回到正题，继续追入HashMap的带参构造，如下 :
哎哟，这第一眼看上去还挺有货。当然，还是那句话——不要因为走得太远而忘了自己为什么出发。我们半路折回去，不就是想找到为threshold赋值的语句么。
仔细看，最后一句正是我们要找的为threshold赋值的语句。但是该赋值语句中又调用了tableSizeFor方法，见名知意，这个方法和table数组的容量有关。我们也没办法，毕竟已经上了贼船，还是得一路坐到西。
跳入tableSizeFor方法，如下 :
首先，定义了n变量，并通过一个算法为其初始化，这里涉及到了二进制无符号右移的内容，我们不再深究。看右面IDEA提示，我们只需要知道最后n = 15就可以了。
其次，return语句的返回值是一个双重复合的三目运算符。什么意思呢？就是说如果外层三目运算符的判断条件成立，就返回1，否则返回内层三目运算符的结果。而外层判断条件n < 0显然不成立，所以要返回内层三目运算符的结果；而内层三目运算符的判断条件n是否大于等于那一大堆数（将鼠标悬浮在上面可以显示），显然不成立。所以return语句最后返回的值就是 n + 1 = 16。
跳出tableSizeFor方法，如下 :
这下可以解释我们前面的问题了。threshold就是在HashMap的无参构造中被初始化为了16。（注意此处loadFactor属性也被初始化，初始化为了0.75）
④继续回到resize方法。
好的，搞清楚threshold变量变化的原因后，我们可以返回到刚刚的resize方法继续解读。如下 :
可以看到，将threshold（= 16）赋值给oldThr变量后，又定义了newCap（即newCapacity）和newThr（即newThreshold）两个变量。第一个if语句显然判断不成立，不进入它。但后面的else if语句的判断是成立的，如下 :
else if语句中，将newCap赋值为了16（顾名思义，LinkedHashSet的默认初始容量同HashSet一样，第一次扩容也是16）。
继续，接下来的一个if语句如下 :
由于threshold的改变，我们并没有进入if - else if - else中的else语句，而是进入了else if语句，所以newThr变量还是默认值0。这里其实就是将ft赋值给了newThr变量，计算方式仍然是数组容量 * 增长因子 = 16 * 0.75 = 12。
继续，如下图 :
后面几步就都一样了。将临界值12赋值给threshold属性，这才符合逻辑对不对？（关于临界值，up已经在HashSet源码分析中仔细讲过了，大家可以去找一下，这里不再赘述）。
然后，又是new一个长度为16的数组，并最终将table属性初始化。之后有个巨**大的if 语句，不过，幸好，判断为假，我们不用进去😂。
好的，最后就是返回这个新数组了，如下 :
⑤回到演示类方法。
接下来，我们先回到putVal方法，如下 :
仍然是根据当前元素（141）的hash值，通过特定的算法获得当前元素在table数组中应该存放的位置的索引值。然后判断，如果table数组该索引处为空，就直接放进去；不为空的话就去下面的else语句，去链表中一一进行判断。
当然，这些都是在HashSet源码分析中讲过的。以下几个步骤也都一样，我们也不再多说，毕竟老讲重复的东西也没啥意思对不对？
好滴，接下来我们逐层返回，一直到演示类中，如下GIF图所示 :
可以看到，table数组成功初始化为长度 = 16的数组，141元素也成功添加到了集合中。
但是注意看，此时table数组仍然是Node类型（LinkedHashMap的静态内部类），但是里面保存的元素却成了Entry类型（LinkedHashMap的内部类）。一个类型的数组里面存放了另一类型的元素，请问，你想到了什么？大声告诉我😎！没错，多态数组。显然，这里的Entry类型一定是继承或者实现了Node类型。
⑥多态数组的体现。
我们来看看Entry类的源码，如下 :
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}这下真相大白了，Entry类继承了Node类，因此Node类型数组中存放Entry类型元素达到了多态的效果。大家注意，此处的Node类型是由HashMap通过类名来引用的，显然，Node类型其实就是HashMap类中的一个静态内部类。（关于java中的四种内部类，up之前已出过博文讲解，大家可以移步《java进阶》专栏阅读。）
同时要注意，Entry内部类中定义了before和after属性，即我们在上文"LinkedHashSet的底层实现"中提到的——before指向双向链表的前一个结点，after指向双向链表的后一个结点，从而实现双向链表。
2.继续向集合添加元素 :
①向集合中添加重复元素。
当我们重复添加141元素时，肯定无法加入。底层和HashSet玩得是一套，up就不演示了。大家可以自己下去Debug一次，回顾一下就好。
当然，我们在Debug界面中也可以查看table数组的情况，如下 :
可以看到，此时集合中仍然只有一个元素。
②向集合中添加第二个元素。
继续向下执行，将"CSDN"元素加入集合中。如下图所示 :
可以看到，目前table数组中已经有俩元素了。注意，记住这俩元素目前的标识——141的标识是819，"CSDN"的标识是836。
注意，精彩的要来了，如下 :
我们点开添加的第一个元素，可以看到，此时第一个元素141的after属性指向了第二个元素"CSDN"，而第二个属性的before属性则指向了第一个元素141；并且141元素的before属性和"CSDN"元素的after属性均为null。此时，table数组中的两个元素已然形成了一个简单的双向链表。并且，我们还可以在map对象的界面看到LinkedHashMap中的head和tail分别指向了双向链表的第一个元素和最后一个元素。
此时，这个简单的双向链表就应该长下面这个样子 :
③向集合中添加第三个元素。
继续向下执行，将11元素加入到集合中，如下图所示 :
此时底层的"数组 + 链表"结构如下 :
④向集合中添加第四、五、六个元素。
继续向下执行，向集合中添加"Cyan"，new Apple("红富士")，和new Apple("红富士")这三个对象。注意，由于我们没有在Apple类重写equals方法，因此两个Apple对象会被判定为不同的元素，可以加入集合；但是由于我们在Apple类中重写了hashCode方法，这俩对象最终得到的哈希值一样，因此它们会挂载到同一链表下。Debug界面图示如下 :
我们可以通过点击每个元素的after属性来直接查看它的下一个属性，如下GIF图所示 :
此时底层的"数组 + 链表"结构如下 :
可能有点乱😂，不过看准每个结点的before和after，以及第一个结点和最后一个结点的null，还是可以很轻松找到顺序的。
这里还要再说一点——关于after和next的区别，其实很简单——
1°after是用于双向链表中专门指向下一个元素，没有下一个元素则为null。即不管某一个结点的下一个元素是在table数组中其他索引处的位置，还是挂载在该结点的后面，after都会指向它。
2°next则是和我们在HashSet中分析的一样，如果数组某一个索引处的元素形成了链表，next会指向链表中的下一个元素。
3°比如，此处的第一个Apple对象元素，它的after毫无疑问指向了第一个Apple对象元素；但是因为第二个Apple对象元素恰好挂载在了它的后面，即它们在table数组同一索引处的位置，所以第一个Apple对象元素的next属性也指向了第二个Apple对象。
4°也就是说，after是针对了整个双向链表，针对于所有元素，针对于全局；而next则是仅仅针对于同一索引位置处形成的单向链表，针对于table数组同一索引位置处的元素，针对于局部。
5° 从源码角度分析，next属性由HashMap$Node类维护，而after由LinkedHashMap$Entry类维护。
所以，我们可以通过Debug看到，在table数组的所有元素中，仅有第一个Apple对象元素的next属性有指向，且指向同它的after属性一样，指向了挂载在它后面的第二个Apple对象元素。如下图所示 :
五、完结撒❀
🆗，以上就是我们LinkedHashSet源码分析的全部内容了😆。其实如果你认真看完了up之前对于HashSet的源码分析。看这篇LinkedHashSet的源码分析会轻松许多，毕竟有其父必有其子么（bushi）。当然，对于两者不同的地方，比如说是底层结构的差异，构造器的差异up也都有讲到。阅读源码的能力需要慢慢培养，希望大家都能下去亲自动动手，Debug一下。感谢阅读！
System.out.println("END----------------------------------------------");
- 点赞
- 收藏
- 关注作者
评论（0）