面试官:为什么 HashMap 的加载因子是0.75?
码农突围
共 1174字,需浏览 3分钟
· 2020-08-05
点击上方“码农突围”,马上关注
这里是码农充电第一站,回复“666”,获取一份专属大礼包
真爱,请设置“星标”或点个“在看”
为什么HashMap需要加载因子? 解决冲突有什么方法? 为什么加载因子一定是0.75?而不是0.8,0.6?
为什么HashMap需要加载因子?
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// AbstractMap
public int hashCode() {
int h = 0;
Iterator> i = entrySet().iterator();
while (i.hasNext())
h += i.next().hashCode();
return h;
}
加载因子 = 填入表中的元素个数 / 散列表的长度
散列函数是否可以将哈希表中的数据均匀地散列? 怎么处理冲突? 哈希表的加载因子怎么选择?
解决冲突有什么方法?
1. 开放定址法
Hi = (H(key) + di) MOD m,其中i=1,2,…,k(k<=m-1)
1.1 线性探查法(Linear Probing):di = 1,2,3,…,m-1
1.2 平方探测法(Quadratic Probing):di = ±12, ±22,±32,…,±k2(k≤m/2)
1.3 伪随机探测法:di = 伪随机数序列
这种方法建立起来的哈希表,当冲突多的时候数据容易堆集在一起,这时候对查找不友好; 删除结点的时候不能简单将结点的空间置空,否则将截断在它填入散列表之后的同义词结点查找路径。因此如果要删除结点,只能在被删结点上添加删除标记,而不能真正删除结点; 如果哈希表的空间已经满了,还需要建立一个溢出表,来存入多出来的元素。
2. 再哈希法
Hi = RHi(key), 其中i=1,2,…,k
3. 建立一个公共溢出区
4. 链地址法(拉链法)
处理冲突的方式简单,且无堆集现象,非同义词绝不会发生冲突,因此平均查找长度较短; 由于拉链法中各链表上的结点空间是动态申请的,所以它更适合造表前无法确定表长的情况; 删除结点操作易于实现,只要简单地删除链表上的相应的结点即可。
为什么HashMap加载因子一定是0.75?而不是0.8,0.6?
临界值 = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR
* Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/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)). 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
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
那么为什么不可以是0.8或者0.6呢?
对于开放定址法,加载因子是特别重要因素,应严格限制在0.7-0.8以下。超过0.8,查表时的CPU缓存不命中(cache missing)按照指数曲线上升。因此,一些采用开放定址法的hash库,如Java的系统库限制了加载因子为0.75,超过此值将resize散列表。
参考资料
泊松分布和指数分布:10分钟教程: http://www.ruanyifeng.com/blog/2015/06/poisson-distribution.html
---END--- 重磅!码农突围-技术交流群已成立 扫码可添加码农突围助手,可申请加入码农突围大群和细分方向群,细分方向已涵盖:Java、Python、机器学习、大数据、人工智能等群。 一定要备注:开发方向+地点+学校/公司+昵称(如Java开发+上海+拼夕夕+猴子),根据格式备注,可更快被通过且邀请进群 ▲长按加群 推荐阅读
• 那个从深圳流水线工人去Google上班程序媛,最近失业了! • 这款网络排查工具,堪称神器! • 面试官扎心一问:数据量很大,分页查询很慢,有什么优化方案? • 太牛了!华中科技大学学霸,201万顶薪签约华为,成今年顶薪加入第一人! 网友:我酸了,一辈子的都到达不了 • Java 里的 for (;;) 与 while (true),哪个更快? • 三年,我从语文老师到支付宝技术前端的蜕变 最近面试BAT,整理一份面试资料《Java面试BAT通关手册》,覆盖了Java核心技术、JVM、Java并发、SSM、微服务、数据库、数据结构等等。 获取方式:点“在看”,关注公众号并回复 BAT 领取,更多内容陆续奉上。 如有收获,点个在看,诚挚感谢明天见(。・ω・。)ノ♡
评论
金融研究 | 使用Python测量关键审计事项的「信息含量」
Tips: 公众号推送后内容只能更改一次,且只能改20字符。如果内容出问题,或者想更新内容, 只能重复推送。为了更好的阅读体验,建议阅读本文博客版, 链接地址https://textdata.cn/blog/2023-01-13-information-content-of-critical-aud
大邓和他的Python
0
我看阿里的年终奖总算发了!
到4月底了,这两天看朋友圈,发现阿里的年终奖终于发了,问了问老同学,也从网上检索了不少信息,基本搞清楚了阿里今年的年终奖情况。近来来阿里一些集团对绩效等级做了较大的调整,以前的旧绩效系统中,绩效分为3.25、3.5、3.75、4和5五个等级,其中4和5是较高绩效等级,较少见。而且之前3.5绩效内部划
公子龙
0
金融研究(更新) | 使用Python构建关键审计事项的「信息含量」
Tips: 公众号推送后内容只能更改一次,且只能改20字符。如果内容出问题,或者想更新内容, 只能重复推送。为了更好的阅读体验,建议阅读本文博客版, 链接地址https://textdata.cn/blog/2023-01-13-information-content-of-critical-aud
大邓和他的Python
0
盘点Lombok的几个骚操作,你绝对没用过!
👉 欢迎加入小哈的星球 ,你将获得: 专属的项目实战 / Java 学习路线 / 一对一提问 / 学习打卡 / 赠书福利全栈前后端分离博客项目 2.0 版本完结啦, 演示链接:http://116.62.199.48/ ,新项目正在酝酿中
小哈学Java
0
堪称最优秀的Docker可视化管理工具——Portainer你真的会用吗?
来源:blog.csdn.net/shark_chili3007/article/details/123366179👉 欢迎加入小哈的星球 ,你将获得: 专属的项目实战 / Java 学习路线 / 一对一提问 / 学习打卡 / 赠书福利全栈前后端分离博客项目
小哈学Java
0
周鸿祎是真牛逼
最近在各个视频平台,我的推荐信息流上一定会出现红衣教主周鸿祎的身影,俨然是新一代的顶流IP网红,还是自己贼有钱的那种。不得不说,周鸿祎是真牛逼,他是懂得学习的。年初的时候,他就发文:“如今已是网红时代,我现在已经拜了俞敏洪为师,在学习如何当网红,每天勤奋的发短视频”。“有时候也在劝很多亚布力大哥级
公子龙
1
Apache Paimon毕业,湖仓架构的未来发展趋势!
北京时间 2024 年 4 月 16日,开源软件基金会 Apache Software Foundation(以下简称 ASF)正式宣布 Apache Paimon 毕业成为 Apache 顶级项目(TLP, Top Level Project)。经过社区的共同努力和持续创新,Apache Paim
程序源代码
0
JS的这些新特性,你都用过么?
大厂技术 高级前端 Node进阶点击上方 程序员成长指北,关注公众号回复1,加入高级Node交流群作为一门不断演进的语言,JavaScript每年都会引入新特性。这些特性的加入,能够帮助我们编写更加简洁、高效、易于维护的代码。然而,并非所有新特性
程序员成长指北
1