4

据我目前的理解，通用散列是一种在运行时随机选择散列函数以保证任何类型输入的合理性能的方法。

我知道我们可能会这样做，以防止有人故意选择恶意输入进行操纵（知道确定性哈希函数的可能性）。

我的问题如下：这不是真的吗，我们仍然需要保证每次散列时都会将密钥映射到相同的地址？例如，如果我们想检索信息，但哈希函数是随机选择的，我们如何保证我们可以取回我们的数据？

4

1 回答 1

6

通用散列函数是一组不同的散列函数，它们具有以下性质：无论选择哪个散列函数，宇宙中两个随机选择的元素都不会发生碰撞。通常，这是通过让实现从一系列散列函数中选择一个随机散列函数在实现内部使用来实现的。一旦选择了这个散列函数，散列表就照常工作——你使用这个散列函数计算一个对象的散列码，然后把对象放到适当的位置。哈希表必须记住它所做的哈希函数的选择，并且必须在整个程序中始终如一地使用它，否则（正如您所指出的）它会忘记它映射每个元素的位置。

希望这可以帮助！

于 2012-01-30T21:25:33.467 回答