通用哈希基础知识，如何确保可访问性 [英] Basics in Universal Hashing, how to ensure accessibility

问题描述

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

to my current understanding Universal Hashing is a method whereby the hash function is chosen randomly at runtime in order to guarantee reasonable performance for any kind of input.

我知道我们可以这样做是为了防止有人故意选择恶意输入(已知确定性哈希函数的可能性).

I understand we may do this in order to prevent manipulation by somebody choosing malicious input deliberately (a possibility of a deterministic hash function is know).

我的问题如下:这是不正确的，我们仍然需要保证每次对键进行哈希处理时，键都将映射到同一地址吗?例如，如果我们要检索信息，但是随机选择了哈希函数，那么我们如何保证我们可以取回我们的数据呢?

My Question is the following: Is it not true, that we still need to guarantee that a key will be mapped to the same address every time we hash it ? For instance if we want to retrieve information, but the hash function is chosen at random, how do we guarantee we can get back at our data ?

推荐答案

通用哈希函数是一系列不同的哈希函数，这些哈希函数具有以下特性:从宇宙中随机选择的两个元素很可能不会发生冲突选择哪个哈希函数.通常，这是通过让实现从一系列哈希函数中选择一个随机哈希函数以在实现内部使用来实现的.选择此哈希函数后，哈希表将照常工作-您可以使用此哈希函数计算对象的哈希码，然后将对象放入适当的位置.哈希表必须记住对哈希函数所做的选择，并且必须在整个程序中始终使用它，因为否则(如您所指出的那样)它将忘记将每个元素映射到何处.

A universal hash function is a family of different hash functions that have the property that with high probability, two randomly-chosen elements from the universe will not collide no matter which hash function is chosen. Typically, this is implemented by having the implementation pick a random hash function from a family of hash functions to use inside the implementation. Once this hash function is chosen, the hash table works as usual - you use this hash function to compute a hash code for an object, then put the object into the appropriate location. The hash table has to remember the choice of the hash function it made and has to use it consistently throughout the program, since otherwise (as you've noted) it would forget where it mapped each element.

希望这会有所帮助！

这篇关于通用哈希基础知识，如何确保可访问性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！