HashMap中数组的长度为什么要设计成2次幂?

了解本文的前提是你必须对数据结构有一定的了解,明白各数据结构的优势及弊端。当然如果你已经知道了HashMap底层的数据结构是数组+链表+红黑树那就更好了。如果你还知道hashMap默认初始化的数组长度是16,且每次扩容都扩容为原长度的两倍,那么我只能说“你已经是一个合格的大佬了”。

我算是一个比较喜欢刨根问底的人,我相信“存在既有意义”,这通常使我收益良多,但是偶尔也容易陷入死角。OK 废话不多说,转入正题。

下面是jdk1.8中HashMap的部分源码

HashMap中数组的长度为什么要设计成2次幂?

通过源码我们可以看到,HashMap新添加的元素是通过 ((数组长度 -1) & key的hashCode) 取模运算来计算槽位的(也就是新元素需要放在数组的哪个下标位置)

ps:取模运算这里就不做说明了,想要了解的小伙伴可以自行baidu

下面这个程序简单的模拟了,当数组长度分别为15、16时,添加100个元素所计算出的下标位置。这100个元素对应的hashcode分别从0-100递增

public static void main(String[] args) {
            int[] length={15,16};
            for(int n : length){
                System.out.println("--------------"+n+"-----------------");
                for(int hash=0;hash<=100;hash++){
                    System.out.print((hash & n-1)+"/t");
                }
                System.out.println();
            }  
  }
复制代码

执行结果如下

HashMap中数组的长度为什么要设计成2次幂?

可以看出当数组的长度为16时,计算出了16个槽位并且均匀分布在数组的每一个位置,当数组长度为15时,只计算出了8个槽位,每个槽位放了一个两个节点的链表,导致了有8个槽位是空闲状态。这个问题一般被称为hash冲突,hash冲突会导致HashMap查询效率低下。我们从map中取数据时,本来可以直接通过key计算出的槽位取出对应元素就可以了,现在因为这个槽位存放的是一个链表,那么想要取数据还得遍历这个链表,在非常极端的情况下(所有元素的hashcode都是相同的),HashMap将会退化成一个链表。这样就失去了数组随机查找效率高的这样一个特性。

因此让数组的长度等于二次幂可以有效的减少hash冲突的概率。

HashMap还有许多的特性,感兴趣的话可以参考JDK自己手写一个HashMap。 ps:1.7的HashMap比较简单,如果要研究HashMap源码的话建议可以先从jdk1.7入手

最后附上之前自己实现的一个简单的HashMap blog.csdn.net/qq_39914581…

原文 

https://juejin.im/post/5e970f8d518825739837c70b

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » HashMap中数组的长度为什么要设计成2次幂?

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址