相信大家对HashMap的底层原理或多或少都有了解，这里简单提一下，jdk1.8版本之后HashMap内部主要通过数组+链表+红黑树的数据结构来存放元素，本文我们来分析HashMap的几个主要方法，看看HashMap的源码具体是如何实现的，以及jdk做了哪些优化来提升性能。
Node节点
static class Node implements Map.Entry {
//hash值
final int hash;
//元素的key
final K key;
//元素的值
V value;
//指向下一个节点
Node next;
//此处省略其他代码。。。
}
复制代码Node类是以HashMap的内部类形式存在，代表放入HashMap的元素，字段含义都比较好理解，这里的next字段表示一个指针，指向下一个节点，等会在put方法里分析这个字段的使用场景
put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
复制代码put方法直接调用了putVal方法，可以看到第一个参数传入了hash(key),那我们先来看一下hash方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
复制代码这个hash方法就是用来计算放入map方法的元素的hash值，重点是这段代码(h = key.hashCode()) ^ (h >>> 16)，先通过key.hashCode()获取key的hash值，然后再异或(h >>> 16)计算出最终的hash值，h>>>16表示将hash值右移16位
如果对右移>>>和异或^运算不熟悉的同学，看这行代码可能会比较疑惑，举个栗子：
h值：
1111 1111 1111 1111 1111 1010 0111 1100
h>>>16值：
0000 0000 0000 0000 1111 1111 1111 1111
h ^ (h >>> 16)值：
1111 1111 1111 1111 0000 0101 1000 0011
最终通过h ^ (h >>> 16)计算出来的值才是hash方法获取到的hash值，那么这里为什么要先右移再异或来获取hash值，而不是直接返回hashCode方法拿到的hash值呢？一句话解释就是：为了降低hash冲突，至于为什么能降低hash冲突，我们在后面讲定位元素在数组上的位置的时候再来解释，这里只要知道通过异或操作能将原始hash的高低16位的特征都保留下来，反应在最终的hash值上
hash方法分析完了之后，我们来看下putVal方法，这个方法比较长，里面分支逻辑也比较复杂，我们一点一点来看
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
//1.数组为空，先调用resize方法生成一个数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//2.先定位元素在数组中的位置，如果当前位置元素为空，构建一个Node放入当前位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
//3.当前位置已经存在元素且key相同，直接覆盖当前元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//4.如果当前元素是一个树节点，将新元素挂到树上
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
//5.将元素挂到链表上
else {
//6.遍历链表元素
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//7.构建一个节点，这里就是用next指针来链接节点
p.next = newNode(hash, key, value, null);
//8.如果链表上的元素超过8个，转成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//9.如果当前元素和新元素key相同，直接覆盖链表上的节点
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;
}
复制代码 上面的代码中，我在各个重要代码上加了注释，应该很容易理解，我们来看下几个比较重要的点：
1.定位元素位置：p = tab[i = (n - 1) & hash]
还记得前面留下的问题吗，为什么hash方法要移位和异或操作，这里就来解释清楚，在获取到hash值之后，(n - 1) & hash将hash和数组长度减1进行与操作定位元素在数组上的位置，n在代码里保证了是2的幂次方，比如16、32、64等等，看完这个方法也就明白了为什么要是2的幂次方，同样，我们来举个栗子看看这个操作：
n值假设是16，那么n-1就是15，二进制值为:1111
hash值就用上面的1111 1111 1111 1111 0000 0101 1000 0011，两者取与，结果是11，所以这个元素就会落在索引为11的位置上，这里用与操作而不是对数组取模，主要还是因为性能上的考虑。
那么为什么要用异或操作呢，我们假定前面那个元素叫a,原始hash值是1111 1111 1111 1111 1111 1010 0111 1100，还有另一个元素b的原始hash值是1111 1111 1111 1110 1111 1010 0111 1100，注意和之前元素的区别，它们只有第16位不一样，a是1，b是0
如果没有进行移位和异或操作，那么它俩进行(n - 1) & hash计算之后值是一样的，都是16，也就是会产生冲突，我们再来看看b经过移位和异或操作之后的hash值是什么
b的h值：
1111 1111 1111 1110 1111 1010 0111 1100
h>>>16值：
0000 0000 0000 0000 1111 1111 1111 1110
h ^ (h >>> 16)值：
1111 1111 1111 1111 0000 0101 1000 0010
所以b最终的hash值为1111 1111 1111 1111 0000 0101 1000 0010，求与(n - 1) & hash之后就是10，也就是定位到了索引为10的数组位置，和a不冲突了，感受到了么，这就是移位和异或的作用，降低元素在数组位置上冲突的概率。
2.链表转红黑树： treeifyBin(tab, hash); 这个方法简单来说就是将链表转成了一颗红黑树，内部实现还是很复杂的，有兴趣的可以自己去看源码。
resize方法
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
//1.hash值&老数组长度等于0
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//2.hash值&老数组长度不等于0
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
//3.放到新数组的原位置
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
//4.放到（老数组长度+原位置）的新位置
newTab[j + oldCap] = hiHead;
}
复制代码 HashMap扩容的时候会先生成一个容量为老数组2倍的新数组，然后将老元素拷贝到新数组上，上面代码是从resize方法里摘出来的确定扩容之后新元素位置的代码，注释1那里通过元素hash值和原数组长度取余是否为0就可以快速确定放在新数组的位置，如果为0，就放在老位置，如果不为0就放在新位置，新位置通过老数组长度+原位置来确定，同样，我们来举个栗子理解一下：
假设，hash为1111 1111 1111 1111 0000 0101 1000 0011，数组从16扩容到32，通过e.hash & oldCap计算值为0，所以在新旧数组上的位置都是11
另有hash为1111 1111 1111 1111 0000 0101 1001 0011的元素，数组从16扩容到32，通过e.hash & oldCap计算值为1，所以在新数组上的位置就变成了11 + 16 = 27，不再是原来是的11
总结
本文主要讲述了HashMap以下几个实现：
1.计算hash值（移位、异或操作）
2.寻址算法优化（&操作代替取模）
3.put()方法实现（挂链表以及链表转红黑树）
4.resize方法实现（rehash定位新数组中的位置）
以上，希望对你理解HashMap有帮助，有不同看法或疑问欢迎随时和我讨论
作者：haixiang
链接：
https://juejin.cn/post/6986447578111934500
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
