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