之前一直听说HashMap集合要保证为2的整数次幂，最近粗略的研究了一下这种机制的好处。
- 便于计算索引
- 扩容带来的便利
1. 计算索引时
阅读源码，发现了一些有意思的代码：
比如下面的get()调用的getNode()中：
public V get(Object key) {
Node<K, V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods.
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
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 &&// 判断table是否初始化
(first = tab[(n - 1) & hash]) != null) { // ※根据hash计算出table中的索引※
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 红黑树结构
if (first instanceof TreeNode)
return ((TreeNode<K, V>) first).getTreeNode(hash, key);
// 链表结构，遍历链表
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
可以看到第18行有一句tab[(n - 1) & hash]；其中
- n=tab.length //第17行中
- hash = hash(key) //第三行中 put()中传入的参数
再来看一下put()调用的putVal()
/**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K, V>[] tab;
Node<K, V> p;
int n, i;
// 先判断是否为null，避免空指针异常
if ((tab = table) == null || (n = tab.length) == 0) // table 为空或长度为 0 的未初始化状态
n = (tab = resize()).length; // 初始化table内存空间；并记录大小
if ((p = tab[i = (n - 1) & hash]) == null) // put的键将要插入的位置是否有键值对链？（没有就直接插入）
tab[i] = newNode(hash, key, value, null); // 新建一个Node，放在 i = (n-1)&hash的位置
else {
/*.....*/
}
}
同样，在putVal方法中也有同样的代码：tab[i = (n - 1) & hash]；
- n = tab.length
- hash=hash(key)
这样的代码在HashMap中有很多，这句话是什么意思呢？
很明显，[]中的是tab的下标；不难发现这就是HashMap中计算table索引的方式：根据(table.length- 1) & hash(key) = (capacity- 1) & hash(key) 得到键值对在table中的索引；
即:
HashMap使用容量截断hash(key)的后n位作为存放于table数组中的索引
这样做的好处是什么？
不按照插入顺序决定键值对的位置；而是根据hash(key)与HashMap中table的长度来判断插入的位置(这里只是决定了插入到HashMap哪一个索引连接的链表后或红黑树中)；
由于HashMap中table的length必须是2的整数次幂；所以n-1是一串前面全是0后面全是1的二进制数；hash & (n - 1) 之后，得到的数就小于n；保证了不会越界，证明了可以使用这种方式计算索引（虽然可以用i = hash % n 的方式，不过这样容易发生hash碰撞）。
这种机制保证了数组访问的随机访问的同时，还可以直接根据key就找到索引：
- 普通数组：判断数组中是否存在某个对象，获取对象的索引时需要遍历数组；
- HashMap：判断是否存在某个key，只需要根据key的hash值与table的长度就可以计算出键值对的索引。
-
扩容时带来的方便
上面只是这种机制在HashMap运用之一，这种机制还在HashMap扩容时有意想不到的好处。
先来看一下HashMap的存储结构(这里不多解释，网上解释存储结构的有一大堆)
图片来源：https://www.jianshu.com/p/dd06fdb2ff4d
总之：HashMap底层是一个键值对数组，由于可能多个hash(key) 的后n位相同(hash冲突)，所以数组中存放的是一个单链表或者是一颗红黑树。
HashMap使用容量截断hash(key)的后n位作为存放于table数组中的索引；而HashMap每次扩容都是扩容为原来的2倍；那么扩容后HashMap中键值对存放的索引是否会变化？
举个例子：
假设:
- hash(key) = 1100 1101 1001 1111 1110 1000 1011 1101
- capacity = table.length = 2^4 = 16
根据规则扩容前后的index应该为：
- 扩容前：index = hash & (capacity - 1) = ..11101 & 01111 = 01101 = 13
- 扩容后：index = hash & (capacity - 1) = ..11101 & 11111 = 11101 = 29 ( = 13 + 16)
即扩容后的索引有可能会变化；
当table一个索引只有一个结点的时候，直接计算新索引即可，但是通过上面的HashMap存储结构，我们知道HashMap一个索引位置可能存放多个结点；那么如何简单有效的将一个索引上的多个结点存放到新数组呢？这就是2的整数次幂带来的第二个好处：
把旧数据复制到新数组里面。这里面需要注意的有下面几种情况：
- 扩容后，若hash值新增参与运算的位=0，那么元素在扩容后的位置=原始位置
- 扩容后，若hash值新增参与运算的位=1，那么元素在扩容后的位置=原始位置+偏移量:(扩容后的旧位置)。
下面看原理：
-
前提：
- newCap = 2 * oldCap = oldCap << 1 并且 capacity 为2的整数次幂
- 假设:oldCap = 2 ^ n; 则 newCap = 2 ^ (n + 1)
- 并且有:键值对的索引 = hash(key) & capacity 即:截取 hash 的后n-1位为索引
- 注:这里位数从最低位开始算
-
先看扩容前的索引:
- oldCap的二进制第n位为1,其余位为0
- 所以:扩容后的索引 = hash & (oldCap - 1) 为 n-1 位
-
再看扩容后的索引:
- newCap的二进制第n+1位为1,其余位为0
- 所以:扩容后的索引 = hash & (newCap - 1) 为 n 位
再联合起来看:
- 所以:扩容后，计算key的hash值时由原来的n位变为n+1位;多一位
- hash & oldCap = n 位，第n位的值就是hash第n位的值
扩容后计算的索引(截取后n+1-1位)去扩容前索引的差别只有最高位(第n位)不一样
结论:
- hash & oldCap = 0: 则hash第n位为0; 即新索引 = 旧索引
- hash & oldCap = 1: 则hash第n位为1; 即新索引 = 旧索引 + 偏移量(偏移量 = 2^n = 原hash桶长度)
新桶(newTab)可以看做两部分:低2 ^ n位和高2 ^ n位
- 若 hash & oldCap = 0,索引不变,放入低2 ^ n位
- 若 hash & oldCap = 1,索引+2 ^ n,放入高2 ^n 位
所以先把这两种情况的结点分开为两个链表;然后再按照规则放到新链表的低2 ^ n位或高2 ^ n位中指定位置
以上设计都是依托于HashMap保证容量为2的整数次幂这个前提的；
源码如下：分割线下面的代码就是处理一个索引位置删挂着的结点链表的方法；
/**
* 初始化table或扩大table为原来的两倍大小。如果table未初始化，使用保留了
* 初始化容量的成员变量 threshold 对 table 进行分配空间。
*/
final Node<K, V>[] resize() {
Node<K, V>[] oldTab = table; // 记录table的引用
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 记录table.length：HashMap原来的容量
int oldThr = threshold; // 记录原来的阈值threshold
int newCap, newThr = 0; // 新容量，新阈值
/*
* 首先如果超过了数组的最大容量，那么就直接将阈值设置为整数最大值，
* 如果没有超过，就扩容为原来的2倍，用oldThr << 1移位操作来实现
* */
if (oldCap > 0) { // table已经初始化过了
if (oldCap >= MAXIMUM_CAPACITY) { // 已经达到了最大容量，不扩容，直接返回原table
threshold = Integer.MAX_VALUE;
return oldTab;
// newCap = oldCap << 1左移一位，即扩大为两倍
// 判断扩容
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// threshold = capacity * load factor；capacity 扩容为两倍，所以threshold需要扩容为两倍
newThr = oldThr << 1; // double threshold
} else if (oldThr > 0) // 阈值已经初始化了，就直接使用，将初始容量设置为阈值
newCap = oldThr; // 注:如果oldCap=0;oldThr>0 即table 没有初始化，capacity应初始化为当前threshold:oldThr
else { // zero initial threshold signifies using defaults
// 如果oldCap=0；oldThr=0;使用默认值:没有初始化阈值那就初始化一个默认的容量和阈值
newCap = DEFAULT_INITIAL_CAPACITY;
// threshold更新为默认加载因子 * 默认初始化容量
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float) newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
(int) ft : Integer.MAX_VALUE);
}
// 因为threshold是成员变量，而capacity不是成员变量，是计算出来的，所以这里只记录threshold
threshold = newThr; // 更新threshold
// 上面只是计算扩容后的capacity 以及 threshold
// 下面才是真正的扩容 ———— 一个新的table
@SuppressWarnings({"rawtypes", "unchecked"})
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap]; // 用newCapacity扩容
table = newTab;
if (oldTab != null) { // 如果table里有对象
for (int j = 0; j < oldCap; ++j) { // 遍历 oldTab,将oldTab中的值存入newTab
Node<K, V> e;
if ((e = oldTab[j]) != null) { // 当前遍历到的索引位置的值不为null
oldTab[j] = null; // 将原来位置指针置为null,以防止多余指针指向结点
if (e.next == null) // 如果当前索引只有一个结点,直接将这个结点存入newTab
newTab[e.hash & (newCap - 1)] = e; // 根据hash和capacity计算结点的索引
else if (e instanceof TreeNode) // 红黑树
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
/* --------------------------------------------------------------------------------------------*/
/* ------------------------------------I'm a cool divider--------------------------------------*/
/* --------------------------------------------------------------------------------------------*/
else { // preserve order
// 如果索引指向的是长度大于1的链表...
// 将原链表拆分为两个链表,分别放到newTab的 低2^n位 和 高2^n位
Node<K, V> loHead = null, loTail = null; // lo -> low :低位链表头尾指针
Node<K, V> hiHead = null, hiTail = null; // hi -> high:高位链表头尾指针
Node<K, V> next;
// 遍历链表
do {
next = e.next;
if ((e.hash & oldCap) == 0) { // 放入低位的链表
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else { // 放入高位的链表
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// loHead存于原索引
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// hiHead存于原索引加上偏移量(2^n = 原hash桶长度)
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
至于HashMap如何保证容量为2的整数次幂，可以参考另一篇笔记：
HashMap如何保证容量为2的整数次幂？
以上只是我——一个java新手学习时的一点思考与笔记，如果有朋友刷到这篇笔记，并且赏脸看了这篇笔记，发现了有不对的地方，还请不吝赐教。
