为什么散列 table 通过加倍来调整大小？
Why is the hash table resized by doubling it?
签入 java 并在线搜索哈希 table 代码示例似乎 table 的大小调整是通过将其加倍来完成的。
但是大多数教科书都说 table 的最佳大小是质数。
所以我的问题是：
加倍的做法是因为：
- 很容易实现，或者
- 寻找素数效率太低（但我认为寻找
下一个素数超过
n+=2 并使用
模是 O(loglogN) 这很便宜)
- 或者这是我的误会，只是某些hashtable变体
只需要 prime table 尺寸？
更新：
教科书中使用质数的方式是某些属性起作用所必需的（例如，二次探测需要质数大小 table 来证明，例如，如果 table 不是完整的项目 X 将被插入）。
作为重复发布的 link 通常询问有关增加任何数字的问题，例如25% 或下一个质数，接受的答案表明我们加倍以保持调整大小操作 "rare"，因此我们可以保证摊销时间。
这没有回答 table 大小为质数并使用质数调整大小甚至大于两倍的问题。所以想法是在考虑调整大小开销的情况下保持主要大小的属性
Q: But most textbooks say that the best size for the table is a prime number.
Regarding size primality:
What comes to primality of size, it depends on collision resolution algorithm your choose. Some algorithms require prime table size (double hashing, quadratic hashing), others don't, and they could benefit from table size of power of 2, because it allows very cheap modulo operations. However, when closest "available table sizes" differ in 2 times, memory usage of hash table might be unreliable. So, even using linear hashing or separate chaining, you can choose non power of 2 size. In this case, in turn, it's worth to choose particulary prime size, because:
If you pick prime table size (either because algorithm requires this, or because you are not satisfied with memory usage unreliability implied by power-of-2 size), table slot computation (modulo by table size) could be combined with hashing. See this answer for more.
The point that table size of power of 2 is undesirable when hash function distribution is bad (from the answer by Neil Coffey) is impractical, because even if you have bad hash function, avalanching it and still using power-of-2 size would be faster that switching to prime table size, because a single integral division is still slower on modern CPUs that several of multimplications and shift operations, required by good avalanching functions, e. g. from MurmurHash3.
Q: Also to be honest I got lost a bit on if you actually recommend primes or not. Seems that it depends on the hash table variant and the quality of the hash function?
散列函数的质量无关紧要，您始终可以通过 MurMur3 雪崩 "improve" 散列函数，这比从次幂切换到素数 table 大小要便宜-2 table 大小，见上。
我推荐选择prime size，用QHash或者quadratic hash算法(aren't same), only when you need precise control over hash table load factor and predictably high actual loads. With power-of-2 table size, minimum resize factor is 2, and generally we cannot guarantee the hash table will have actual load factor any higher than 0.5. See this answer.
否则，我建议使用线性探测的 2 次幂大小的哈希 table。
Q: Is the approach of doubling because:
It is easy to implement, or
基本上，在很多情况下，是的。
见 this large answer regarding load factors:
Load factor is not an essential part of hash table data structure -- it is the way to define rules of behaviour for the dymamic system (growing/shrinking hash table is a dynamic system).
Moreover, in my opinion, in 95% of modern hash table cases this way is over simplified, dynamic systems behave suboptimally.
什么是加倍？这只是最简单的调整大小策略。该策略可以任意复杂，在您的用例中以最佳方式执行。它可以考虑当前哈希 table 大小、增长强度（自上次调整大小以来完成了多少 get 操作）等。没有人禁止您实现此类自定义调整大小逻辑。
Q: Is finding a prime number too inefficient (but I think that finding the next prime going over n+=2 and testing for primality using modulo is O(loglogN) which is cheap)
预先计算一些素数哈希 table 大小的子集是一种很好的做法，以便在运行时使用二进制搜索在它们之间进行选择。看the list double hash capacities and explaination, QHash capacities. Or, even using direct lookup，就是很快。
Q: Or this is my misunderstanding and only certain hashtable variants only require prime table size?
是的，只有某些类型需要，见上文。
Java HashMap (java.util.HashMap) 在链表（或 [自 JDK8] 树中链接桶冲突，具体取决于容器的大小和溢出）。
因此，关于辅助探测功能的理论不适用。
似乎消息 'use primes sizes for hash tables' 已经脱离了多年来适用的情况...
使用 2 的幂具有将散列值减少为 table 条目的优点（如其他答案所述），可以通过位掩码实现。整数除法相对昂贵，在高性能情况下这会有所帮助。
我要观察 "redistributing the collision chains when rehashing is a cinch for tables that are a power of two going to a power of two"。
请注意，当根据哈希码的 'next' 位使用 2 的幂重新散列到大小 'splits' 的两倍时，两个桶之间的每个桶。
也就是说，如果 hash-table 有 256 个桶，因此使用哈希值的最低 8 位重新散列会根据第 9 位拆分每个冲突链，并且要么保留在同一个桶 B 中（第 9 位为 0 ) 或进入 B+256 桶（第 9 位为 1）。这种拆分可以 preserve/take 桶处理方法的优势。例如，java.util.HashMap 以插入的相反顺序对小桶进行排序，然后将它们拆分为遵循该顺序的两个子结构。它将大桶保存在按哈希码排序的二叉树中，并类似地拆分树以保留该顺序。
注意：这些技巧直到 JDK8 才实现。
（我很确定）Java.util.HashMap 只会放大（永远不会缩小）。但是，将哈希值减半-table 与将其加倍具有相似的效率。
此策略的一个 'downside' 是 Object 实施者没有明确要求确保散列码的低阶位分布良好。
一个完全有效的散列码可能在整体上分布良好，但在其低位上分布不佳。因此，一个遵守 hashCode() 通用契约的对象在 HashMap 中实际使用时可能仍然会失败！
Java.util.HashMap 通过在提供的 hashCode() 实现上应用额外的散列 'spread' 来缓解这种情况。 'spread' 真的很粗鲁（将 16 位高位与低位异或）。
对象实施者应该意识到（如果还没有意识到的话）他们的散列码中的偏差（或缺乏）会对使用散列的数据结构的性能产生重大影响。
郑重声明，我的分析基于此源副本：
http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java
签入 java 并在线搜索哈希 table 代码示例似乎 table 的大小调整是通过将其加倍来完成的。
但是大多数教科书都说 table 的最佳大小是质数。
所以我的问题是：
加倍的做法是因为：
- 很容易实现，或者
- 寻找素数效率太低（但我认为寻找
下一个素数超过
n+=2并使用 模是 O(loglogN) 这很便宜) - 或者这是我的误会，只是某些hashtable变体 只需要 prime table 尺寸？
更新：
教科书中使用质数的方式是某些属性起作用所必需的（例如，二次探测需要质数大小 table 来证明，例如，如果 table 不是完整的项目 X 将被插入）。
作为重复发布的 link 通常询问有关增加任何数字的问题，例如25% 或下一个质数，接受的答案表明我们加倍以保持调整大小操作 "rare"，因此我们可以保证摊销时间。
这没有回答 table 大小为质数并使用质数调整大小甚至大于两倍的问题。所以想法是在考虑调整大小开销的情况下保持主要大小的属性
Q: But most textbooks say that the best size for the table is a prime number.
Regarding size primality:
What comes to primality of size, it depends on collision resolution algorithm your choose. Some algorithms require prime table size (double hashing, quadratic hashing), others don't, and they could benefit from table size of power of 2, because it allows very cheap modulo operations. However, when closest "available table sizes" differ in 2 times, memory usage of hash table might be unreliable. So, even using linear hashing or separate chaining, you can choose non power of 2 size. In this case, in turn, it's worth to choose particulary prime size, because:
If you pick prime table size (either because algorithm requires this, or because you are not satisfied with memory usage unreliability implied by power-of-2 size), table slot computation (modulo by table size) could be combined with hashing. See this answer for more.The point that table size of power of 2 is undesirable when hash function distribution is bad (from the answer by Neil Coffey) is impractical, because even if you have bad hash function, avalanching it and still using power-of-2 size would be faster that switching to prime table size, because a single integral division is still slower on modern CPUs that several of multimplications and shift operations, required by good avalanching functions, e. g. from MurmurHash3.
Q: Also to be honest I got lost a bit on if you actually recommend primes or not. Seems that it depends on the hash table variant and the quality of the hash function?
散列函数的质量无关紧要，您始终可以通过 MurMur3 雪崩 "improve" 散列函数，这比从次幂切换到素数 table 大小要便宜-2 table 大小，见上。
我推荐选择prime size，用QHash或者quadratic hash算法(aren't same), only when you need precise control over hash table load factor and predictably high actual loads. With power-of-2 table size, minimum resize factor is 2, and generally we cannot guarantee the hash table will have actual load factor any higher than 0.5. See this answer.
否则，我建议使用线性探测的 2 次幂大小的哈希 table。
Q: Is the approach of doubling because:
It is easy to implement, or
基本上，在很多情况下，是的。 见 this large answer regarding load factors:
Load factor is not an essential part of hash table data structure -- it is the way to define rules of behaviour for the dymamic system (growing/shrinking hash table is a dynamic system).
Moreover, in my opinion, in 95% of modern hash table cases this way is over simplified, dynamic systems behave suboptimally.
什么是加倍？这只是最简单的调整大小策略。该策略可以任意复杂，在您的用例中以最佳方式执行。它可以考虑当前哈希 table 大小、增长强度（自上次调整大小以来完成了多少 get 操作）等。没有人禁止您实现此类自定义调整大小逻辑。
Q: Is finding a prime number too inefficient (but I think that finding the next prime going over n+=2 and testing for primality using modulo is O(loglogN) which is cheap)
预先计算一些素数哈希 table 大小的子集是一种很好的做法，以便在运行时使用二进制搜索在它们之间进行选择。看the list double hash capacities and explaination, QHash capacities. Or, even using direct lookup，就是很快。
Q: Or this is my misunderstanding and only certain hashtable variants only require prime table size?
是的，只有某些类型需要，见上文。
Java HashMap (java.util.HashMap) 在链表（或 [自 JDK8] 树中链接桶冲突，具体取决于容器的大小和溢出）。
因此，关于辅助探测功能的理论不适用。 似乎消息 'use primes sizes for hash tables' 已经脱离了多年来适用的情况...
使用 2 的幂具有将散列值减少为 table 条目的优点（如其他答案所述），可以通过位掩码实现。整数除法相对昂贵，在高性能情况下这会有所帮助。
我要观察 "redistributing the collision chains when rehashing is a cinch for tables that are a power of two going to a power of two"。
请注意，当根据哈希码的 'next' 位使用 2 的幂重新散列到大小 'splits' 的两倍时，两个桶之间的每个桶。
也就是说，如果 hash-table 有 256 个桶，因此使用哈希值的最低 8 位重新散列会根据第 9 位拆分每个冲突链，并且要么保留在同一个桶 B 中（第 9 位为 0 ) 或进入 B+256 桶（第 9 位为 1）。这种拆分可以 preserve/take 桶处理方法的优势。例如，java.util.HashMap 以插入的相反顺序对小桶进行排序，然后将它们拆分为遵循该顺序的两个子结构。它将大桶保存在按哈希码排序的二叉树中，并类似地拆分树以保留该顺序。
注意：这些技巧直到 JDK8 才实现。
（我很确定）Java.util.HashMap 只会放大（永远不会缩小）。但是，将哈希值减半-table 与将其加倍具有相似的效率。
此策略的一个 'downside' 是 Object 实施者没有明确要求确保散列码的低阶位分布良好。
一个完全有效的散列码可能在整体上分布良好，但在其低位上分布不佳。因此，一个遵守 hashCode() 通用契约的对象在 HashMap 中实际使用时可能仍然会失败！
Java.util.HashMap 通过在提供的 hashCode() 实现上应用额外的散列 'spread' 来缓解这种情况。 'spread' 真的很粗鲁（将 16 位高位与低位异或）。
对象实施者应该意识到（如果还没有意识到的话）他们的散列码中的偏差（或缺乏）会对使用散列的数据结构的性能产生重大影响。
郑重声明，我的分析基于此源副本：
http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java