y % x = y & (x - 1)的数学证明
在基于哈希表实现的Map中一个常用技巧就是将哈希桶的数量设置为2的n次方，也就是\(2^n\)，此后通过取余操作定位key所在桶的位置可以转换成与运算。之所以将取余运算改成与运算，一方面这两者计算的结果是一样的，另外一方面是因为与运算具有更好的性能，因为与运算指令周期是小于取余运算的。Java中的 HashMap 和Go中 map 都使用到这个技巧。
基于哈希表实现的Map中的取余运算转换成与运算的技巧，用数学语言来表达：
对于正整数x, y，如果x为2的n次方，n为正整数，那么\(y\;\%\;x = y \;\&\; (x-1)\) 表达式是成立的。
对于\(y\;\%\;x = y \;\&\; (x-1)\)等式的成立有很多理解角度，本文从数学角度出发，尝试以数学证明方式来证明它。证明过程如下：
y为正整数，将y转换成二进制后，其十进制的值可以用如下表达式表示，其中\(a_1\)，\(a_2\)，... \(a_n\)分别表示y二进制表示时其第1位，第2位，第n位上的值，依次类推：
举例说明，比如y为25时候，其对应二进制为11001，那么上面表达式表示如下：
其中\(a_1=1\)，\(a_2= 0\)，\(a_3=0\)，\(a_4=1\)，\(a_5=1\)，\(a_5\)之后的都为0，这里面为了方便理解，把\(a_5\)之后都写出来了。
那么 \(y\;\%\;x\)可以转换成：
由于x是2的n次方，所以\(x=2^n\)，那么上面表达式可以转换为：
进一步转换成：
从上面可以看到我们把y分为从\(a_1\)到\(a_n\)和从\(a_{n+1}\)到无穷这两部分，按照模运算规则：\((a + b) \;\%\; p = (a \;\%\; p + b \;\%\; p) % p\)，上面表达式可以继续转换成如下：
由于\((a_{n+1} * 2^n + a_{n+2} * 2^{n+1}+...)\)可以整除\(2^n\)，上面表达式可以进一步简化为：
而\(a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1}\)可能的最大值为\(2^n-1\)（当且仅当\(a_1 = a_2 = ... = a_n = 1\)时），也就是说\(a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1} < 2^n\), 那么存在：
那么等式\(y\;\%\;x= ((a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1})\%2^n)\;\%\;2^n\)进一步可以简化为：
上面等式中\(a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1}\)的含义是y二进制表示时候第1位到n位，其对应的十进制整数结果可以用与运算\(y\;\&\;(2^0+2^1 + ... + 2^{n-1})\)得到，存在以下等式：
\(y\;\%\;x= a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1}\)等式可以进一步简化处理得到我们要证明的等式：
综上所述，对于正整数x, y，如果x为2的n次方，n为正整数，那么\(y\;\%\;x = y \;\&\; (x-1)\) 表达式是成立的。