小编典典

为什么散列表的大小127(素数)比128好?

algorithm

假设简单的统一哈希,就是说,任何给定的值都同样希望哈希到哈希的任何插槽中。为什么最好使用大小为127而不是128的表?我真的不明白2的幂的问题是什么。或它到底有什么不同。

使用除法时,我们通常避免使用某些m值(表大小)。例如,m不应该是2的幂,因为如果m = 2 ^ p,则h(k)只是k的p个最低位。

假设可能的元素仅在1到10000之间,并且我选择表大小为128。127怎么会更好?所以128是2 ^
6(1000000),而127是0111111。这有什么区别?所有数字(经过散列处理)仍然仍然是127的k的p个最低位。我弄错了吗?

我正在寻找一些示例,因为我真的不明白为什么这样不好。在此先多谢!


阅读 719

收藏
2020-07-28

共1个答案

小编典典

所有数字(经过散列处理)仍然仍然是127的k的p个最低位。

那是错误的(或者我误会了..)。k % 127取决于k的所有位。k % 128仅取决于最低的7位。


编辑:

如果您的理想分布在1到10,000之间。10,000 % 12710,000 % 128两者都将在一个优秀的小分布开启此。所有存储桶将包含10,000 / 128 = 78(或79)个项目。

如果您的分布在1到10,000之间是有偏差的,因为{x,2x,3x,..}发生的频率更高。然后,如该答案中所述,素数大小将提供更好得多的分布。(除非x恰好是该素数。)

因此, 如果 低位的分布足够好,则切断高位(使用大小为128)就没有问题。但是,使用真实数据和错误设计的真实哈希函数,您将需要这些高位。

2020-07-28