Universal Hashing全域哈希原理与python实现,减少hash冲突/碰撞!

深渊向深渊呼唤

全域哈希原理与实现

1-hash哈希介绍 2-Universal hashing全域哈希法 3-构造一个全域哈希H\mathcal{H}H 4-python实现

1-hash哈希介绍

hash函数y=h(k)y=h(k)y=h(k),把任意长度的输入kkk通过散列算法hhh变换成固定长度的输出yyy,该输出就是散列值1。一种常见的hash函数是y=H(k)=(ak+b)mod  my=H(k)=(a\cdot k+b) \mod my=H(k)=(a⋅k+b)modm,mmm一般取素数。
设hash函数的定义域为KKK,值域为YYY,一般来说,K>Y|K|>|Y|∣K∣>∣Y∣,这样hash函数容易出现碰撞,如下图,h(k5)=h(k2)=h(k7)h(k_5)=h(k_2)=h(k_7)h(k5​)=h(k2​)=h(k7​),k5,k2,k7k_5,k_2,k_7k5​,k2​,k7​在一条链上(碰撞):

在这里插入图片描述
对于hash函数,基本上都能找到一组输入,使得它们的hash值都相同,导致它们在一条链上,有时甚至会比线性查找的复杂度还要高,因为比线性查找多了hash的时间。

2-Universal hashing全域哈希法

思路:解决上述问题的一种方法就是随机。随机从一组hash函数(a family of hash functions)中选择一个。这样选的话,攻击者就没办法针对特定的hash函数构造一组输入,使得hash函数效率很低。

定义1U\mathcal{U}U是定义域,H\mathcal{H}H是hash函数的集合,能够将U\mathcal{U}U映射到{0,1,...,m1}\{0, 1, ..., m-1\}{0,1,...,m−1},即h:U{0,1,...,m1},hHh:\mathcal{U}\rightarrow\{0, 1, ..., m-1\}, h\in \mathcal{H}h:U→{0,1,...,m−1},h∈H.

定义2:如果x,y\forall x, y∀x,y满足xyx\neq yx​=y并且{hH:h(x)=h(y)}=Hm|\{h\in \mathcal{H}:h(x)=h(y)\}|=\frac{|\mathcal{H}|}{m}∣{h∈H:h(x)=h(y)}∣=m∣H∣​,则称H\mathcal{H}H是全域(universal)的。

根据定义2,如果h是随机均匀地从H\mathcal{H}H中选择(注意每个输入要重新选择一个hash函数), 那么xxx和yyy碰撞的概率是:
h(x)=h(y)=HmH=1m.\frac{h(x)=h(y)的函数数量}{所有的函数} =\frac{\frac{|\mathcal{H}|}{m}}{|\mathcal{H}|}=\frac{1}{m}.所有的函数h(x)=h(y)的函数数量​=∣H∣m∣H∣​​=m1​.

定理1:随机均匀地从H\mathcal{H}H(H\mathcal{H}H是全域的)选择hhh,如果我们现在已经把nnn个输入放入了hash表TTT中了,则再给一个输入xxx,有
E[hashTx]<nm,E[hash表T中元素和x碰撞的数量]<\frac{n}{m},E[hash表T中元素和x碰撞的数量]<mn​,
其中E[]E[\cdot]E[⋅]表示期望。

[定理1的重要性] 通过证明上述定理,我们就可以说,如果存在H\mathcal{H}H是全域的,那么最终在hash表TTT中元素的分布(在平均意义上)是均匀的。

定理1的证明.CxC_{x}Cx​表示在hash表TTT中的随机元素和xxx碰撞的数量,设
Cxy={1if h(x)=h(y)0if h(x)h(y)C_{xy}=\left\{\begin{array}{cr} 1 & if\ h(x)=h(y) \\ 0 & if\ h(x)\neq h(y) \end{array}\right.Cxy​={10​if h(x)=h(y)if h(x)​=h(y)​
那么,
E[Cx]=E[yTxCxy]=yTxE[Cxy]线=yTx1m=(n1)1m<nm.\begin{array}{lll} E[C_x]&=E[\sum_{y\in T-x}C_{xy}] \\ &=\sum_{y\in T-x}E[C_{xy}] & 因为期望的线性性质\\ &=\sum_{y\in T-x}\frac{1}{m} \\ &=(n-1)\frac{1}{m} \\ &<\frac{n}{m}. \end{array}E[Cx​]​=E[∑y∈T−x​Cxy​]=∑y∈T−x​E[Cxy​]=∑y∈T−x​m1​=(n−1)m1​<mn​.​因为期望的线性性质

例子 :如果n=1,m=2n=1,m=2n=1,m=2,则E[Cx]<12.E[C_x]<\frac{1}{2}.E[Cx​]<21​.

3-构造一个全域哈希H\mathcal{H}H

定理2: 按照如下四个步骤构造的H\mathcal{H}H是全域的:

    (条件)令mmm等于一个素数; (初始准备)将输入kkk写成r+1r+1r+1个数字:k=<k0,k1,...,kr>k=<k_0,k_1,...,k_r>k=<k0​,k1​,...,kr​>,其中ki{0,1,...,m1}k_i\in\{0, 1, ..., m-1\}ki​∈{0,1,...,m−1}(等价于将kkk用mmm进制表示); (随机)随机选择一个a=<a0,a1,...,ar>a=<a_0, a_1,...,a_r>a=<a0​,a1​,...,ar​>,其中ai0,1,...,m1a_i\in{0, 1,..., m-1}ai​∈0,1,...,m−1; (hash函数)ha(k)=(i=0i=rai×ki)mod  mh_a(k)=(\sum_{i=0}^{i=r}a_i\times k_i) \mod mha​(k)=(∑i=0i=r​ai​×ki​)modm.

证明见2

4-python实现

自己写的代码,如有错误望指正。代码链接:https://github.com/VFVrPQ/LDP/blob/master/Components/UniversalHashing.py,另有完整代码如下:

import math
import random
class UniversalHashing:
    '''
        g: a prime
        d: domain, [0, 1, ..., d-1]
        len: The maximum number of digits in g Base
        v: an input value in [0, 1, ..., d-1] 
        hash function: H_a(k) = (a(0)*k(0)+a(1)*k(1)+...+a(len-1)*k(len-1)) % g
    '''
    def __init__(self, g, d):
        self.__g = g
        assert g>=2, 'g is less than 2'
        assert self.__isPrime(g), 'g is not a prime'

        self.__d = d
        self.__len = math.ceil( math.log(d) / math.log(g)) # g进制下,最大的位数
        self.__a = self.__len*[0] # initial length
    
    # v is an input value in [0, 1, ..., d-1] 
    def hash(self, v):
        self.__randomness() # regenerate a, select H
        out = self.calc(self.__a, v)
        return self.__a, out

    # calc H_a(k) = (a(0)*k(0)+a(1)*k(1)+...+a(len-1)*k(len-1)) % g
    def calc(self, a, v):
        assert len(a)==self.__len, 'len(a)!=self.__len'
        k = self.__toBitList(v)
        out = 0
        for i in range(self.__len):
            out = (out + a[i]*k[i]) % self.__g
        return out

    def __randomness(self):
        # generate a
        for i in range(self.__len):
            self.__a[i] = random.randint(0, self.__g-1)

    def __toBitList(self, v):
        assert v>=0, 'v<0'
        if v == 0:
            return self.__len * [0]
        bitList = self.__len * [0]
        for i in range(self.__len):
            bitList[i] = v%self.__g
            v = int(v/self.__g)
        return bitList
    
    def __isPrime(self, v):
        if v<=1:
            return False
        for i in range(2, int(math.sqrt(v))+1, 1):
            if v%i==0:
                return False
        return True

# for test
if __name__ == "__main__":
    TIMES = 10
    g = 29 # prime
    d = 16 # domain
    uhash = UniversalHashing(g, d)
    H = g * [0]
    for i in range(TIMES): # random TIMES to verify
        x = random.randint(0, d-1)
        _, out = uhash.hash(x)
        H[out] += 1
    for i in range(g):
        print(i, H[i])

    https://baike.baidu.com/item/Hash/390310?fr=aladdin ↩︎

    http://cs-www.bu.edu/faculty/homer/537/talks/SarahAdelBargal_UniversalHashingnotes.pdf 或者https://download.csdn.net/download/MustImproved/12275636 ↩︎

栏目