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 碰撞。
计算机中的取余运算 (也称为模运算) 是一个相对耗时的操作，主要是除法运算耗时较长。但是，计算机上的位运算耗时较短。所以人们找到了一种特殊情况，在这种情况下，计算机可以将取余运算转化为位运算，以节省 CPU 算力:
模数 m 为 2^n 时取余运算 key % m 会被转换为 AND 运算 key & (m - 1) 。
注意到 2^n 的二进制表示为 1 后接 n 个 0，而 2^n - 1 的二进制表示为 n 个 1。比如:
根据 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
可以看到: