哈希表：为什么大小应该是素数？

可能重复：
Why should hash functions use a prime number modulus?哈希表：为什么大小应该是素数？

为什么需要一个哈希表的（数据结构）的大小是素？

从我的理解，它确保更均匀的分布，但是有没有其他原因？

2010-10-20 Olivier Lalonde

这是[为什么应该使用哈希函数使用素数模数？]的副本（http://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus ） - 边栏“相关”部分的第一个链接 - 我认为[接受的答案]（http://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-数字模数/ 1147232＃1147232）非常好。 – 2010-10-20 22:34:00

您应该接受答案。 – gwg 2017-10-17 01:18:13

唯一的原因是避免将值聚类到少数桶（是，分布）。更均匀的分布式哈希表将更加一致地执行。

从http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html

如果假设你的hashCode函数导致以下哈希码等等{X，2倍，3倍，4倍，5倍，6倍...}，那么所有这些都将在要群集只有m个桶，其中m = table_length/GreatestCommonFactor（table_length，x）。（这是微不足道的验证/派生这个）。现在你可以做下列操作之一，以避免集群

确保您不会产生太多的哈希码是像{X，2倍，3倍，4倍，5倍，6倍的另一个的hashCode的倍数。 ..}但是如果你的hashTable应该有数以百万计的条目，这可能会有点困难。

或者通过使GreatestCommonFactor（table_length，x）等于1，即通过使table_length与x互质，简单地使m等于table_length。如果x可以是任何数字，那么请确保table_length是一个素数。

来源

2010-10-20 17:02:24

比我想我的理解是正确的：避免群集<=>获得更好的分布。对？感谢您的参考。 – 2010-10-20 17:07:05

@Olivier Lalonde，如果这回答你的问题，请将其标记为答案。 – 2011-01-29 20:34:49

-5

无论散列函数你用你得到一个整数。为了将它映射到散列表，通常你需要使用散列表的大小的整数来使该值小于表的大小以便映射它。

回报hashVal％tableSize

我有点从这时开始，但IIRC如果tableSize甚至，所有参赛作品将甚至丧失。你的一半散列表将永远不会被填充。

来源

2010-10-20 17:04:33 Afwas

这是另一个好点。我相信主要的原因是它减少了hashVal中可能导致不均匀分布的模式（例如10,20,30,40，如果tableSize = 10，将全部给出0）的风险，就像@Sam提到的那样。 – 2010-10-20 17:13:29

347％20是7，这不是偶数。 – 2010-10-20 17:54:32

哈希表：为什么大小应该是素数？

回答

相关问题