Java1.8 HashMap源码分析

一、HashMap的特点

    HashMap是基于hash算法+数组+链表+红黑树实现的，重要性逐渐提高

    1、hash算法就是将任意长度的值通过算法转换成固定长度的值

    2、数组最大的优点就是随机访问的时间复杂度为O(1)，得到hash算法转换后的值（下标），那么就能实现时间复杂度为O(1)的查询功能。

    3、O(1)的时间复杂度是建立在最理想的hash算法之上的，再好的hash算法也会存在哈希冲突，为了解决hash冲突同时满足新增、修改、删除、扩容等高性能需求，那么链表就闪亮登场了（至于为什么不直接使用红黑树，可查看细节中3）

    4、链表最大的缺点就是查询的时间复杂度为O(n)，如果hash算法太差，或者其他原因（例如Hash Collision Dos攻击）导致hash冲突严重，查询性能急速下降，在Java1.7版本会导致CPU飙升，所以Java1.8使用了红黑树来解决长链表的查询性能问题，此时时间复杂度从O(n)下降至O(logN)

    总结：从上述可看出，hash算法决定了HashMap的性能高低，所以官方每次对HashMap的优化无非就是一方面提高hash算法的分散性（越分散，碰撞率越低，空间利用率就越高），一方面尽可能地提升hash算法极差时的稳定性（使用了链表、红黑树和扩容来保证），简单一句话就是提高HashMap的下限和上限，那么整体的性能就能提升了。

    提示：HashMap和ArrayList作为容器中两大杀器，使用率基本是极高极高的，每一点点的性能提升都是值得追求的，那么下面我们看看HashMap的细节之处，究竟是如何提高HashMap的性能的。

二、HashMap细节

    1、扰动函数hash(key)

        Java1.8对Java1.7做了优化，将多次位运算减到一次位运算 和一次异或运算，也就 是高低位异或，提高分散性，降低hash碰撞率

        可参考知乎：JDK 源码中 HashMap 的 hash 方法原理是什么？

    2、treeifyBin方法中如果容量小于64直接扩容

/**
 * 扩容,因为hash冲突严重(大于1/3)
 * 1、tab.length为32时，threshold=24(负载因子=0.75)
 * 2、单个bucket的链表长度已经达到9了(大于8才转树形结构)
 * 碰撞率>=8/24,碰撞率已经很严重了,直接扩容
 */
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
   resize();
           

    3、链表长度大于8(包括添加节点)时转红黑树

        受几个因素影响：

        ①树节点TreeNode比Node大很多（TreeNode继承LinkedHashMap.Entry继承 Node，一个Entry有两个Entry引用8个字节，一个TreeNode有4个TreeNode引用16个字节，1个布尔值1个字节，而Node为8+4+4+4=20个字节，两者比例为45:20）

        ②链表查询的平均时间复杂度为O(n)，而红黑树的为O(logN)

        ③对于增删改，红黑树需要考虑保持平衡的性能消耗（旋转）

        ④根据Poisson distribution（泊松分布），达到8的链表长度概率几乎为0

        ⑤如果阈值太小，退化为链表时就会存在频繁的树化和退化的情况

    4、扩容后红黑树节点小于等于6时退化为链表

        确定树化阈值为8后，退化的阈值就相对好确定了：

        ①比树化阈值小是为了缓冲上面⑤的情况

    5、扩容函数

        ①最大容量为2^30

if (oldCap >= MAXIMUM_CAPACITY) {
    /**
     * threshold变成MAX_VALUE(2^31-1),随它们碰撞,但是oldCap不改变。
     * 为什么不扩容了呢？--> 为什么capacity扩容都是扩大一倍并且是2的幂次方呢？
     * 这里涉及到扩容中的逻辑e.hash & (oldCap - 1) 跟空间利用率
     * 假如当容量扩容到最大值MAX_VALUE(2^31-1)时,转换成二进制
     *            hash
     *      &
     *            0111 1111 1111 1111 1111 1111 1111 1110
     * ---------------------------------------------------
     *            xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxx0
     * 从上面可看出无论hash最低位是0或者1,结果的最低位都为0,也就是下标只有2^30个位置被使用,有
     * 2^30-1个下标没有被使用
     * 所以当容量为MAX_VALUE(2^31-1)时会造成一半的空间浪费,效率等同于未扩容前的
     * MAXIMUM_CAPACITY(2^30)
     * 总结：如果capacity扩容后的容量不是2的幂次方，空间利用率最高不超过50%
     */
    threshold = Integer.MAX_VALUE;
    return oldTab;
}
           

        ②容量大于等于16的扩容不重新计算threshold

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
         oldCap >= DEFAULT_INITIAL_CAPACITY)
    /**
     * 为什么需要判断oldCap >= DEFAULT_INITIAL_CAPACITY呢？
     * (这问题类似于数组下标为什么从0开始？cpu计算数组地址公式baseAddress+n*typeSize和
     * baseAddress+(n-1)*typeSize为了省去cpu计算n-1的指令)
     * 当容量capacity较小时 threshold=capacity * loadFactor 造成的误差比较大,
     * 例如初始化容量为capacity=2 * loadFactor=0.75 threshold=1,如果每次扩容threshold都翻倍,
     * 第二次：threshold=2
     * 第三次：threshold=4
     * ....
     * 那么误差就越来越大了，所以为了降低误差，容量较小时还是需要重新计算threshold
     * 为什么只小于16呢？
     * 个人猜测是在每次扩容都计算newThr和用位运算翻倍之间做权衡
     * 因为loadFactor默认值为0.75,当capacity>=4的时候，当capacity*loadFactor是没有小数的，
     * 所以threshold是没有误差的，所以如果需要设置loadFactor，
     * 最好是使得capacity（1,2,4,8）*loadFactor=整数
     * 如果 loadFactor=0.6 初始化容量capacity=8  则threshold=4
     * 下次扩容：threshold=8 capacity=16 由于capacity>=16的时候不会再次计算threshold
     * 所以，这个时候loadFactor相当于从0.6降低到了0.5
     */
    newThr = oldThr << 1; // double threshold
           

        ③扩容后位置，1.8根据hash值对应的最高位决定

if (e.next == null)
    /**
     * e.hash & (newCap - 1) 重点，要考！
     * newCap - 1 ：最高位1到最低位全是1，因为容量是2的幂次方
     * newCap = oldCap*2
     * 节点在oldTab中的下标为：e.hash & (oldCap - 1)
     * 节点在newCap中的下标为：e.hash & (oldCap*2 - 1)
     * 那么(oldCap - 1) 与(oldCap*2 - 1) 的差别就是在最高位的差别，后者比前者多一位最高位1
     * 例如32 -1 与64-1 换成二进制就明显了
     * 那么最终的下标就在于e.hash 对应 (oldCap*2 - 1)或者(newCap - 1) 最高位的bit是0或1了
     * 转化为：e.hash & oldCap
     * 0下标不变，1下标=原下标+oldCap
     * 这么做有什么好处？
     * 1、1.7版本rehash性能低，比位运算差多了
     * 2、把原来碰撞的节点又散列了一次（非常重要，减低冲突是hash算法的毕生使命）
     */
    newTab[e.hash & (newCap - 1)] = e;
           

          ④疑问，put方法，第一个if和else为什么不合并？

           个人觉得这解析还是比较牵强，如果有其他思路请给我留言，谢谢！

/**
 * 为什么不跟下面的else合并？先判断第一个链表元素，下面else再循环遍历链表？
 * Poisson distribution（泊松分布）http://en.wikipedia.org/wiki/Poisson_distribution
 * 也可参考ConcurrentHashMap中的Overview，下面就是桶中元素个数的概率：
 *  0:    0.60653066
 *  1:    0.30326533
 *  2:    0.07581633
 *  3:    0.01263606
 *  4:    0.00157952
 *  5:    0.00015795
 *  6:    0.00001316
 *  7:    0.00000094
 *  8:    0.00000006
 * 进入此分支代码时，说明p要么是链表，要么是树形结构，按照上面的概率来说，桶中只有一个元素的概率为0.3/(1-0.61)=77.69%
 * 根据此结论，多几行代码或许能提升一点性能，还是可以接受的
 */
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);
            // binCount从0开始，所以-1，大于8个才转树结构(上面的if也需要算)
            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;
    }
}
           

           总结：虽然平时开发不用太刻意去追求一点点性能（建议不要牺牲可读性去追求一点点性能），但是这些思路还是很值得学习的