为什么HashTable的初始化因子是11，HashMap却是16

灰太狼 2024-05-01 16:04 60阅读 0赞

关于HashTable和HashMap的不同点这里就不再说明，网上很多；

今天突然对这个初始化因子不通的问题有了兴趣，以前只知道不一样，从没想过为什么不一样，然后查了半天，感觉相关文章说的很少，想自己来记录一下

关于HashTable和HashMap，最重要的不过是hash了，而hash的目的就是为了尽可能的减少寻址冲突，下面边看源码变分析（1.8）

1.HashTable

![f7e189bd2bd746609ff70d517793d090.png][]

使用外部对象key的hashCode()方法，经过和数组大小取模获取下标。

那么这里为什么用11，而不是用16呢（HashMap的是16）？

网上有不少说的论证是如下图（[【集合我能讲两小时028】为什么hashtable的扩容方式选择为2n+1？\_檀越剑指大厂的博客-CSDN博客\_hashtable扩容为什么是2n+1为什么hashtable的扩容方式选择为2n+1？为了均匀分布，降低冲突率。首先，Hashtable的初始容量为11。Index的计算方式为： int index = (hash & 0x7FFFFFFF) % tab.length;常用的hash函数是选一个数m取模（余数），这个数在课本中推荐m是素数，但是经常见到选择m=2n，因为对2n求余数更快，并认为在key分布均匀的情况下，key%m也是在\[0,m-1\]区间均匀分布的。但实际上，key%m的分布同m是有关的。证明如下：key%m![favicon32.ico][]https://blog.csdn.net/qyj19920704/article/details/123322666?utm\_medium=distribute.pc\_aggpage\_search\_result.none-task-blog-2~aggregatepage~first\_rank\_ecpm\_v1~rank\_v31\_ecpm-1-123322666-null-null.pc\_agg\_new\_rank&utm\_term=hashtable%E4%B8%BA%E4%BB%80%E4%B9%88%E9%BB%98%E8%AE%A4%E4%B8%BA11&spm=1000.2123.3001.4430][028_hashtable_2n_1_-CSDN_hashtable_2n_1_hashtable_2n_1_Hashtable_11_Index_ int index _ _hash _ 0x7FFFFFFF_ _ tab.length_hash_m_m_m_2n_2n_key_key_m_0_m-1_key_m_m_key_m_favicon32.ico_https_blog.csdn.net_qyj19920704_article_details_123322666_utm_medium_distribute.pc_aggpage_search_result.none-task-blog-2_aggregatepage_first_rank_ecpm_v1_rank_v31_ecpm-1-123322666-null-null.pc_agg_new_rank_utm_term_hashtable_E4_B8_BA_E4_BB_80_E4_B9_88_E9_BB_98_E8_AE_A4_E4_B8_BA11_spm_1000.2123.3001.4430]）

![ecb1df6da5cd4b86b3120923128a6e08.png][]

中间的证明，我不是很认可，因为他举例的是和 m有公约数的key，用一定条件的key来举证在所有m的位置不均匀本身就是断章取义，比如：m=9，那么公约数=3，那么key的范围只是局限于如（12、15、18、21、24、27。。），所在位置index也就是 3、6、0；但是如果key为任意数，则index的位置为 1、2、3、4、5、6、7、8、0，均匀分布；所以举证不成立；

那是不是结果就不正确呢，我认为不是，上面所说的前提的key是均匀分布的，但是实际上怎么样呢？我们知道这个key在HashTable中，是根据hashcode()方法来的，方法是属于其他对象的，并不能确定一定是均匀的，所以我们认为key不一定是均匀分布

这时候我们用一个质数（至少也是个奇数）作为桶的数量，能更大程度的减少冲突

而初始化的值也不适合过大（影响空间），所以是11

2.HashMap

HashTable是取模，HashMap却是 & ，所以只能是2的n次方（二进制都是1），这样才会尽量减少冲突，hash方法是HashMap内部的，如下

![092855ee30bd4770b989b4014f6ab9ab.png][]

把高位的变化，通过异或运算，也映射到低位，这样，在 & 的时候才能减少冲突

![a4482185f8ad44c4a39eea796ef10bb2.png][]

参考自：[language agnostic - Why should hash functions use a prime number modulus? - Stack Overflow![favicon.ico_v_ec617d715196][]https://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus][language agnostic - Why should hash functions use a prime number modulus_ - Stack Overflow_favicon.ico_v_ec617d715196_https_stackoverflow.com_questions_1145217_why-should-hash-functions-use-a-prime-number-modulus]

[f7e189bd2bd746609ff70d517793d090.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/01/a405406553e24e58ae413ef7e036cfaf.png
[favicon32.ico]: https://g.csdnimg.cn/static/logo/favicon32.ico
[028_hashtable_2n_1_-CSDN_hashtable_2n_1_hashtable_2n_1_Hashtable_11_Index_ int index _ _hash _ 0x7FFFFFFF_ _ tab.length_hash_m_m_m_2n_2n_key_key_m_0_m-1_key_m_m_key_m_favicon32.ico_https_blog.csdn.net_qyj19920704_article_details_123322666_utm_medium_distribute.pc_aggpage_search_result.none-task-blog-2_aggregatepage_first_rank_ecpm_v1_rank_v31_ecpm-1-123322666-null-null.pc_agg_new_rank_utm_term_hashtable_E4_B8_BA_E4_BB_80_E4_B9_88_E9_BB_98_E8_AE_A4_E4_B8_BA11_spm_1000.2123.3001.4430]: https://blog.csdn.net/qyj19920704/article/details/123322666?utm_medium=distribute.pc_aggpage_search_result.none-task-blog-2~aggregatepage~first_rank_ecpm_v1~rank_v31_ecpm-1-123322666-null-null.pc_agg_new_rank&utm_term=hashtable%E4%B8%BA%E4%BB%80%E4%B9%88%E9%BB%98%E8%AE%A4%E4%B8%BA11&spm=1000.2123.3001.4430
[ecb1df6da5cd4b86b3120923128a6e08.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/01/b4828a44628b48fd9611d45b0ee99ae0.png
[092855ee30bd4770b989b4014f6ab9ab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/01/5011f868379840a88bf1de798a0dce3e.png
[a4482185f8ad44c4a39eea796ef10bb2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/01/3229e6440f834272ad4e7cdc307cef16.png
[favicon.ico_v_ec617d715196]: https://cdn.sstatic.net/Sites/stackoverflow/Img/favicon.ico?v=ec617d715196
[language agnostic - Why should hash functions use a prime number modulus_ - Stack Overflow_favicon.ico_v_ec617d715196_https_stackoverflow.com_questions_1145217_why-should-hash-functions-use-a-prime-number-modulus]: https://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus