前言

为了程序的高效运行，合理的Hash函数设计至关重要

Subdiffusions

常用的方法有很多，例如bitwise subdiffusions

$$d(x)=\sigma(x)\oplus m$$

其中，$\sigma(x)$代表$x$的二进制排列

dependent bitwise subdiffusions

$$d(x)=\sigma(x)\oplus x$$

$$d(x)=(x\ll m) \oplus x$$

linear subdiffusions

$$d(x) \equiv ax + c \pmod m, \quad \gcd(x, m) = 1$$

arithmetic subdiffusions

$$d(x) = x \oplus (x + c)$$

Diffusions

通过多个Subdiffusions的组合，可以得到一个比较好的Diffusions。

但仍需要注意的是，得到的Diffusions应当对为0的输入有反应：例如，对集合$\{3,0\}$与集合$\{3\}$分别哈希，得到的hash值应当不同

常用算法

FNV-1a

# 32位
hash = 2166136261
mod = pow(2, 31)
for value in values:
    hash = hash ^ value
    hash = hash * 16777619 % mod

# 64位
hash = 14695981039346656037
mod = pow(2, 63)
for value in values:
    hash = hash ^ value
    hash = hash * 1099511628211 % mod

参考

http://ticki.github.io/blog/designing-a-good-non-cryptographic-hash-function/

wiki (opens new window)