李守中
该站已迁往根域名 https://lishouzhong.com
需要注意,迁移后的文章的 url 可能会发生变化。
域名 https://note.lishouzhong.com 下的内容将不再更新,但已有内容会永久保留。

hash 算法相关

Table of Contents

1. 为什么推荐将素数作为模数

hash 算法的意义在于把一个大的集合 A,映射到小的集合 B。最常见的就是 hash(key) = key % m 这种通过取余来获取 hash 值得方式。其中,m 就是模数。

显然,hash(key) 的取值范围是 [0,m-1]。

假设存在一个整数 x 使得 key % m = key - xm 成立。

即,key 在去掉 x 个 m 之后,剩下的比 m 小的部分就是 key % m 的值。

现在我们把

hash(key) = key - xm

变形为

hash(key) = gcd(key,m)*(key/gcd(key,m) - xm/gcd(key,m))

注: gcd 函数表示计算最大公约数

可知 hash(key) 的值只能是 gcd(key,m) 的倍数。这意味着在实际操作时,hash(key) 的值不一定能取到 [0,m-1] 上的所有值。

显然,gcd(key,m) 的值不为 1 时,hash(key) (即非 1 数的倍数) 一定不能取到 [0,m-1] 上的所有值。要想让 hash(key) 能取到 [0,m-1] 上的所有值,只能让 gcd(key,m) = 1。此时 hash(key) 的取值是 1 的倍数,然而任何数都是 1 的倍数,也就意味着 hash(key) 可以取到 [0,m-1] 上的所有值。

gcd(key,m) = 1 意味着,key 和 m 的最大公约数为 1。通常,在实际操作中,key 的取值无法被影响,但 m 的取值可以人为规定。

如果将 m 定为一个素数,那么除非 key 是 m 的倍数,否则 gcd(key,m) 的值永远为 1。这样可以尽可能地让 hash(key) 的值在 [1,m-1] 上均匀分布,避免 hash 碰撞。

2. 计算机对取余计算的优化

计算机中的取余运算 (也称为模运算) 是一个相对耗时的操作,主要是除法运算耗时较长。但是,计算机上的位运算耗时较短。所以人们找到了一种特殊情况,在这种情况下,计算机可以将取余运算转化为位运算,以节省 CPU 算力:

模数 m = 2^n 时取余运算 key % m 会被转换为 AND 运算 key & (m - 1)

注意到 2^n 的二进制表示为 1 后接 n 个 0,而 2^n - 1 的二进制表示为 n 个 1。比如:

  • 2^4 = 16,二进制表示为 10000
  • 2^5 = 32,二进制表示为 100000
  • 2^4 - 1 = 15,二进制表示为 1111
  • 2^5 - 1 = 31,二进制表示为 11111

根据 AND 运算的逻辑 0 AND 1 = 0, 1 AND 1 = 1 可以知道,key 与二进制表示为 n 个 1 的数,从低位到高位,按位做 AND 运算就表示取 key 的二进制表示的 n 个低位。

例如,如果我们要计算 21 % 8:

8      = 01000
8 - 1  = 00111 = 7
21     = 10101
-------------
21 % 8 = 00101 = 5

可以看到:

  • m = 8 = 2^3 的二进制表示是 1000,n 值为 3
  • m - 1 = 7 的二进制表示是 111,高位补 0 变成 00111
  • key = 21 的二进制表示是 10101
  • key & (m - 1) 的效果是保留了从低位开始的 n 位,即,保留低 3 位得到 101 转十进制为 5


Last Update: 2024-04-10 Wed 11:56

Generated by: Emacs 28.2 (Org mode 9.5.5)   Contact: lsz.sino@outlook.com

若正文中无特殊说明,本站内容遵循: 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议