相信大家对HashMap的底层原理或多或少都有了解，这里简单提一下，jdk1.8版本之后HashMap内部主要通过数组+链表+红黑树的数据结构来存放元素，本文我们来分析HashMap的几个主要方法，看看HashMap的源码具体是如何实现的，以及jdk做了哪些优化来提升性能。

Node节点

static class Node<K,V> implements Map.Entry<K,V> {
    //hash值
    final int hash;
    //元素的key
    final K key;
    //元素的值
    V value;
    //指向下一个节点
    Node<K,V> 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<K,V>[] tab; Node<K,V> 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<K,V> 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<K,V>)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<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> 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
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。