江苏龙网

  1. 首页 > 生活 > >

全域哈希是啥意思

由于数学功底太差，只能给出一个对于全域哈希的一个感性认识。首先哈希有一个我们无法回避的缺点，对于某个键集，它的键值是一样的。那么对于别有用心的数据，该哈希函数的表现就是很差的，那么我们如何尽量避免这种情况呢？就像家源说的那样，random就好呀，我们都不知道会在函数族里撞到谁，那么自然就会达到目的了。那么对于它的定义，既然碰撞的概率不会超过1/m，那么我们可以证明对于任意的x，它的碰撞次数的期望是严格小于装载因子α的，实际上E(Cx)=(n-1)/m。而实际上题主有疑问的那句话。。。恰好这就是全域哈希的定义。祝您越来越强。
■网友
参考《introduction to algorithms》\u0026amp; Universal hashing，以下是个人理解，不知正确否：
universal hash 指一个有限hash函数族H={h0, h1, ..., ht}，hx彼此之间相互独立，hx可以将n elements 映射到 m slots中，且映射到每一个slot中的概率是等价的，即为1/m。
则有：任意的k, l ∈ n elements，从H中选定某一hash函数hx，映射到同一个slot中也就是产生collision的概率是1/m。
又hash函数族中各hash函数相互独立，对任意的k, l ∈ n elements，hash函数族将其映射到同一个slot中的概率是|H| * 1/m = |H|/m。
个人感觉，universal hash主要是为了perfect hash准备的，以便证明perfect hash优越性能和随机性。
看不懂，我觉得也无所谓啦，但要知道怎么产生一族hash函数即可。

■网友
就是说你有一组函数H包含|H|个函数，把所有的关键字散列成0～m-1的哈希值。我们把H设计成有这样一个性质：对于所有的不相等关键字x和y，使x和y的散列值相等的函数h的个数等于|H|/m 那么，在不知道选择了哪个函数时，两个不相等的关键字x和y会有相同的哈希值的概率可以计算出来：在最开始时随机选一个函数hi，然后所有的值都用这个函数散列，那么P{ 还没确定函数hi时，hi(x)=hi(y)且x!=y }= 使hi(x)=hi(y)相等的函数个数 / 函数的总个数= ( |H|/m ) / |H| = 1/m正好等于随机选择散列值时，两个不同关键字散列值相等的概率/*不知道大家看clrs时有没有这样的问题，感觉书里有时候表达不清楚。刚开始看的时候我还以为每次插入一个关键字时都要随机选择函数，但是这样就没法查找关键字了，想了一个晚上想不出来，怀疑智商了，看了网上的代码，发现在最初执行的时候，把函数指针固定了....*/
■网友
【全域哈希是啥意思】 全域哈希指的是在哈希函数中, 加入随机值保证哈希函数的不同. 用于实现完美散列, 其中各表随机值是要保存的.


    推荐阅读


    上一篇：年薪30W～60W的BAT中层程序猿在古代大概算个啥样社会角色

    下一篇：高级语言中哪些函数会导致被exploit?