java - 双散列中的重新散列也会改变主散列函数吗？

Question

当您在双重哈希中与主哈希函数发生冲突时，您使用辅助哈希函数。但是如果你也有冲突，那么你必须重新哈希，所以你将表大小加倍并选择最接近的素数作为新的表大小。这也会改变你的主要散列函数吗？例如，如果您的主散列函数是 key mod tableSize 并且您的 tableSize 最初是 11，现在是 23，那么它也会改变吗？因为如果哈希函数保持不变，您仍然会在相同的位置发生冲突。

Answer 1

当您在双重哈希中与主哈希函数发生冲突时，您使用辅助哈希函数。但是如果你也有冲突，那么你必须重新哈希，所以你将表大小加倍并选择最接近的素数作为新的表大小。

我不认为这是真的。

在双重哈希中，

 h(k,i) = h1(k) + i*h2(k)

其中 h(k,i) 是为密钥探测的第 (i+1) 个槽。所以你连续增加i，这样你就碰到了一个空槽。

当负载因子超过特定值时，您需要重新散列，是的，在重新散列时，通常主散列函数会改变，但我认为没有它你可以过关（[编辑：更改主散列函数]），虽然它会降低性能。

Answer 2

几周前在我的数据结构课上，我们正在研究哈希表。我也遇到了这个困境。当我问我的教授时，他说没有必要在重新散列时更改主散列函数。即使在技术上您仍然在同一个地方发生冲突，您仍然应该能够在使用开放寻址技术重新散列时找到一个空白点。但是，他说通常主哈希函数会更改为新的模数，原因之一是它有助于防止数据聚集。因此，总而言之，从他所说的任何一种方式来看都没有对错，但是更改哈希函数是更好的途径，以避免在同一个地方发生聚类和冲突。希望这可以帮助！

Answer 3

实际上，对于双散列，我使用表大小 2^N 和两个散列函数，计算值 h1(position) 和 h2(step)。步数必须为奇数，以符合条件

gcd(table_sz, step) == 1

当满足此条件时，试用索引会迭代表中的所有单元格。

此后，我只用索引 (pos)、(pos+step)、(pos + step + step) 等对表进行迭代，以 table_size 为模。

程序的主循环看起来像：

do {
  pos = (pos + step) & (TAB_SIZE - 1);
} while(table[pos] have collision);

在此处查看简单的实现示例：

http://olegh.cc.st/src/words.c.txt

有趣的实现，当你有 TAB_SIZE = 2^16 时。在这种情况下，您可以将变量（pos，step）定义为 unsigned short，并且不需要应用掩码（TAB_SIZE - 1）；相反，您只需编写：

pos += step;