HashSet集合底层源码解析

创始人

2025-05-31 07:40:32

Java源码系列：下方连接
http://t.csdn.cn/Nwzed

文章目录

前言
一、set接口
二、HashSet
- 模拟数组+链表实现HashSet底层结构
- 进入HashSet底层源码，非战斗人员做好撤离准备
- HashSet第一次添加元素
- HashSet第二次添加元素以及添加重复元素
- - 重复元素判断的全面详解
总结

前言

提示：发文三个工作日后总结：

提示：以下是本篇文章正文内容，下面案例可供参考

一、set接口

set接口的实现子类，可以使用 iterator迭代器和增强for循环进行遍历，但是不能使用索引的方式获取也就是说不能使用普通的for循环来进行遍历了，其实增强for循环的底层还是一个 iterator迭代器。
示例：pandas 是基于NumPy 的一种工具，该工具是为了解决数据分析任务而创建的。
在这里插入图片描述

二、HashSet

在这里插入图片描述

在这里插入图片描述
上图，lucy是字符串常量，是同一个对象只能加入一个，new Dog("tom")两个都能放入hashSet，但是 new String("hsp")就是两个字符串了，不再是在常量池中而是在堆内存区，但是为什么只能放入一个? 所以这个地方就出现了一个悖论，hashSet不能加入相同的对象，而 new String( )明明是两个对象，因该都加入进去的，HashSet却把它们定义成了同一个对象，这是因为String类重写了hashCode和equals方法，在底层两个“hsp”的hashCode获取的hash值肯定是一样的，根据相同的hash值它们就落到了同一个数组下标，这时会先比较它们的 hash值是否相同，这时肯定是相同的然后接了一个 && 逻辑与，（比较它们的内存地址是否相同(new了两个肯定不同)，再通过equals比较两个对象的内容是否相同这里肯定是相同的），只要内存地址和equals的条件一个为 true配合逻辑 &&就认为是相同的元素不去添加元素，只要后面两个条件都不满足才会去添加节点，上面两个 hsp 通过equals肯定是true，然后逻辑与&&两边都为 true，就会认为是相同的元素，看完源码再来看这一段话你肯定深有体会。
在这里插入图片描述

模拟数组+链表实现HashSet底层结构

在这里插入图片描述

数组加链表模拟HashSet底层结构

package tanchishell.list;/*** 数组加链表模拟HashSet底层结构* hashSet其实就是一个HashMap*/
public class HashSetStructure {public static void main(String[] args) {//创建一个数组 tableNode[] table = new Node[16];//先往数组[2]上添加元素Node jack = new Node("jack", null);table[2] = jack;//往数组下标挂载节点Node lucy = new Node("lucy", null);jack.next = lucy;Node join = new Node("join", null);lucy.next = join;//先往数组[3]上添加元素Node nihao = new Node("nihao", null);table[3] = nihao;System.out.println();}
}class Node{private String node; //节点的名称public Node next; //指向下一个节点public Node(String node, Node next) {this.node = node;this.next = next;}
}

进入HashSet底层源码，非战斗人员做好撤离准备

在这里插入图片描述

HashSet第一次添加元素

在这里插入图片描述

不多废话直接，debug开始，调用 HashSet的无参构造会 new HashMap，所以HashSet的底层还是HashMap，直接步出了可以。

在这里插入图片描述

调用add方法，e是泛型，也就是我们传过来的 java，只不过现在我们传的字符串是常量池中的，然后会调用 map.put(e,PRESENT)方法，常量PRESENT是一个共享属性(如果没有添加成功会将PRESENT返回)，类型是Object，可以把它理解成节点的 prev指针。
在这里插入图片描述
来到put方法key是java，value是一个空对象，然后继续调用 hash(key)计算哈希值。

来到 hash( ) 判断我们传入的key是否为空，不为空调用hashCode方法进行计算hash值，再将 hash值按位异或无符号向右位移16位避免hash碰撞，不为空返回 hash 值，为空返回 0 。

在这里插入图片描述
一路返回到 put 方法但是，这次有了 hash值。

拿着形参列表hash值和key，value是常量空对象，另外两个布尔类型的值是底层设计者加的我们先不管，来到 putVal 方法。
然后一上来就定义了几个占位变量，Node[ ] tab; Node p; int n ,i ;这几个占位属性后面都是用的到的。

在这里插入图片描述
接着我们步入 if 判断，由于我们是第一次添加数据，table 肯定等于 null,再将 null 赋值给 tab，if 语句第一个表达式成立，然后看逻辑或，tab.length 为 0 赋值给 n 也== 0 ，逻辑或成立，然后会进入if 的代码块。

在这里插入图片描述
然后会调用 resize() 方法，将值赋值给 tab[ ] 数组，然后数组的长度赋值给 n

在这里插入图片描述

来到 resize( ) 已经不是我一两句话能说清楚的了，截图给各位，可以以自己分析，但是执行完该方法，会返回一个默认16长度的数组。

在这里插入图片描述
从 resize( ) 方法出来后 tab就变成了一个 16 长度的数组。

在这里插入图片描述
现在算出要在下标为 3 的地方落点，但是不确定为3 的地方有没有对象，先把里面的对象取出来看一下有没有对象，因为16长度的数组一开始都是null，如果取出下标为 3 的地方是 null 就表示该下标还没有存放元素，就一个 new Node存入到下标为 3 的地方。

在这里插入图片描述

在这里插入图片描述

最后让 ++modCount；记录操作map的次数防止多线程乱入，再判断++size是否大于 threshold，大于则需要再次调用 resize( ) 进行扩容，
afterNodeInsertion(evict); 是一个空方法，是留给子类去使用的，最后返回一个空。
在这里插入图片描述

然后再一路返回add方法，判断 null == null 吗，null 等于 null 就是 true，表示添加成功，如果 map.put(e,PRESENT)返回一个非空数据，就会判断 非空数据 == null ？，肯定不成立返回 false 添加失败。至此HashSet的第一个元素的添加完毕。

HashSet第二次添加元素以及添加重复元素

在这里插入图片描述
接着步入第二次元素的添加

然后就和第一次添加元素的步骤一样了，这里不多说了，还是直接来到重复元素的添加。

在这里插入图片描述

还是一样的配方，一样的味道，我们直接到添加元素的地方。

把数组上已经存在的节点赋值给了 e ，e就不等于 null 就会进入上图的 if 语句，然后将 e.value（PRESENT空对象）赋值给 oldValue,将oldValue返回，等于返回了一个 PRESENT对象
在这里插入图片描述

然后一路返回到add方法，这时返回的是一个空对象PRESENT，然后判断PRESENT == null ？返回 false，添加失败。

重复元素判断的全面详解

上面讲到计算元素下标落点时如果有对象存在，就会走else语句，下面是else语句的全面详解。
在这里插入图片描述

解读else语句

//如果下标落点有元素进入 else 语句还是会进行三次判断//hashCode相同不一定是同一个对象，同一个对象hashCode一定相同Node e; K k;  //定义两个临时变量//p.hash(面计算下标落点时已经将当前下标的元素赋值给了 p)//如果 p.hash值 == 传入的hash值 说明是同一个对象，//然后去比较内容 第一个 && 后面有一个为 true条件就会成立，就会执行e = p;，//如果(k = p.key) == key内存地址形同，返回 true 表达式成立，进入if，  == 对比引用数据类型是比较的内存地址，//如果内存地址不同，就去调用 eques比较两个对象的内容是否相同，内容相同返回 true表达式成立，进入if。//所以一句话，如果两个对象的hash值相同，但是内存地址不同并且内容不同所以就是两个对象。不会进入if语句if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//不进入 if 就会进入 else if 下面是将链表抓换成红黑树，我们先不看。else if (p instanceof TreeNode)e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);//上面没有进入红黑树就会执行最后的 elseelse {//一进来就是死循环for (int binCount = 0; ; ++binCount) {//让 e 执向 数组下标对应 p的下一个节点，如果为空将需要加入的节点放入 p.next p的下一个节点。if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);//如果循环的次数大于等于 7,单向链表的最大限制 8个就调用 treeifBin进行扩容或者转成红黑树//并不是说单个链表的长度一旦达到 8 个就会去扩容的，会先去判断当前数组的长度是否大于等于 64，如果大于 64，会将该链表转换成红黑树。//如果小于 64，就会去考虑扩容来，扩容后再拿着 数组的长度和hash进行运算得出新的下标落点。if (binCount >= TREEIFY_THRESHOLD(8) - 1) // -1 for 1st//最大是8个，循环到第7次就会考虑扩容了，因为是 ++binCounttreeifyBin(tab, hash);//p.next为空添加新的节点后跳出循环。break;}//如果上面p.next == null 没有成立，就表示数组上的当前节点的后面有单向链表//拿着e.hash循环对需要加入的 hash 进行循环对比，有重复的条件成立跳出循环，没有重复的将 p 指向 eif (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}//等到下一次循环，p指向了e，p和e就指向了同一个节点，进入循环后e 又指向了 p的下一个元素，然后就这样进行循环比较，直到 p.next为空将新节点放入跳出循环，或者找到重复元素退出循环。
}

算上数组的元素是 9 个，从 0 开始循环，后面是前++，bin变成了1，循环到binCount = 6 时为第7个节点，bin也为 7，这时加入一个节点达到了8，再进行判断 bin >= 7,进行扩容或树化

第 8 个元素一旦加入，就会进行扩容或数化，有新的元素添加重新计算下标落点
在这里插入图片描述