HashTable：超大规模数据下哈希表容量与哈希函数选型咨询

1. 10^9量级数据下的哈希表容量怎么定？ #

• 别直接跟输入规模对齐，也不能乱缩小，核心是在内存开销和查询效率之间找平衡：
  • 哈希表的性能核心看负载因子（元素总数/哈希表容量），行业默认的安全线是0.7~0.8——超过这个值，哈希冲突会暴增，原本O(1)的查询会退化到O(n)；低于这个值，纯纯浪费内存。
  • 10^{9量级的数据集，要是把容量设成10}9，内存直接炸锅（比如每个哈希条目占16字节，就得16GB以上），绝大多数场景根本扛不住。
  • 正确思路：先算你能拿多少内存存哈希表，再反推容量。比如你有8GB内存，每个条目16字节，最多能装5e8个元素，那容量就得设成5e8 / 0.7 ≈ 7.1e8，既控住内存，又保证负载因子在安全区。
  • 要是内存实在不够，就考虑分段哈希或者磁盘哈希（比如LevelDB的思路），但先把负载因子的红线守住再说。

2. 10^6范围的键怎么哈希成更小的值？ #

• 用取模的话，核心就是让哈希值尽量散，少冲突，取模的数要这么选：
  • 优先选质数：比如键范围是1~1e6，哈希表容量设成99991（接近1e5的质数），用key % 99991就能让哈希分布更均匀——要是选合数，碰到键有固定周期（比如全是偶数），哈希值会扎堆。
  • 要是选2的幂（比如131072），别直接取模：直接取模2的幂等于拿键的低N位，要是键的低位分布不均（比如都是100的倍数），冲突会炸。这时候先给键做个扰动，比如(key * 1234567) % 131072，用乘法打乱低位再取模。
  • 记住：取模的数必须≤哈希表容量，不然哈希值会超出数组下标范围，白忙活。本质是把键映射到哈希表的下标空间里，最终哈希值得落在[0, 容量-1]里。

对你尝试的做法的点评 #

你把容量设成输入规模的75%，用key%X生成哈希码，这做法不对：

• 首先，负载因子=输入规模/X≈1.33，远超0.7的安全线，冲突会多到离谱，哈希表性能直接拉胯，说不定比遍历还慢。
• 其次，要是X不是质数也没做扰动，key%X的哈希分布会很差，雪上加霜。

内容的提问来源于stack exchange，提问作者stoogie