专栏首页JavaQHashMap扩容拾遗

HashMap扩容拾遗

JDK8中HashMap扩容涉及到的加载因子和链表转红黑树的知识点经常被作为面试问答题,本篇将对这两个知识点进行小结。

链表转红黑树为什么选择数字8

在JDK8及以后的版本中,HashMap引入了红黑树结构,其底层的数据结构变成了数组+链表或数组+红黑树。添加元素时,若桶中链表个数超过8,链表会转换成红黑树。之前有写过篇幅分析选择数字8的原因,内容不够严谨。最近重新翻了一下HashMap的源码,发现其源码中有这样一段注释:

Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFYTHRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poissondistribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-pow(0.5, k) / factorial(k)). The first values are: 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 more: less than 1 in ten million

翻译过来大概的意思是:理想情况下使用随机的哈希码,容器中节点分布在hash桶中的频率遵循泊松分布(具体可以查看http://en.wikipedia.org/wiki/Poisson_distribution),按照泊松分布的计算公式计算出了桶中元素个数和概率的对照表,可以看到链表中元素个数为8时的概率已经非常小,再多的就更少了,所以原作者在选择链表元素个数时选择了8,是根据概率统计而选择的。

默认加载因子为什么选择0.75

HashMap有两个参数影响其性能:初始容量和加载因子。容量是哈希表中桶的数量,初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动扩容之前可以达到多满的一种度量。当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行扩容、rehash操作(即重建内部数据结构),扩容后的哈希表将具有两倍的原容量。

通常,加载因子需要在时间和空间成本上寻求一种折衷。加载因子过高,例如为1,虽然减少了空间开销,提高了空间利用率,但同时也增加了查询时间成本;加载因子过低,例如0.5,虽然可以减少查询时间成本,但是空间利用率很低,同时提高了rehash操作的次数。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地减少rehash操作次数,所以,一般在使用HashMap时建议根据预估值设置初始容量,减少扩容操作。

选择0.75作为默认的加载因子,完全是时间和空间成本上寻求的一种折衷选择,至于为什么不选择0.5或0.8,笔者没有找到官方的直接说明,在HashMap的源码注释中也只是说是一种折中的选择。

END

本文分享自微信公众号 - JavaQ(Java-Q),作者:wind瑞

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-04-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 我的2016年书单

    相对于电子书,我更喜欢纸质版的书籍。我喜欢在拿到新书时记录购买时间、地点、开始阅读的时间、第一次看完的时间,算是一种学习的记录。过去的2016年一共阅读过15本...

    JavaQ
  • 编写高质量代码开篇

    最近因为加入一个新的团队,才开始认真的关注关于编写高质量代码的话题,学习总结的同时,记录下这段让自己再一次认真学习的过程。 想成为架...

    JavaQ
  • 开发环境利器vagrant

    引言 团队合作的编码过程中,有时会因为个人开发环境的不同,而出现“代码在我的机器上运行没问题,在别人的机器上有问题”的情况。团队有新人加入时,需要为准备开发环境...

    JavaQ
  • mysql 大小写敏感的一个解决方案

         今天,有同事告诉我,我们游戏登陆的时候,账号和密码没有区分大小写,后来又发现创建账号和角色也没有区分大小写。思考登陆流程之后,应该是Mysql没有区分...

    帘卷西风
  • 从“挖光缆”到“剪网线”|蚂蚁金服异地多活的微服务体系

    本文介绍了蚂蚁金服异地多活单元化架构的原理,以及微服务体系在此架构下的关键技术实现。

    数据和云
  • iOS学习巩固笔记-Socket

    2016-05-0922:18:41 发表评论 665℃热度 下面是一些个人学习笔记,查缺补漏,巩固知识,希望大家能有所收获。 ? Socket又称"套接字”...

    timhbw
  • 2016年终总结

    最近看到大家都在写总结,觉得不写点什么记录下2016着实有点不踏实,其实执笔这回事对我们这些程序猿来说真是简直了,行了废话不多说了,以下是一些个人总结: 学到的...

    用户1141560
  • 现身说法:37岁老码农找工作

    https://www.cnblogs.com/freeflying/p/9950374.html

    纯洁的微笑
  • 现身说法:37岁老码农找工作

    他说他们部门调整,虽然最后他留了下来,但还是非常焦虑。人无远虑必有近忧,他这次被刺激到了,想提高一下自己,以免下次再有类似的心惊肉跳。但怎么提高呢?

    三哥
  • 现身说法:37岁老码农找工作

    他说他们部门调整,虽然最后他留了下来,但还是非常焦虑。人无远虑必有近忧,他这次被刺激到了,想提高一下自己,以免下次再有类似的心惊肉跳。但怎么提高呢?

    Java技术栈

扫码关注云+社区

领取腾讯云代金券