data-structures - 将哈希表复制到新的重新哈希表

Question

我有一个关于重新散列的问题。假设我们有一个大小为 7 的哈希表，我们的哈希函数是 (key%tableSize)。我们将 24 插入到表中，因为 24%7=3，所以 24 将位于索引 3。然后，假设我们添加了更多元素，现在我们要重新散列。表大小将是初始表大小的两倍，即新表大小将是 14。那么，在将元素复制到新哈希表时，例如，在复制元素 24 时，它是否仍然在索引 3 中，还是会在索引 24%14=10 处。我的意思是，我们是在复制元素时使用新的表大小，还是元素保留在它们的初始索引中？谢谢

Answer 1

关于哈希表的重要一点是元素的顺序不能保证，它取决于哈希函数。

对于您的示例：如果您使用 7 作为哈希大小将数据复制到新哈希中，则您的索引：新数组的 7、8、9、10、11、12 和 13 将未被使用，因为您使用了更大的数组并且您的哈希函数不能给你大于 6 的结果。这些未使用的索引是一件坏事，因为你根本不需要它们，所以最好key % 14改用它们。

有趣的是，内部哈希表状态不仅取决于哈希函数，还取决于元素插入的顺序。例如，假设有一个大小为 4 的哈希表（用数组和链表实现）X，然后按该顺序插入元素 2、3、6、10：

x 
{
    [0] -> []
    [1] -> []
    [2] -> [2,6,10]
    [3] -> [3]
}

再次使用哈希函数key % size。

现在，如果我们以不同的顺序插入键 - 10、6、3、2，我们得到：

x 
{
    [0] -> []
    [1] -> []
    [2] -> [10,6,2]
    [3] -> [3]
}

我在上面写了所有这些行，只是为了向您展示哈希的两个副本在内部可能看起来不同，因为有很多因素。我认为这是对您问题的考虑。

Answer 2

这取决于您的哈希函数。在您的情况下，您应该使用 key%size_of_table 否则 7 之后的插槽将永远不会被散列函数映射。只有当您选择线性探测以解决碰撞时，这些插槽才会被占用。（我们在哪里寻找下一个空插槽）。选择新的尺寸将有助于减少早期的碰撞，否则情况表还没有达到负载因子，你仍然面临着很多碰撞。