HashMap的算法解析及高并发下死循环分析

最新推荐文章于 2023-12-16 11:07:59 发布

codingtu

最新推荐文章于 2023-12-16 11:07:59 发布

阅读量3k

点赞数

分类专栏：算法文章标签： HashMap 数据结构算法

本文链接：https://blog.csdn.net/codingtu/article/details/84846220

版权

本文分析HashMap的长度设置原因，JDK1.8与1.7的实现区别，尤其是为何长度设为2的n次方。在高并发环境中，JDK1.7可能出现死循环问题，而JDK1.8通过改进解决了这一问题，避免了链表循环导致的性能问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

HashMap是一个以空间换时间，内部以数组+链表\红黑树实现的散列表。HashMap的具体原理我们不做深入仔细分析，这类文章网上较多，且HashMap在面试中命中率极高。本文以jdk1.8为例，只分析里面我认为值得拿出来分析的有关数据结构和算法的部分来讲解。

HashMap的长度

JDK1.8实现

HashMap的初始默认长度是16.HashMap在jdk1.8上做了一层优化，创建时并没有创建Node数组，只有首次put元素的时候才创建。但是我们在创建时也可以指定数组的长度，HashMap会将长度重新转化为2的n次方。具体为什么是2的n次方，后面再分析。

初始长度源码及案例分析

//java.util.HashMap#tableSizeFor
/**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

这里主要运用了位或操作和无符号右移操作。
位或操作：两个位都为0时，结果才为0
无符号右移：不论正负,高位均补0.可参考博客有符号右移>>，无符号右移>>>
tableSizeFor方法很简单，但是却充分用到了我们大一学到的大学计算机基础内容，主要是位运算和移位运算符，关于其他的可自行扩展（如左移( << )、右移( >> ) 、无符号右移( >>> ) 、位与( & ) 、位或( | )、位非( ~ )、位异或( ^ )）。
首先cap为我们传入的想要初始化数组的值，这里会对cap进行一个减一的操作，然后依次进行无符号右移和或运算。现假定我们传入默认长度16.

static final int tableSizeFor(int cap) {
        //cap:10000
        //n:1111
        int n = cap - 1;
        //n >>> 1:111   1111|111:1111

最低0.47元/天解锁文章