Bel*_*ame 4 theory hash data-structures universal-hashing
我目前的理解Universal Hashing是一种在运行时随机选择散列函数的方法,以保证任何类型输入的合理性能.
我知道我们可能会这样做是为了防止有人故意选择恶意输入的操纵(知道确定性散列函数的可能性).
我的问题如下:是不是真的,我们仍需要保证每次哈希时都将一个密钥映射到同一个地址？例如,如果我们想要检索信息,但随机选择哈希函数,我们如何保证我们可以回到我们的数据？
通用散列函数是具有以高概率,从宇宙2随机选择的元素将不会碰撞没有被选择哪个哈希函数物质的属性不同的散列函数族.通常,这通过使实现从一系列散列函数中选择随机散列函数以在实现内部使用来实现.选择此哈希函数后,哈希表将照常工作 - 您使用此哈希函数计算对象的哈希码,然后将对象放入适当的位置.哈希表必须记住它制成,并且具有在整个程序持续使用哈希函数的选择,因为否则的话(如你提到的),将它映射每个元素忘记.
希望这可以帮助!
| 归档时间： |
|
| 查看次数： |
789 次 |
| 最近记录： |