关于 add 方法
add 方法是 HashSet 最常用的方法之一。
作用：如果集合中不包含此元素，则添加到此集合。
返回值：如添加成功，返回 true ，反之返回 false 。
案例代码
我会以下面这段代码为例，分析 add 方法底层究竟在干什么。
public class Main {public static void main(String[] args) {HashSet set = new HashSet();System.out.println(set.add("java")); // trueSystem.out.println(set.add("php")); // trueSystem.out.println(set.add("java")); // falseSystem.out.println(set);}}
流程总结：
1、添加一个元素时，先计算 hash 值，再计算索引值。
2、找到存储数据表 table，看一下这个索引位置是否已经存放了元素。
3、如果已经存放了，调用 equals 比较两个元素，如果相同就放弃添加，如果不相同，就添加到该索引位置的链表尾节点处。
4、在 Java 8 中，如果一条链表的元素个数超过 TREEIFY_THRESHOLD （ 默认是 8 ），并且 table 的大小 >= MIN_TREEIFY_CAPACITY（ 默认 64 ），就会进行树化（红黑树）。
源码分析
针对上面的案例代码，进行逐行分析，力求把 add 方法的底层逻辑嚼碎、嚼烂。
1、无参构造器
public HashSet() {
map = new HashMap<>();
}
HashSet 有一个 HashMap 类型的属性 map，HashSet 的数据都借助此对象保存。
private transient HashMap<E,Object> map;
所以 HashSet 的无参构造器实际上是实例化了一个 HashMap 对象赋给了自身的 map 属性。
2、set.add(“java”);
此时 set 为空，第一次 添加：”java”。
2.1、HashSet -> add()
首先，set.add 直接调用了 map.put ，也就是说 HashSet 的 add 方法实际上是在调用 HashMap 的 put 方法添加数据。
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
HashMap 的 put 方法有两个参数，分别是 key ， value 。显然这里的 e 是我们添加的数据，HashSet 将我们要存储的数据放在了 put 方法的 key 参数位置，而 value 参数位置是一个叫 PRESENT 的玩意儿，这东西是 HashSet 内部定义的一个静态 Object ，这样 HashMap 在存储的时候 value 对象就是复用同一个，不会浪费额外的空间。所以，PRESENT 本身其实没什么意义，只起到了占位的作用。
2.2、HashMap -> put
map.put 调用了自身的 putVal 方法，也就是 HashMap 类的 putVal。不过，在调用 putVal 前还调用了 hash。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
2.3、HashMap -> hash
对传入的 key 进行 hash ，可以看出，计算后的 hash 值是 int 型。
1）如果 key 为 null ，直接返回 0；
2）调用 key 自身的 hashCode 方法，并且将结果进行异或运算后，再无符号右移了 16 位；（ 哈希算法的目的就是为了尽可能的让不同的值计算后得到的不同的哈希值，尽量避免 hash 碰撞 ）
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
此时，我们就知道，在上面第 3 点，调用 putVal 前， HashMap 会先对 key 进行 hash。
2.4、HashMap -> putVal()
继续看一下 HashMap 的 putVal 方法，这个是重头戏。
先看一下参数：
- int hash：key 的 hash 值；
- K key：key；
- V value：value；
- boolean onlyIfAbsent：如果为真，不改变现有值；
- boolean evict：如果是false，则表示该表处于创建模式。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
下面我们逐行对源码进行分析，需要点耐心。逐行分析之后，还有一个大体的总结可以作为日常复习的内容。
第 3 行：
Node<K,V>[] tab; Node<K,V> p; int n, i;
1）定义了几个辅助变量
第 4-5 行：
关于这段，你可以理解为，如果当前 table 是 null 或者 length（长度/大小） 为 0 时，进行第一次扩容。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
此处的 table 是 HashMap 的一个属性（ transient Node
1）先将 table 赋给辅助变量 tab ；
2）判断 tab 是否为空，如果为空，就执行 resize 方法，并将返回值赋给 tab ；
3）令 n 等于 tab 的 length ，由于刚创建时 table 一定是空的，所以这个 resize 方法一定会执行。
这里先不提 resize 方法的源码，继续往下看。你目前只要知道，resize 方法返回了一个 大小为 16 （默认值）的空数组并赋给了 tab 这个辅助变量即可。关于 resize 在后面专门挑出来说。
第 6-7 行：
如果目标索引处没有存放过元素，则创建一个 Node 对象放入。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
n 是 table resize 后的 length ，也就是 16，hash 是 key 经过计算后得到的哈希值。
1）计算 (n - 1) & hash 并将其赋给 i ；
2）计算索引值：(n - 1) & hash 实际上是在计算索引值 / 数组下标，也就是这个 key 对应的哈希值应该存储到 tab 的哪一个索引位置上。
3）取出tab[ 索引值 ] 位置的 Node，赋给辅助变量 p；
4）判断 p 是否为 null；
5）如果 p 为 null，说明该索引处尚未存放过元素，就实例化一个 Node 对象放入 tab[ 索引值 ] 。
因为进入了 if ，所以 else 分支的内容就不再执行，也就是第 8-36 行的部分。
第 37 行：
modCount 加 1
++modCount;
modCount 记录的是 HashMap 对象修改的次数，在 HashMap 的 put(), get(), remove(), Interator() 等方法中,都使用了该属性。由于 HashMap 不是线程安全的，所以在迭代的时候,会将 modCount 赋值到迭代器的 expectedModCount 属性中,然后进行迭代，如果在迭代的过程中 HashMap 被其他线程修改了，modCount 的数值就会发生变化，这个时候 expectedModCount 和 ModCount 不相等，迭代器就会抛出 ConcurrentModificationException() 异常。
第 38-39 行：
如有需要，进行 resize 。
if (++size > threshold)
resize();
先看一下参数：
- size：当 HashMap 存储的元素个数；
- threshold：存储当前 HashMap 容量大小的 0.75，这个值在 resize 时会被更新（此时因为 HashMap 的容量是 16，所以 threshold 为 12）；
很明显了，如果当前 HashMap 的 size 达到了总容量的 75%，就执行一次 resize 。
第 40 行：
预留扩展点
afterNodeInsertion(evict);
evict：putVal 的第 4 个参数。
afterNodeInsertion 方法实际上是 HashMap 预留给子类（ LinkedHashMap ）的扩展点，实际上是空方法。
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
第 47 行：
putVal 方法返回 null，
return null;
因此，HashSet add 会返回一个 true ，代表添加成功了。
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
到这里，就完成了 HashSet 初始化，并使用 add 方法向其新增了一个元素（”java”）的操作。输出 HashSet 的内容，可以看到里面已经新增了一个 “java”
3、set.add(“php”);
此时，set 中已经添加了一个 “java”，现在添加一个 “php”。
前三步和 2.1 / 2.2 / 2.3 一样，就不重复讲了，跳过这些重复的步骤，直接讲第四步。
3.1、HashMap -> putVal()
继续看一下 HashMap 的 putVal 方法，这个是重头戏。
先看一下参数：
- int hash：key 的 hash 值；
- K key：key；
- V value：value；
- boolean onlyIfAbsent：如果为真，不改变现有值；
- boolean evict：如果是false，则表示该表处于创建模式。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
第 3 行：
Node<K,V>[] tab; Node<K,V> p; int n, i;
1）定义了几个辅助变量
第 4-5 行：
关于这段，你可以理解为，如果当前 table 是 null 或者 length（长度/大小） 为 0 时，进行第一次扩容。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
因为当前 set 中已经添加了一个 “java”，所以 table 和 tab 是非空的，这个 if - else 显然不执行。
第 6-7 行：
与上次添加 java 字符串时一样，只要计算出来的哈希不冲突，这里的索引位置就不会一致，所以会进入 if 的逻辑里 new 一个 Node 放入索引。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
通过 debugger 逐行调试发现，字符串 “php” 计算出来的哈希值是 110969 ，计算出来的索引值 i 是 9。
第 37 行：
修改次数加 1
++modCount;
执行到这里时，通过 debugger 可以看到，table 中索引 9 的位置已经放入了 “php” 元素。
第 38-41 行：
size + 1，没有超过阈值，因此不会触发 resize ，afterNodeInsertion 是空方法，至此，”php” 字符串已经被添加进去了。
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
4、set.add(“java”);
set 中已经添加了 “java” 和 “php” ，现在添加 “java” 。
前三步和上面一样，就不重复讲了，跳过这些重复的步骤，直接讲第四步。
4.1、HashMap -> putVal()
继续看一下 HashMap 的 putVal 方法，这个是重头戏。
先看一下参数：
- int hash：key 的 hash 值；
- K key：key；
- V value：value；
- boolean onlyIfAbsent：如果为真，不改变现有值；
- boolean evict：如果是false，则表示该表处于创建模式。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
第 3 行：
Node<K,V>[] tab; Node<K,V> p; int n, i;
1）定义了几个辅助变量
第 4-5 行：
关于这段，你可以理解为，如果当前 table 是 null 或者 length（长度/大小） 为 0 时，进行第一次扩容。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
因为当前 set 中已经添加了 “java” 和 “php” 两个元素，所以 table 和 tab 是非空的，这个 if 显然不执行，不会执行 resize 操作。
第 6-7 行：
判断 tab[ 索引值 ] 处的 Node 是否为 null，显然在 1.2 这个步骤已经添加过 “java” 这个元素，因此现在第二次添加的 “java” 计算出来的哈希值与上次一致，所以这个索引位置的 Node 一定非空，这个 if 逻辑不会执行，进入 else 部分。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
第 9-12 行：
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
p.hash 是 Node 构造器执行时传入的参数，也就是第 7 行处的 hash ，我们知道 hash 是 key 的哈希值，因此这个 p.hash 就是 key 的哈希值。
p.key 也是一样，是 Node 构造器执行时传入的参数，其实也就是 key 。
至此，我们知道了 p.hash == hash 是在判断 table[ 索引值 ] 处对应的 Node key 的哈希值是否等于当前的 key 的哈希值。需要注意的是，如果哈希值相等，只能说明发生了哈希碰撞，并不能肯定说两个 key 的值一定是相同的。所以就有了后面的一个表达式，只有这个表达式为真，并且哈希值一致，我们才能肯定，该位置的 Node key 与当前传入的 key 相等。
((k = p.key) == key || (key != null && key.equals(k)))) 这个表达式实际上做了这样几个事
1）将 p.key 赋给 k ，如果 key == k ，则说明是重复添加了一样的元素，该表达式为真，不再继续判断；
2）如果 key != k ，则调用 key 的 equals 方法判断 是否与 k 相等。
以上两个条件任意一个为真，表达式结果即为真，那么就会执行 e=p 操作，即被判定为重复对象，无法加入 table。
第 29-35 行：
被判定为重复对象后，执行到这里。
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
如果 e != null 的话，按照一般重复添加重复对象处理，null 算是一个比较特殊的值。
到此就结束了，之后 add 会返回一个 false ，表示添加失败，因为 table 中已经有了 “java”。
我们继续往下分析，还有一些代码块没有讲到。
第 13-14 行：
判断 p 是不是一颗红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
如果 p 是一颗红黑树，就按照红黑树的规则去添加该元素，并按照红黑树的规则判定是否为重复元素，也就是调用 TreeNode 的 putTreeVal 方法。
如果这个情况也不满足，则进入 else 块
第 15-28 行：
p.key != key ，p 也不是一颗红黑树，则把 p 当成链表的头，使用 for 循环遍历，如果遍历完链表发现没有重复的元素，则将数据加入到链表尾部，如果遍历中发现重复元素，则直接退出循环不再继续往下判定。
最后，如果链表的长度大等于 7 ，则将该链表转换为红黑树。
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
至此，HashSet 的 add 方法的底层流程大体讲解的差不多了。实际上，讲 HashSet 就是在讲 HashMap 。
若有收获，就点个赞吧
0 人点赞
