HashMap源码分析

原创

编程之心

修改于 2020-09-23 10:18:26

4550

修改于 2020-09-23 10:18:26

文章被收录于专栏：编程之禅编程之禅

哈希表的由来

哈希表的出现是从数组能够根据索引随机访问这个特性发展而来的。

将元素的关键字Key通过哈希函数，均匀映射为数组下标，将键对应的值存储在数组中。

下次查找时，通过相同的方式，对关键字做哈希运算，得到下标，获取数组中的存放的值。

设计哈希函数的三原则

哈希函数计算得到的哈希值是一个大于等于0的整数。
如果关键字key相同，那么经过哈希计算后的哈希值也要相同。
如果经过哈希计算后的哈希值不相同，那么关键字key就不能相同。

第三点是理想情况，事实上做不到。即无法完全避免这种散列冲突。

负载因子

当数组快满的时候，需要扩容，而达到扩容的标准叫做负载因子loadFactor。

负载因子表示：已存储的数据量 / 总共能存储的数据量。

如果负载因子过大，那么剩余能用的空间就越少，越容易发生冲突。但如果负载因子过小，又容易频繁扩容，扩容之后要重新哈希计算放到新哈希表中，也对性能有影响。

哈希冲突

如果遇到了散列冲突，解决办法有两种：开放寻址法与链表法。

开放寻址法又可分为线性探测，二次探测与双重散列。

线性探测：当前存储位置被占用了，就每次向下一个找空余的位置。索引依次是hash(key)+0，hash(key)+1，hash(key)+2。

二次探测：和线性探索差不多，只是步长是原来步长的二次方。索引依次是hash(key)+02，hash(key)+12，hash(key)+22

双重散列：当使用了第一个哈希函数对key进行哈希，值冲突了，就用第二个哈希函数，还冲突就用第三个哈希函数。hash1(key)，hash2(key)，hash3(key)

开放寻址法适合数据量小、装载因子小（就是动不动就会扩容的），ThreadLocalMap就是使用的是开放寻址法。

因为hashMap用的是链表法。开放寻址法就不细说了。

链表法：散列表的每个桶/槽都对应一条链表，如果出现了哈希冲突，即哈希值相同了，就依次放在后面的链表中。

链表法的好处是可以有更大的装载因子，因为即使冲突了，就是在链表后面追加。只是查找效率下降。但如果哈希函数做的非常随机均匀，链表也不会太长的。

Java中的HashMap

下面就拿JDK1.8中的HashMap实现来看看。

源码中的常量

HashMap构造方法

HashMap的数组初始值是16。每次扩容2倍。数组长度一定是2的n次方（Java源码中控制的），所以是一个合数（这不是一种常规设计，常规设计是把数组长度设计为素数，比如hashTable初始值是11。相对来说素数的冲突概率小于合数。HashMap采用数组长度2的n次方设计，主要是为了后续取模与扩容时的优化）

就算使用者给的初始大小值不是2的n次方，Java也会把值更改为大于等于给定值的最小2的n次方。

HashMap的构造方法

HashMap的构造方法的前面几行代码，是做参数校验。负载因子要大于0。

比较有意思的是tableSizeFor方法，通过五个位移运算+异或运算。最后的+1操作，得到大于等于初始容量值的最小2的次方数。这里的cap是用户设置的初始哈希表容量大小值。Java会把这个值改成大于等于这个值的最小2的次方数。（2的次方数这个特性在后面的取模与扩容时的会用到

在阿里巴巴的开发手册中有一条规则，如果有很多数据需要储存到 HashMap 中，建议 HashMap 的容量一开始就设置成足够的大小，这样可以防止在其过程中不断的扩容，影响性能；

为什么1.8后加入红黑树？

JDK1.7中，HashMap底层使用数组+链表。

利用了数组快速检索与链表快速增删双特性，强强结合。

对于正常数据，由于优秀的哈希算法与自身的扩容机制，能够均匀散列，发生冲突概率很小，所以链表长度通常不会很长，所以即使链表是O(n)的遍历速度，因为很短，也不会有很大的影响。

但如果是黑客被精心构造的数据，会将散列表构造成只有一条长长的单链表，

查询的时间复杂度从O(1)上升到O(n)，原本可能查询效率0.1秒，被攻击后变成了1万秒。造成查询操作消耗大量资源，导致其他请求无法响应，从而达到DoS（拒绝服务攻击），这是散列表碰撞攻击的基本原理。

之后JDK1.8 HashMap底层改为了数组+链表+红黑树。

变化为当链表长度超过阈值8即达到9个时，并且数组长度>=64时，会将链表转化为红黑树（数组长度<64时，只会扩容，不会转化为红黑树，因为数据量还很小没有必要），转化为红黑树后如果同样被之前所讲到的散列碰撞攻击，查询时间复杂度会从O(1)升级为红黑树查询时间复杂度的O(logn)而不会再是单链表的O(n)了。当红黑树结点个数少于6时（是6不是8，因为设定为8，如果节点个数持续在8左右徘徊变动，就会频繁进行二叉树与链表的转换，消耗性能损耗），

会退化为链表，因为相对于链表，一条红黑树的维护成本更高。（但正常使用情况下，链表长度能达到8的概率非常小，源码注释中写的概率是0.00000006

HashMap是如何计算存放哈希桶数组索引位置

分为三步：取key的hashCode值、高低16位混合（扰动函数）、取模运算。

去讲之所以需要进行高低16位混合，先要讲取模运算。

单纯的取模运算，用数组长度对哈希值取模确认存放的数组下标，即哈希值%length 作为底层使用会耗时，Java将其改成了h& (length-1)，因为Java数组的长度每次扩容是原来的两倍，长度都是2的n次方，基于这个公式：x mod 2^n = x & (2^n - 1)，所以h%length 与h& (length-1)结果是等价的，而&与运算的效率会高于%取模运算。

Java源码：

// 将(tab.length - 1) 与 hash值进行&运算
int index = (n - 1) & hash;

但随之也带来个一个问题。就是数组-1(即n-1)转成二进制的结果通常只有低16位有值。

而数组-1的高16位有值，则至少需要0000 0000 0000 0001 1111 1111 1111 1111，（数组长度是2的n次方）转成十进制是n-1=131071，即n=131072（2的17次幂）。通常开辟的HashMap很少有131072这么大的，这也造成了(n-1)的高16位通常一直都是0，而0与上任何值都是0。也就造成了被与运算的哈希值的高16位对结果没有产生任何影响。

所以Java源码中对Hash值的计算做了优化，将高16位右移，与原来的低16位做了异或运算，这样新的结果的低16位保留了原来高低16的所有特征。即使(n-1)的高16位还是0，只有低16位有效，但优化后的新Hash值的低16位保留了原本高低16位的特征，这样就确保了哈希值的高低16位对最终的结果都会产生了影响，这样最后的hash结果可以更加散列，碰撞概率更低。

static final int hash(Object key) { // 计算key的hash值
    int h;
    // 1.先拿到key的hashCode值; 2.将hashCode的高16位参与运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

总结：一共三步骤。1.取对象的hashCode值。2.做hash算法优化（扰动函数），确保哈希值低16位保留了高低16位的特征。3.最后再和数组长度-1做与运算计算数组的下标。

存放值的put方法

HashMap存储值put()方法大致步骤：

对 key 计算存放哈希桶数组索引位置;
如果当前数组为 null，进行容量的初始化，初始容量为 16；
如果 hash 计算后没有碰撞，直接放到对应数组下标里；
如果 hash 计算后发生碰撞且节点已存在，则替换掉原来的对象；
如果 hash 计算后发生碰撞且节点已经是树结构，则挂载到树上。
如果 hash 计算后发生碰撞且节点是链表结构，则添加到链表尾，并判断链表是否需要转换成树结构（默认大于 8 的情况会转换成树结构）；
完成 put 后，是否需要 resize () 操作（数据量超过 threshold，threshold 为初始容量和负载因子之积，默认为 12）。

示意图：

源代码

// 入参 hash：通过 hash 算法计算出来的值。
// 入参 onlyIfAbsent：false 表示即使 key 已经存在了，仍然会用新值覆盖原来的值，默认为 false
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // n 表示数组的长度，i 为数组索引下标，p 为 i 下标位置的 Node 值
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //如果数组为空，使用 resize 方法初始化
    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);
    // 如果当前索引位置有值的处理方法，即我们常说的如何解决 hash 冲突
    else {
        // e 当前节点的临时变量
        Node<K,V> e; K k;
        // 如果 key 的 hash 和值都相等，直接把当前下标位置的 Node 值赋值给临时变量
        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) {
                // e = p.next 表示从头开始，遍历链表
                // p.next == null 表明 p 是链表的尾节点
                if ((e = p.next) == null) {
                    // 把新节点放到链表的尾部 
                    p.next = newNode(hash, key, value, null);
                    // 当链表的长度大于等于 8 时，链表转红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                // 链表遍历过程中，发现有元素和新增的元素相等，结束循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                //更改循环的当前元素，使 p 在遍历过程中，一直往后移动。
                p = e;
            }
        }
        // 说明新节点的新增位置已经找到了
        if (e != null) {
            V oldValue = e.value;
            // 当 onlyIfAbsent 为 false 时，才会覆盖值 
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            // 返回老值
            return oldValue;
        }
    }
    // 记录 HashMap 的数据结构发生了变化
    ++modCount;
    //如果 HashMap 的实际大小大于扩容的门槛，开始扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}