universal hashing prime numbers 质数的基本应用: universal hashing

[cybernagle]

universal hash 就是随机选择 hash function , 从而让碰撞几率变为 1/m , 也就是不碰撞. 比如说我的 slot 的位置是 100 , 我碰撞的几率是 1/100. 那么基本上每个人都会有自己的 slot ;

而实现这个 feature 的函数为:

((a*k + b) mod p) mod m

p 是一个 prime number 这个里面的 a = {1, 2, 3, 4 ... p-1} 这里的 b = {0, 1, 2, 3, 4 ... p-1}

然后 mod p 的目的就是将其带回到 p 的领域 然后再 mod m 就是将其带回到 m 的领域.

[cybernagle]

为什么是 prime ?

1. F 是 symmetrical, a k 这个数是对称的. a k mod p == k * a mod p
2. 并且, 因为 p 是质数, 所以 a*k mod p 不会等于0

如果等于 0 的话, 就不能 reverse 了

[cybernagle]

第二个, x1, x2 属于 U 的情况下, (x1 a + b) mod p == (x2 a + b) mod p 吗? 如果相等, 则 (x1 a) == (x2 a) modp a(x1 - x2) == 0 modp