Java 8 中 HashMap 的实现使用了很多位操作来进行优化。本文将详细介绍每种位操作优化的原理及作用。
-
Java 中的位运算
- 位操作包含：与、或、非、异或
- 移位操作包含：左移、右移、无符号右移
-
HashMap 中的位运算
- 计算哈希桶索引
- hashCode 方法优化
- 指定初始化容量
- 扩容方法里的位运算
-
总结回顾
Java 8 中，HashMap 类使用了很多位运算来进行优化，位运算是非常高效的。下边我们将详细介绍。
Java 中的位运算
位操作包含：与、或、非、异或
-
与
&，两个操作数中的位都是 1，结果为 1，否则为 0。- 1 & 1 = 1
- 0 & 1 = 0
- 1 & 0 = 0
- 0 & 0 = 0
-
或
|，两个操作数中的位只要有一个为 1，结果为 1，否则为 0。- 1 | 1 = 1
- 0 | 1 = 1
- 1 | 0 = 1
- 0 | 0 = 0
-
非
~，单个操作数中的位为 0，结果为 1；如果位为 1，结果为 0。- ~1 = 0
- ~0 = 1
-
异或
^，两个操作数中的位相同结为 0，否则为 1。- 1 ^ 1 = 0
- 0 ^ 1 = 1
- 1 ^ 0 = 1
- 0 ^ 0 = 0
移位操作包含：左移、右移、无符号右移
- 左移
<<，左移 n 为相当于乘以 2n，例如 num<<1，num 左移 1 位 = num*2；num << 2，num 左移 2 位 = num*4 - 右移
>>，右移 n 为相当于除以 2n，例如 num>>1，num 右移 1 位 = num/2；num>>2，num 右移 2 位 = num/4 - 无符号右移
>>>，计算机中数字以补码存储，首位为符号位；无符号右移，忽略符号位，左侧空位补 0
HashMap 中的位运算
Java 8 中 HashMap 的实现结构如下图所示，对照结构图我们将分别介绍 HashMap 中的几种位运算的实现原理以及它们的作用、优点。
计算哈希桶索引
HashMap 的 put(key, value) 操作和 get(key) 操作，会根据 key 值计算出该 key 对应的值存放的桶的索引。计算过程如下：
- 计算 key 值的哈希值得到一个正整数，hash(key) = hash
- 使用 hash(key) 得到的正整数，除以桶的长度取余，结果即为 key 值对应 value 所在桶的索引，index = hash(key) % length
put/get 操作，计算 key 值对应 value 所在哈希桶的索引的主要代码
// table 即为上述结构图中存放左边桶的数组transient Node<K,V>[] table;// 计算 key 值的哈希值static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}public V put(K key, V value) { return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) // 当 table 为 null 或长度为 0 时，初始化数组 table n = (tab = resize()).length; // tab[i = (n - 1) & hash] 的下标表达式 i = (n - 1) & hash 即为计算哈希桶的索引 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { 省略其他代码 } 省略其他代码}public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value;}final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // n = tab.length，n 即为哈希桶的长度 // tab[(n - 1) & hash]，hash 为 key 值的哈希值，表达式 (n - 1) & hash 为哈希桶的索引 省略其他代码 } return null;}
上述代码中，使用了与操作来代替取余，我们先来看结论：当 length 为 2 的次幂时，num & (length - 1) = num % length 等式成立，使用 Java 代码来验证一下：
public static void main(String[] args) { // n 次幂 int multiple = 0; // 长度 int length; // 不成立的次数 int fail = 0; while (true) { length = (int) Math.pow(2, ++multiple); if (length >= Integer.MAX_VALUE) { break; } // 随机生成一个正整数 int num = new Random().nextInt(Integer.MAX_VALUE - 1); // 判断等式是否成立 if ((num & (length - 1)) != num % length) { fail++; } else { System.out.printf("2 的%d 次幂，length=2^%d=%d，转换成二进制：length=%s,length-1=%s\n", multiple, multiple, length, Integer.toBinaryString(length), Integer.toBinaryString(length - 1)); } } if (fail == 0) { System.out.printf("当 length 为 2 的次幂时，num & (length - 1) = num %s length 等式成立, 最大%d 次幂\n", "%", multiple - 1); }}
执行结果：
2 的 1 次幂，length=2^1=2，转换成二进制：length=10,length-1=12 的 2 次幂，length=2^2=4，转换成二进制：length=100,length-1=112 的 3 次幂，length=2^3=8，转换成二进制：length=1000,length-1=1112 的 4 次幂，length=2^4=16，转换成二进制：length=10000,length-1=11112 的 5 次幂，length=2^5=32，转换成二进制：length=100000,length-1=111112 的 6 次幂，length=2^6=64，转换成二进制：length=1000000,length-1=1111112 的 7 次幂，length=2^7=128，转换成二进制：length=10000000,length-1=11111112 的 8 次幂，length=2^8=256，转换成二进制：length=100000000,length-1=111111112 的 9 次幂，length=2^9=512，转换成二进制：length=1000000000,length-1=1111111112 的 10 次幂，length=2^10=1024，转换成二进制：length=10000000000,length-1=11111111112 的 11 次幂，length=2^11=2048，转换成二进制：length=100000000000,length-1=111111111112 的 12 次幂，length=2^12=4096，转换成二进制：length=1000000000000,length-1=1111111111112 的 13 次幂，length=2^13=8192，转换成二进制：length=10000000000000,length-1=11111111111112 的 14 次幂，length=2^14=16384，转换成二进制：length=100000000000000,length-1=111111111111112 的 15 次幂，length=2^15=32768，转换成二进制：length=1000000000000000,length-1=1111111111111112 的 16 次幂，length=2^16=65536，转换成二进制：length=10000000000000000,length-1=11111111111111112 的 17 次幂，length=2^17=131072，转换成二进制：length=100000000000000000,length-1=111111111111111112 的 18 次幂，length=2^18=262144，转换成二进制：length=1000000000000000000,length-1=1111111111111111112 的 19 次幂，length=2^19=524288，转换成二进制：length=10000000000000000000,length-1=11111111111111111112 的 20 次幂，length=2^20=1048576，转换成二进制：length=100000000000000000000,length-1=111111111111111111112 的 21 次幂，length=2^21=2097152，转换成二进制：length=1000000000000000000000,length-1=1111111111111111111112 的 22 次幂，length=2^22=4194304，转换成二进制：length=10000000000000000000000,length-1=11111111111111111111112 的 23 次幂，length=2^23=8388608，转换成二进制：length=100000000000000000000000,length-1=111111111111111111111112 的 24 次幂，length=2^24=16777216，转换成二进制：length=1000000000000000000000000,length-1=1111111111111111111111112 的 25 次幂，length=2^25=33554432，转换成二进制：length=10000000000000000000000000,length-1=11111111111111111111111112 的 26 次幂，length=2^26=67108864，转换成二进制：length=100000000000000000000000000,length-1=111111111111111111111111112 的 27 次幂，length=2^27=134217728，转换成二进制：length=1000000000000000000000000000,length-1=1111111111111111111111111112 的 28 次幂，length=2^28=268435456，转换成二进制：length=10000000000000000000000000000,length-1=11111111111111111111111111112 的 29 次幂，length=2^29=536870912，转换成二进制：length=100000000000000000000000000000,length-1=111111111111111111111111111112 的 30 次幂，length=2^30=1073741824，转换成二进制：length=1000000000000000000000000000000,length-1=111111111111111111111111111111当 length 为 2 的次幂时，num & (length - 1) = num % length 等式成立, 最大 30 次幂
根据上述结果我们看出，length 为 2 的 n 次幂时，转换为二进制，最高位为 1，其余位为 0；length-1 则所有位均为 1。1 和另一个数进行与操作时，结果为另一个数本身。
因为 length - 1 的二进制每一位均为 1，所以 length - 1 与另一个数进行与操作时，另一个数的高位被截取，低位为另一个数对应位的本身。结果范围为 0 ~ length - 1，和取余操作结果相等。
那么桶数为什么必须是 2 的次幂？比如当 length = 15 时，转换为二进制为 1111，length - 1 = 1110。length - 1 的二进制数最后一位为 0，因此它与任何数进行与操作的结果，最后一位也必然是 0，也即结果只能是偶数，不可能是单数，这样的话单数桶的空间就浪费掉了。同理：length = 12，二进制为 1100，length - 1 的二进制则为 1011，那么它与任何数进行与操作的结果，右边第 3 位必然是 0，这样同样会浪费一些桶空间。
综上所述，当 length 为 2 的次幂时，num & (length - 1) = num % length 等式成立，并且它有如下特点：
- 位运算快于取余运算
- length 为 2 的次幂时，
0～length - 1范围内的数都有机会成为结果，不会造成桶空间浪费
hashCode 方法优化
上述代码中计算哈希值方法中有一个无符号右移和异或操作：^ (h >>> 16)，它的作用是什么？
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
无符号右移和异或操作的主要目的是为了让生成的哈希值尽量均匀。
计算哈希桶索引表达式：hash & (length - 1)，通常哈希桶数不会特别大，绝大部分都在 0 ~ 216 这个区间范围内，也即是小于 65536。因此哈希结果值 hash 再和 length - 1 进行与操作时，hash 的高 16 位部分被直接舍得掉了，未参与计算。
那么如何让 hashCode() 结果的高 16 位部分也参与运算从而让得到的桶索引更加散列、更加均匀？可以通过让 hashCode() 结果再和它的高 16 位进行异或操作，这样 hashCode()结果的低 16 位和哈希结果的所有位都有了关联。当 hash & (length - 1) 表达式中 length 小于 65536 时，结果就更加散列。为什么使用异或操作？与 & 操作和或 | 操作的结果更偏向于 0 或者 1，而异或的结果 0 和 1 有均等的机会。
如何实现 hashCode() 结果再和它的高 16 位异或操作？
h >>> 16，将 hashCode() 结果无符号右移，所得结果高 16 位移到低 16 位，而高 16 位都变为 0(h = key.hashCode()) ^ (h >>> 16)，再将 hashCode() 结果和无符号右移的结果进行异或
这样所得结果的低 16 位就和 hashCode() 的所有位相关。当再进行 hash & (length - 1) 运算，length 小于 65536 时，结果就更加散列。
hash & (length - 1)，当 length = 2n 时，hash & (length - 1) 的结果和 hash 值的低 n 位相关。
指定初始化容量
我们知道，在构造 HashMap 时，可以指定 HashMap 的初始容量，即桶数。而桶数必须是 2 的次幂，因此当我们传了一个非 2 的次幂的参数 2 时，计算离传入参数最近的 2 的次幂作为桶数。（注：2 的次幂指的是 2 的整数次幂）
static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}
HashMap 是通过 tableSizeFor 方法来计算离输入参数最近的 2 的次幂。tableSizeFor 方法中使用了 5 次无符号右移和或操作。
假如现在我们有一个二进制数 1xxxxx，x 可能是 0 或者 1。我们来按照上述代码进行无符号右移和或操作：
1xxxxx |= 1xxxxx >>> 1
1xxxxx| 01xxxx，1xxxxx 无符号右移 1 位的结果= 11xxxx，或操作结果
从上述结果看出，无符号右移 1 位然后和原数进行或操作，所得结果将最高 2 位变成 1。我们再将结果 11xxxx 继续进行操作。
11xxxx |= 11xxxx >>> 2
11xxxx| 0011xx，11xxxx 无符号右移 2 位的结果= 1111xx，或操作结果
再进行 无符号右移 2 位然后和原数进行或操作，所得结果将最高 4 位变成 1。我们再将结果 1111xx 继续进行操作。
1111xx |= 1111xx >>> 4
1111xx| 000011，1111xx 无符号右移 4 位的结果= 111111，或操作结果
再进行 无符号右移 4 位然后和原数进行或操作，所得结果将最高 6 位变成 1。我们再将结果 111111 继续进行操作。
111111 |= 111111 >>> 8
111111| 000000，111111 无符号右移 8 位的结果= 111111，或操作结果
再进行 无符号右移 8 位然后和原数进行或操作，所得结果不变，最高 6 位还是 1。我们再将 111111 继续进行操作。
111111 |= 111111 >>> 16
111111| 000000，111111 无符号右移 16 位的结果= 111111，或操作结果
再进行 无符号右移 16 位然后和原数进行或操作，所得结果不变，最高 6 位还是 1。
从上述移位和或操作过程，我们看出，每次无符号右移然后再和原数进行或操作，所得结果保证了最高 n * 2 位都为 1，其中 n 是无符号右移的位数。
为什么无符号右移 1、2、4、8、16位并进行或操作后就结束了？因为 int 为 32 位数。这样反复操作后，就保证了原数最高位后面都变成了 1。
二进制数，全部位都为 1，再加 1 后，就变成了最高位为 1，其余位都是 0，这样的数就是 2 的次幂。因此 tableSizeFor 方法返回：当 n 小于最大容量 MAXIMUM_CAPACITY 时返回 n + 1。
tableSizeFor 方法中，int n = cap - 1，为什么要将 cap 减 1？如果不减 1 的话，当 cap 已经是 2 的次幂时，无符号右移和或操作后，所得结果正好是 cap 的 2 倍。
扩容方法里的位运算
HashMap 的 resize() 方法进行初始化或扩容操作。
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; // 旧的数组的长度（原桶数） int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; // 数组已经初始化了，进行扩容操作 if (oldCap > 0) { // 如果已经到达最大容量，则不再扩容 if (oldCap >= MAXIMUM_CAPACITY) { // 阀值设置为最大 Integer 值 threshold = Integer.MAX_VALUE; return oldTab; } // 未到达最大容量 // 数组容量扩大为原来的 2 倍：newCap = oldCap << 1 // 阀值扩大为原来的 2 倍：newThr = oldThr << 1 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } // 数组未初始化，且阀值大于 0，此处阀值为什么大于 0？？？ // 当构造 HashMap 时，如果传了容量参数，将根据容量参数计算的离它最近的 2 的次幂 // 即数组的容量暂存在阀值变量 threshold 中，详见构造器方法中的语句： // this.threshold = tableSizeFor(initialCapacity); else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; // 数组未初始化且阀值为 0，说明使用了默认构造方法进行创建对象，即 new HashMap() else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // newCap = oldThr; 语句之后未计算阀值，所以 newThr = 0 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) // 根据新的容量创建一个数组 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; // 旧数组不为 null 时表示 resize 为扩容操作，否则为第一次初始化数组操作 if (oldTab != null) { // 循环将数组中的每个结点并转移到新的数组中 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; // 获取头结点，如果不为空，说明该数组中存放有元素 if ((e = oldTab[j]) != null) { oldTab[j] = null; // 头结点 e.next == null 时，表明链表或红黑树只有一个头结点 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; // 如果结点为红黑树结点，则红黑树分裂，转移到新表中 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 否则为链表，将链表中各结点原序的转移至新表中 else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; // (e.hash & oldCap) == 0 时，链表所在桶的索引不变 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } // 否则将链表转移到索引为 index + oldCap 的桶中 else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } // 返回新的数组 return newTab;}
上述代码中，扩容操作使用了左移运算
- newCap = oldCap << 1
- newThr = oldThr << 1
数组容量和阀值均左移 1 位，表示原数乘以 21，即扩容为原来的 2 倍。
当桶中存放的为链表，在进行链表的转移时，if 判断使用了如下位操作
- if ((e.hash & oldCap) == 0)
其中 oldCap 为扩容前数组的长度，为 2 的次幂，也即它的二进制中最高位为 1，其余位都位 0。而每次扩容为原来的 2 倍。
例如原容量为 16，即 oldCap = 10000，扩容后 newCap = 32，即 newCap = 100000。计算链表所在数组的索引表达式 hash & (length - 1)：
-
扩容前，oldCap =
10000length - 1=oldCap - 1=1111index=hash & (length - 1)=hash & 1111- 数组索引下标 index 依赖于 hash 的低 4 位
-
扩容后，newCap =
100000
compareAndSwapObject
位运算的其他应用
不用额外的变量实现两个数字互换
见参考资料中的BitOperationTest，方法reverse通过三次异或操作完成了两个变量值的替换。
证明很简单，我们只需要明白异或运算满足下面规律（实际不止如下规律）：
0a = a，aa = 0；
a b = b a；
a b c = a (b c) = (a b) c；
a b a = b；
假设a,b两个变量，经过如下步骤完成值交换：a=ab,b=ba,a=a^b。
证明如下：
因为a b = b a，又a=ab,b=ba。故b=ba= b (a^b)=a。
继续a=ab，a=（ab) b (a^b)，故a=b。完成值交换。
不用判断语句实现求绝对值
公式如下：(a^(a>>31))-(a>>31)
先整理一下使用位运算取绝对值的思路：若a为正数，则不变，需要用异或0保持的特点；若a为负数，则其补码为原码翻转每一位后+1，先求其原码，补码-1后再翻转每一位，此时需要使用异或1具有翻转的特点。
任何正数右移31后只剩符号位0，最终结果为0，任何负数右移31后也只剩符号位1，溢出的31位截断，空出的31位补符号位1，最终结果为-1.右移31操作可以取得任何整数的符号位。
那么综合上面的步骤，可得到公式。a>>31取得a的符号，若a为正数，a>>31等于0，a0=a，不变；若a为负数,a>>31等于-1 ，a-1翻转每一位。
判断一个数的奇偶性
通过与运算判断奇偶数，伪代码如下：
n&1 == 1?”奇数”:”偶数”
奇数最低位肯定是1，而1的二进制最低位也是1，其他位都是0，所以所有奇数和1与运算结果肯定是1。
* `newLength - 1` = `newCap - 1` = `11111`
* `newIndex` = `hash & (newLength - 1)` = `hash & 11111`
* 新数组索引下标 newIndex 依赖于 hash 的低 5 位
在上述例子中，扩容后，新的数组索引和原索引是否相等取决于 hash 的第 5 位，如果第 5 位为 0，则新的数组索引和原索引相同；如果第 5 位为 1，则新的数组索引和原索引不同。
如何测试 hash 第 5 位为 0 还是为 1？因为 oldCap = 10000，刚好第 5 位为 1，其余位都为 0，因此 e.hash & oldCap 与操作的结果，hash 第 5 位为 0 时，结果为 0，hash 第 5 位为 1 时，结果为 1。
综上所述，扩容后，链表的拆分分两步：
- 一条链表不需要移动，保存在原索引的桶中，包含原链表中满足
e.hash & oldCap == 0条件的结点 - 一条链表需要移动到索引为 index + oldCap 的桶中，包含原链表中不满足
e.hash & oldCap == 0条件的结点