为什么HashMap的容量是2的次方数
- 优化模除运算
// jdk 1.8
// 扰动
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 取模
(n - 1) & hash
HashMap在1.7与1.8中的区别
- 1.7是头插，1.8是尾插
- 1.8优化了hash算法
- resize()逻辑修改，1.7会出现死循环，1.8不会
- 1.8的桶会在链表与红黑树中变换
HashMap初始大小
-
初始大小默认为16
-
也可以指定初始大小，最好指定为2n（2的次幂），如果不是程序还需额外工作将你给的值向上取整值2n
// java8 // Returns a power of two size for the given target capacity. // 这段代码做的事是：将给定cap的第一位1的右侧全部补1，最后再加一即可得到向上取整的2^n static final int tableSizeFor(int cap) { // 这里假设一个cap == 65，1000000，即除最高位以外全部需要补1 int n = cap - 1; n |= n >>> 1; // 1100000 n |= n >>> 2; // 1111000 n |= n >>> 4; // 1111111 // 至此全部1已补齐 n |= n >>> 8; n |= n >>> 16; // 根据观察可以发现：n |= n >>> 1 的结果中至少有1个1，n |= n >>> 2 的结果中至少有4个1 // 所以运行到 n |= n >>> 16 时可以使n中有32位为1 // 由代码：static final int MAXIMUM_CAPACITY = 1 << 30; aka 2^30 HashMap的最大容量 // 所以没有n |= n >>> 32 了 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
threshold
HashMap中的threshold表示可以容纳的最大键值对数量。
对于使用initialCapacity参数的第二和第三中初始化方式，由于HashMap中没有一个用来存储数组长的的字段，initialCapacity会暂时存数在threshold字段上，直至第一次执行put()方法时，对table[]数组进行初始化（一次resize()）时，才根据存储在threshold中的数组长度与负载因子LOAD_FACTOR计算出实际的threshold。
put() / putVal()
- 第一次
put()会先进行一次resize()初始化table和threshold - 1.7为头插，1.8为尾插
- 链表长度≥8 且 数组长度≥64会将链表升级为红黑树
put()后如果size > threshold会进行resize()扩容
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) // 如果没有put()过
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) // 如果该位置还没有元素，直接把给元素作为链表表头表头，i == hash, p == 对应hash链表表头
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode) // 红黑树相关，暂略
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { // 到结尾了（新key）
p.next = newNode(hash, key, value, null); // 1.8尾插，新KV添加到链表末尾
if (binCount >= TREEIFY_THRESHOLD - 1) // static final int TREEIFY_THRESHOLD = 8; // 链表长度≥8时升级为红黑树
treeifyBin(tab, hash); // static final int MIN_TREEIFY_CAPACITY = 64 如果数组的长度 < 64 会取消升级，转而先扩容
break;
}
if (e.hash == hash && // 先比较hash，如果连hash都不一样肯定不是一个元素
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key // 对于key存在的节点，为该key对应的value更新新值，并返回旧值
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) // 检查put()后是否超过threshold大小，超过就扩容
resize();
afterNodeInsertion(evict);
return null;
}
resize()
- 扩容时，如果新数组长度<最大数组长度 且旧数组长度≥16才会更新threshold
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) { // 已经是最大cap了仍然超过了threshold，那么也没办法了，把threshold设为最大，以后就不扩容了
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && // 新数组长度<最大数组长度 && 旧数组长度≥16才会更新threshold
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold // 更新threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold // new HashMap<>()时给了cap的情况，当时将cap暂存在threshold中
newCap = oldThr;
else { // zero initial threshold signifies using defaults //new HashMap<>()时没给了cap的情况
newCap = DEFAULT_INITIAL_CAPACITY;
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 = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 新的桶（数组）
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) { // 遍历旧桶
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = 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
// lo存储位置不变的链表，hi存储位置加了一个oldCap的链表
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) { // 判断最终hash多出来的一个高位是0还是1，0就位置不变，1位置就加一个oldCap
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和hihead接到对应的位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}