文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

HashMap加载因子为什么是0.75?转化红黑树阈值为8?

2024-12-24 16:22

关注

正文

加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度,它衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。

 

对于使用链表法的散列表来说,查找一个元素的平均时间是 O(1+a)。因此如果负载因子越大,对空间的利用更充分,然而后果是查找效率的降低;如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费。

如果你看过源代码,你会发现在初始条件下,HashMap 在时间和空间两者间折中选择了 0.75

  1.  
  2.  
  3. static final float DEFAULT_LOAD_FACTOR = 0.75f; 

但是为什么一定是 0.75?而不是 0.8,0.6,这里有一个非常重要的概念:泊松分布。

相信大家都学过概率论,对这个大名鼎鼎的定律感觉应该是既熟悉又陌生。本篇文章的重点不是为大家普及概率论知识,这里就简单介绍下。

泊松分布是最重要的离散分布之一,它多出现在当X表示在一定的时间或空间内出现的事件个数这种场合。

 

举个简单的例子,假如你一个老板,新开张了一家酒店,这个时候应该如何准备一天所用的食材呢?

准备的太多,最后卖不掉这么多菜只能浪费扔掉;准备不够,又接不了生意。但是你有很多同行和朋友,他们会告诉你很多经验。

比如把一天分成几个时间段,上午、下午、晚上每个时间段大概会来多少个客人,每一桌大概会点几个菜。综合下来,就可以大致知道在一天的时间内,估计出需要准备的食材数量。

我们接下来看看 HashMap 源码注释的原话:

Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution 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(-0.5) * pow(0.5, k) /factorial(k)).

0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952

5: 0.0001579

6: 0.00001316

7: 0.00000094

8: 0.00000006    

more: less than 1 in ten million

翻译过来说的是,在理想情况下,使用随机哈希码,节点出现的频率在 hash 桶中遵循泊松分布。

对照桶中元素个数和概率的表,可以看到当用 0.75 作为加载因子时,桶中元素到达 8 个的时候,概率已经变得非常小,因此每个碰撞位置的链表长度超过 8 个是几乎不可能的,因此在链表节点到达 8 时才开始转化为红黑树。

本文转载自微信公众号「程序员大帝」,可以通过以下二维码关注。转载本文请联系程序员大帝公众号。

 

来源:程序员大帝内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯