出于性能原因，是否总是有必要将桶的哈希数 table 设为质数？
Is it always necessary to make hash table number of buckets a prime number for performance reason?
https://www.quora.com/Why-should-the-size-of-a-hash-table-be-a-prime-number?share=1
我看到有人提到哈希的桶数 table 最好是质数。
总是这样吗？当哈希值已经均匀分布时，就不需要使用质数了吗？
https://github.com/rui314/chibicc/blob/main/hashmap.c
比如上面的hashtable代码就没有使用素数作为桶的个数
https://github.com/rui314/chibicc/blob/main/hashmap.c#L37
但是哈希值是使用 fnv_hash.
从字符串生成的
https://github.com/rui314/chibicc/blob/main/hashmap.c#L17
所以使用不一定是素数的存储桶大小是有道理的？
答案是“通常你不需要大小为质数的 table，但出于一些实现原因你可能想要这样做。”
从根本上说，散列 table 在散列代码尽可能接近均匀地随机散布时效果最佳。这可以防止项目聚集在 table 中的任何一个位置。在某种程度上，只要您有足够好的哈希函数来实现这一点，table 的大小并不重要。
那么为什么人们说要选择大小为质数的 tables 呢？这有两个主要原因，它们是由于所有哈希 tables.
中都没有出现的特定情况造成的
您有时会看到质数大小的 table 的一个原因是由于构建哈希函数的特定方式。您可以通过选择 h(x) = (ax + b) mod p 形式的函数来构建合理的哈希函数，其中 a 是 {1, 2, ..., p-1} 和 b 中的数字是{0, 1, 2, ..., p-1}中的一个数，假设p是素数。如果 p 不是质数，这种形式的散列函数不会均匀地散布项目。因此，如果您使用像这样的散列函数，那么选择大小为质数的 table 是有意义的。
您看到有关质数大小 tables 的建议的第二个原因是您是否正在使用开放式寻址策略，例如二次探测或双重哈希。这些散列策略通过将项目散列到某个初始位置 k 来工作。如果该槽已满，我们查看槽 (k + r) mod T，其中 T 是 table 大小，r 是一些偏移量。如果该槽已满，我们然后检查 (k + 2r) mod T，然后 (k + 3r) mod T，等等。如果 table 大小是质数并且 r不为零，这有一个很好的、令人满意的 属性，即这些索引将循环遍历 table 中的所有不同位置而不会重复，确保项目很好地分布在 table 中.对于非素数 table 大小，此策略可能会在少量插槽中循环卡住，这会降低位置的灵活性，并可能导致插入在 table 填满之前就失败。
所以假设您没有使用双重哈希或二次探测，并且假设您有足够强大的哈希函数，请随意调整 table 的大小。
templatetypedef 一如既往地有一些优点 - 只是添加了更多的例子......
Is it always necessary to make hash table number of buckets a prime number for performance reason?
没有。首先，使用质数进行桶计数往往意味着您需要花费更多 CPU 周期来 fold/mod 哈希值 return 通过哈希函数计算到当前桶计数中。一种流行的替代方法是使用 2 的幂来计算桶计数（例如 8、16、32、64 ... 当您调整大小时），因为这样您就可以执行按位 AND 操作以从哈希值映射到 1 中的桶CPU 循环。 回答了您的 “所以使用不一定是质数的存储桶大小是有道理的？”
调整哈希 table 以提高性能通常意味着权衡更强的哈希函数的成本和 mod 质数与更高冲突的成本。
当哈希函数无法为其输入的键生成非常好的分布时，素数桶计数通常有助于减少冲突。
例如，如果您使用标识哈希对一堆指向 64 位 double 的指针进行哈希处理（基本上，将指针地址转换为 size_t），则哈希值将都是 8 的倍数（由于对齐），如果你有一个散列 table 大小，比如 1024 或 2048（2 的幂），那么你所有的指针都会散列到桶索引的 1/8（特别是，桶 0、8、16、25、32 等）。对于素数的桶，至少指针值——如果负载因子很高，它不可避免地分布在比桶索引范围大得多的范围内——倾向于环绕哈希 table 命中不同的索引.
当您使用非常强大的哈希函数时 - 其中低阶位实际上是随机的但重复table，无论桶数如何，您都已经在桶之间获得了良好的分布。还有一些时候，即使哈希函数非常弱——比如身份哈希——h(x) == x——密钥中的所有位都是随机的，以至于它们产生的分布与加密哈希可以产生的分布一样好，所以没有点在更强的哈希上花费额外的时间 - 这甚至可能会增加冲突。
有时分布本身并不是很好，但您可以负担得起使用额外的内存来保持较低的负载因子，因此不值得使用质数或更好的哈希函数。尽管如此，额外的存储桶也会给 CPU 缓存带来更多压力 - 因此事情最终可能比预期的要慢。
其他时候，具有身份散列的键具有落入不同桶的固有趋势（例如，因为它们可能是由递增计数器生成的，即使某些值不再使用）。在那种情况下，强大的哈希函数会增加冲突并恶化 CPU 缓存访问模式。无论您使用 2 的幂还是素数桶计数在这里都没有什么区别。
When the hash values are already evenly distributed, there is no need to use prime numbers then?
如果您在 mod-to-current-hash-table-size 操作之后谈论散列值，那句话是平凡的，但有点毫无意义：那里的均匀分布直接相关很少发生碰撞。
如果您谈论的是哈希值均匀分布在哈希函数 return 中的更有趣的情况，请键入值 space（例如 64 位整数），在这些值之前 modded 到当前散列 table 桶计数是什么，然后直到素数有帮助的空间，但只有当散列键 space 比散列桶索引的范围更大时。上面的指针示例说明：如果你说 800 个不同的 8 字节对齐指针进入 ~1000 桶，那么数字最低指针和较高地址之间的差异至少为 799 * 8 = 6392 ...你在 table 周围环绕超过 6 次 至少 （对于尽可能接近的指针），质数桶会增加每个桶的几率“包装”modding 到以前未使用的桶中。
请注意，上述对素数桶计数的一些好处适用于任何类型的冲突处理 - 分离链接、线性探测、二次探测、双重哈希、布谷鸟哈希、罗宾汉哈希等。
https://www.quora.com/Why-should-the-size-of-a-hash-table-be-a-prime-number?share=1
我看到有人提到哈希的桶数 table 最好是质数。
总是这样吗？当哈希值已经均匀分布时，就不需要使用质数了吗？
https://github.com/rui314/chibicc/blob/main/hashmap.c
比如上面的hashtable代码就没有使用素数作为桶的个数
https://github.com/rui314/chibicc/blob/main/hashmap.c#L37
但是哈希值是使用 fnv_hash.
https://github.com/rui314/chibicc/blob/main/hashmap.c#L17
所以使用不一定是素数的存储桶大小是有道理的？
答案是“通常你不需要大小为质数的 table，但出于一些实现原因你可能想要这样做。”
从根本上说，散列 table 在散列代码尽可能接近均匀地随机散布时效果最佳。这可以防止项目聚集在 table 中的任何一个位置。在某种程度上，只要您有足够好的哈希函数来实现这一点，table 的大小并不重要。
那么为什么人们说要选择大小为质数的 tables 呢？这有两个主要原因，它们是由于所有哈希 tables.
中都没有出现的特定情况造成的您有时会看到质数大小的 table 的一个原因是由于构建哈希函数的特定方式。您可以通过选择 h(x) = (ax + b) mod p 形式的函数来构建合理的哈希函数，其中 a 是 {1, 2, ..., p-1} 和 b 中的数字是{0, 1, 2, ..., p-1}中的一个数，假设p是素数。如果 p 不是质数，这种形式的散列函数不会均匀地散布项目。因此，如果您使用像这样的散列函数，那么选择大小为质数的 table 是有意义的。
您看到有关质数大小 tables 的建议的第二个原因是您是否正在使用开放式寻址策略，例如二次探测或双重哈希。这些散列策略通过将项目散列到某个初始位置 k 来工作。如果该槽已满，我们查看槽 (k + r) mod T，其中 T 是 table 大小，r 是一些偏移量。如果该槽已满，我们然后检查 (k + 2r) mod T，然后 (k + 3r) mod T，等等。如果 table 大小是质数并且 r不为零，这有一个很好的、令人满意的 属性，即这些索引将循环遍历 table 中的所有不同位置而不会重复，确保项目很好地分布在 table 中.对于非素数 table 大小，此策略可能会在少量插槽中循环卡住，这会降低位置的灵活性，并可能导致插入在 table 填满之前就失败。
所以假设您没有使用双重哈希或二次探测，并且假设您有足够强大的哈希函数，请随意调整 table 的大小。
templatetypedef 一如既往地有一些优点 - 只是添加了更多的例子......
Is it always necessary to make hash table number of buckets a prime number for performance reason?
没有。首先，使用质数进行桶计数往往意味着您需要花费更多 CPU 周期来 fold/mod 哈希值 return 通过哈希函数计算到当前桶计数中。一种流行的替代方法是使用 2 的幂来计算桶计数（例如 8、16、32、64 ... 当您调整大小时），因为这样您就可以执行按位 AND 操作以从哈希值映射到 1 中的桶CPU 循环。 回答了您的 “所以使用不一定是质数的存储桶大小是有道理的？”
调整哈希 table 以提高性能通常意味着权衡更强的哈希函数的成本和 mod 质数与更高冲突的成本。
当哈希函数无法为其输入的键生成非常好的分布时，素数桶计数通常有助于减少冲突。
例如，如果您使用标识哈希对一堆指向 64 位 double 的指针进行哈希处理（基本上，将指针地址转换为 size_t），则哈希值将都是 8 的倍数（由于对齐），如果你有一个散列 table 大小，比如 1024 或 2048（2 的幂），那么你所有的指针都会散列到桶索引的 1/8（特别是，桶 0、8、16、25、32 等）。对于素数的桶，至少指针值——如果负载因子很高，它不可避免地分布在比桶索引范围大得多的范围内——倾向于环绕哈希 table 命中不同的索引.
当您使用非常强大的哈希函数时 - 其中低阶位实际上是随机的但重复table，无论桶数如何，您都已经在桶之间获得了良好的分布。还有一些时候，即使哈希函数非常弱——比如身份哈希——h(x) == x——密钥中的所有位都是随机的，以至于它们产生的分布与加密哈希可以产生的分布一样好，所以没有点在更强的哈希上花费额外的时间 - 这甚至可能会增加冲突。
有时分布本身并不是很好，但您可以负担得起使用额外的内存来保持较低的负载因子，因此不值得使用质数或更好的哈希函数。尽管如此，额外的存储桶也会给 CPU 缓存带来更多压力 - 因此事情最终可能比预期的要慢。
其他时候，具有身份散列的键具有落入不同桶的固有趋势（例如，因为它们可能是由递增计数器生成的，即使某些值不再使用）。在那种情况下，强大的哈希函数会增加冲突并恶化 CPU 缓存访问模式。无论您使用 2 的幂还是素数桶计数在这里都没有什么区别。
When the hash values are already evenly distributed, there is no need to use prime numbers then?
如果您在 mod-to-current-hash-table-size 操作之后谈论散列值，那句话是平凡的，但有点毫无意义：那里的均匀分布直接相关很少发生碰撞。
如果您谈论的是哈希值均匀分布在哈希函数 return 中的更有趣的情况，请键入值 space（例如 64 位整数），在这些值之前 modded 到当前散列 table 桶计数是什么，然后直到素数有帮助的空间，但只有当散列键 space 比散列桶索引的范围更大时。上面的指针示例说明：如果你说 800 个不同的 8 字节对齐指针进入 ~1000 桶，那么数字最低指针和较高地址之间的差异至少为 799 * 8 = 6392 ...你在 table 周围环绕超过 6 次 至少 （对于尽可能接近的指针），质数桶会增加每个桶的几率“包装”modding 到以前未使用的桶中。
请注意，上述对素数桶计数的一些好处适用于任何类型的冲突处理 - 分离链接、线性探测、二次探测、双重哈希、布谷鸟哈希、罗宾汉哈希等。