今天看 Java 源码中关于 put 函数的取哈希表的索引的这个没看懂。深究一番终于了解了其中的原因了。记录一下
今天看 Java 源码中关于 put 函数的取哈希表的索引的这个没看懂。深究一番终于了解了其中的原因了。记录一下
首先需要了解的是 HashMap 中哈希表的长度是 2^n，所以就有如下的公式：
(n - 1) & hash = hash % n
其中 n 为哈希表的长度且为 2 的次幂（注意顺序），关于 hash% n 就是普通的我们想要把 hash 值映射到对应的表位置使用的
方法，就是通过 hash 对表长取余，得出来的一定是比表长小的数，卡，就把 value 放到对应的位置即可。关键是
(n - 1) & hash 这个式子，是一个把表长减 1 然后和 hash 做 与 & 运算。首先解释一下与 & 运算：
与运算是一种二进制运算：
运算规则：0&0=0;0&1=0;1&0=0;1&1=1; 就是说只有都为 1 才能为 1 其他一律为 0。
打个比方：
01011（十进制的 11）
00111（十进制的 7）
-—–
00011（十进制的 3）
OK，在查资料的时候还查到了位运算相关知识：
| 符号 | 描述 | 运算规则 |
|---|---|---|
| & | 与 | 两个位都为 1 结果才为 1 |
| | | 或 | 两个位都为 0 结果才为 0 |
| ^ | 异或 | 两个位相同为 0 相异为 1 |
| ~ | 取反 | 0 变为 1，1 变为 0 |
| << | 左移 | 各个二进位左移若干位，高位丢弃，低位补 0 |
| >> | 右移 | 各个二进位右移若干位，对无符号数，高位补 0，有符号数不一样 |
左移对于二进制相当于 * 2，右移相当于 / 2 。
拿十进制举例：10 左移变为 100 就是乘十。右移变为 1 相当于除十；很有意思。Amazing
那么演过正传，还是谈论取余的，一个好好地取余运算咋就能变成与运算呢？
上面提到右移的运算，对于二进制来说，右移以为相当于除 2，但是！重点来了。移出去的数就是除 2 的余数！神奇不！看一下例子：
101001>>1 = 10100 余 1 对应的就是 41%2 余 1 接着往上推
101001>>2 = 1010 余 01 对应的就是 41%4 余 1 继续
101001>>3 = 101 余 001 对应的就是 41%8 余 1 go on
101001>>4 = 10 余 1001 对应的就是 41%16 余 9
所以说对于 hash% x ,x 为 2^n 时就等于 hash 的二进制的低 n 位数，
那么如何取到低 n 数呢？我们发现 2^n 数总是为 n+1 位为 1 后面都为 0 的数，比如
10 就是 2，100 就是 4,1000 就是 8,10000 就是 16，
那么相应的 2^n-1 就是 n+1 位为 0 其余为 1 的数，比如：
01 就是 1,011 就是 3,0111 就是 7,01111 就是 15。当这个数与 hash 做 与 & 运算的时候正好保留了 hash 的低 n 位数，就是这么的 Amazing。
所以 hash%n=hash&(n-1) 当 2 为 2 的次幂时。那么这么做有什么好处么？就是可以大大提高效率，位运算 (&) 效率要比代替取模运算 (%) 高很多，主要原因是位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。 对于 HashMap 里的取哈希表的索引来说是经常要执行的部分。这样就大大节省了开销
引用一句大佬的话，形容的真的很透彻：
如果数组长度是 2 的整数次方时，也就是一个偶数，length-1 就是一个奇数，奇数的二进制最后一位是 1，因此不管 hash (key) 是多少，hash (key)&(length-1) 的二进制最后一位可能是 0，也可能是 1，取决于 hash (key)。即如果 hash (key) 是奇数的话，则映射到数组上第奇数个位置上。
如果 length 是一个奇数的话，length-1 就是一个偶数，偶数的二进制最后一位是 0，则不管 hash (key) 是奇数还是偶数，该元素都会被映射到数组上第偶数个位置上，奇数位置上没有任何元素！
因此，数组长度是一个 2 的整数次方时，哈希碰撞的概率起码能下降一半，而且所有元素也能均匀地分布在数组上。
注：求余运算：a % b 就相当与 a - (a /b) * b 的运算
为了弄清这块儿真的是找了很多资料。不得不说百度真的太辣鸡了。公司还不能上谷歌和 StackOverFlow。影响查资料的效率。
但是下面这个文章就是点醒我的 trigger。
位与运算与取余