按位与和取模运算 2022-05-06

a % b = a & (b-1) 当且仅当 b = 2^{^n} 时成立

当b=2^{^n}时，a / b 等价于二进制下向右移动n位，而 a % b 就是被右移走的a的低n位，而(b-1)的二进制表示恰好就是n个连续的1，因此a % b = a & (b-1)

• JDK8中hashmap就是以2的幂次方形式完成扩容的

  hashmap的底层数据结构是【数组挂载链表or红黑树】，初始化的数组容量是16，当数据量超过阈值时，翻倍扩容至32，以此类推

  我们知道，hashmap每扩容一次，必然引起数据的迁移，应当尽量减少迁移。而由于数组的容量是以2的幂次方扩容的，那么根据hashcode % L = hashcode & (L-1)，当L翻倍时为2L时，hashcode % 2L 就是在hashcode % L 的基础上多一个高位参与&运算。扩容后，如果&运算的结果最高位是0，则位置不动；结果最高位是1，则新位置=原位置+原长度。这样，保证了一部分数据原地不动，而需要迁移的数据也保有了原来的顺序