解读HashMap中put方法的源码
解析hashMap的put方法是如何存储一个键值。
一、 put方法
代码1-1 V put(K key, V value)方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}调用put方法存储键值，实际上是调用了HashMap的putVal方法，putVal方法的调用过程中 执行了hash(key) 获取了一个int类型的值
代码1-2 int hash(Object key)方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}首先该hash方法声明了一个 int类型的值 h ，int类型占4个字节 共32位，然后调用key的hashCode方法获取一个key的散列码 并将该散列码赋值给h，最后执行h^(h>>>16)并返回结果。
解析h^(h>>>16)，首先将h无符号右移16位，右移的结果是 32位h的低16位变为高16位的值，而高16位则全部变为0 例如：
0010 1100 1010 0000 0001 0100 1010 0001 将h无符号右移16位--》
0000 0000 0000 0000 0010 1100 1010 0000 位移后的结果
之后将h 与 位移后的结果做一个异或运算，整个操作也可以解读为 h的高16位保持不变，将高16位和低16位异或的结果赋值给 低16位 ，最终返回一个更加散列的散列码(也就是将key.hashCode()再一次散列)。
二、 putVal方法
我编写了一段代码 通过debug来观察putVal方法的执行过程，如下：
代码2-1 自定义代码(debug的断点位置已标明)
public static void main(String[] args) {
HashMap<strKey, Object> stringObjectHashMap = new HashMap<>();
strKey strKey = new strKey("a", "b");
strKey strKey2 = new strKey("b", "a");
//strKey和strKey2的哈希值相同
System.out.println(strKey.hashCode());
System.out.println(strKey2.hashCode());
断点1 stringObjectHashMap.put(strKey, "hello");
断点2 stringObjectHashMap.put(strKey2, "hi");
}
//创建全参构造方法，重写equals和hashcode方法
@AllArgsConstructor
public static class strKey {
private String a;
private String b;
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
strKey strKey = (strKey) o;
return Objects.equals(a, strKey.a) && Objects.equals(b, strKey.b);
}
@Override
public int hashCode() {
if (a == null || b == null)
return 0;
int result = 1;
result = 31 * result + a.hashCode() + b.hashCode();
return result;
}
}putVal方法的代码如下：
代码2-2 V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//table是一个 Node<K,V> 类型的数组
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;
}debug 的执行过程如下：
在构造出HashMap类型的对象后，执行断点1处的put方法第一次存储一个键值。
HashMap中存在一个成员变量table，变量table是 Node<K,V> 类型的数组 初始为null，putVal方法最先执行如下代码 第一次调用resize方法做容量的初始化。
代码2-3 putVal方法的第一步
//table最开始为null
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
代码2-4 resize()方法第一次被调用时 主要执行的代码
//声明newCap、newThr ，newCap 为新的容量，newThr为最新的扩容阈值 int newCap, newThr = 0 /** DEFAULT_INITIAL_CAPACITY的值为 1 << 4 ,即值为16 也就是默认的初始化容量是16，DEFAULT_LOAD_FACTOR的值为0.75f , 也就是 默认的加载因子为0.75 **/ newCap = DEFAULT_INITIAL_CAPACITY newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY) //threshold 为扩容阈值 ，是HashMap的成员变量 threshold = newThr; Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab;//将新创建的Node<K,V> 数组赋值给成员变量table return newTab; //返回newTab
在代码2-3执行结束后，HashMap第一次初始化时的容量 16 已经赋值给 putVal 方法的局部变量 n
，之后执行putVal 方法的第二步：
代码2-5 putVal方法的第二步
第二步的执行过程中 将hash(也就是在代码1-2中将key的hashCode再次散列的结果) 与 （n-1）也就是15的 二进制 进行一个 与运算，运算的结果是数组tab的下标，因为HashMap的结构是 由 数组+链表+红黑树组成 其实就是 Node<K,V>[] table，数组的每个位置 最初都是一个可以延长的链表，所以最开始应该确定 put存放的元素应该存储在 数组table的哪个位置。
(n - 1) & hash 的最终结果 <= 15 ，有兴趣的读者可以去了解一下 & 运算。
/**
在代码2-3中其实就已经将 table 赋值给了 tab，由于是第一次执行，数组的所有位置都为null，所以将 hash、key、value 构造成一个Node<K,V>对象 并赋值给tab[i]。
**/
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
代码2-6 putVal方法第三步
++modCount; //modCount会加一 //判断数组容量是否超过阈值，如果超过阈值则调用resize()来扩容，现在是第一次添加 不会执行扩容操作。 if (++size > threshold) resize();
至此断点1就执行完毕，下面开始执行断点2
由于断点1的执行过程中已经进行了初始化 那么断点2的执行直接跳过初始化
代码2-7 putVal方法第一步
首先获取key所在的数组下标。
由于重写了hashCode方法，致使strKey的hashCode和 strKey2的hashCode相同，但是他们equals的结果却不相同，这里使strKey和strKey2的hashCode相同的目的是为了制造散列冲突（散列冲突指的是 ”桶“ 已经被填充的现象，也就是元素对应的node数组下标的位置已经有值了），即由于hashCode相同导致不同的元素存放在node数组的同一位置，要注意hashCode即便是相同的也会出现散列冲突，这里只是为了模拟散列冲突所以设置了相同的hashCode
//发生了散列冲突，if括号内的结果为false，并且将发生冲突的位置的node赋值给 Node<K,V>类型的 p
if ((p = tab[i = (n - 1) & hash]) == null)
由于第一步的结果为false 所以执行如下代码
代码2-8 putVal方法的第二步
在第一步中已经说明发生散列冲突时，hashCode可能不相同，也就是代码中的 局部变量 hash 可能不相同（前面已经说明过，hash是hashCode再次散列的结果，所以hashCode相同 hash一定相同）
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;
}
}
那么我开始解读代码2-8中 else代码块各个步骤的含义：
首先看一下node的结构
每一个node 是由put方法传入的key、value、key所对应的hash以及下一个node组成，其实就是链表的结构，也就是所说的 HashMap是由数组+链表组成，数组中的每一个元素就是 一个node，也就是链表的第一个节点。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
...............
}
1、此时p是tab[i]处的元素，也是链表的第一个node
首先判断p的key的hash和要存入的key的hash是否相同，如果hash不相同 也就是 hashCode不相同，那么两个key一定不是同一个对象 结果返回false，但也有可能出现不同对象的hash相同的情况，所以会出现后续判断 (k = p.key) == key || (key != null && key.equals(k))，如果p的key的内存地址和传入的key的内存地址相同则两个key一定相等，或者equals的结果相同，则两个key也可以判定为相同，判断的最终结果为true 则执行 e=p，如下代码块：
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else{ .................../**
if为true 则表示p的key和传入的key相同，那么以下操作的意思就是，将put方法的value值覆盖p的value值，也就是所说的 HashMap的put方法中如果key相同，则旧的value将会被新的value替换
**/
if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; }
2、 由于strKey和strKey2进行equals的结果为false，那么就执行到下图：
此处会判断p是不是一个树节点，当链表长度大于8 数组长度大于64的时候，链表会转变为红黑树
由于此时还未转变为红黑树则执行到下一步骤
3、该步骤如图所示：
要注意的是 for循环中可能执行多次 e=p.next ，p=e的操作 所以binCount可能是链表中的任意一个位置，图中的for循环先执行如下代码：
if ((e = p.next) == null) {//if判断p的下一个node是否为空
/**
如果p的下一个node为空，则将key、value、以及key对应的hash构造出一个新的node 来作为链表的最后一个node
**/
p.next = newNode(hash, key, value, null);
// TREEIFY_THRESHOLD的值为8，如果链表长度已经达到8 则会调用treeifyBin方法尝试将链表转变为树
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
treeifyBin方法的部分代码如下：
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//MIN_TREEIFY_CAPACITY的值为64，如果数组长度小于64则会调用resize方法进行扩容，否则就会执行将链表转为红黑树的操作
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else{
..............
}
for循环也可能执行后面的代码 来跳出循环，如下所示：
这个操作的意思是，可能该链表的某个node的key和传入的key相同，则将新的value覆盖该node的value值
else {
for (int binCount = 0; ; ++binCount) {
........
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;
}
至此结束调试，如有疑问欢迎留言一起探讨。