1 概述
HashMap的底层跟HashTable一样是个哈希表，所有的动作都是围绕着一个Map.Entry<K, V>[] table数组来的。我们姑且称为这个table数组的每一个位置为桶，那么HashMap的结构可以理解为
2 底层原理
2.1 key 所在的桶
- HashMap 通过 hash & (table.length - 1)来定位key在哪个桶， 由于 table.length 是 2^n 所以 table.length - 1 = 2^ - 1
它的二进制一定是末尾 n 个 1, (hash & (table.length - 1)) <= 2^n - 1 必然成立
2.2 扩容
- threshold = capacity * loadFactory; 当 size(key-value对的数量)大于 threshold时,触发调用
resize() - resize()
- 当桶的数量为MAXIMUM_CAPACITY(2^30)时, 直接将threshold设置为Integer.MAX_VALUE 不扩容且阻止下一次扩容
- 当桶的数量大于0且没有达到MAXIMUM_CAPACITY时， 桶的数量double， 如果double后桶的数量仍然小于MAXIMUM_CAPACITY且原来桶的容量不为0，threshold也double
- 当桶的数量为0且threshold大于0时， 将桶的设置为 threshold
- 当桶的数量和threshold都等于0时，使用默认值，桶的数量设定为16， threshold = 16 * 0.75 = 12
- 桶的数量扩充之后，也需要对桶里的元素进行重新分桶
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) {
// 如果桶的数量大于 0
if (oldCap >= MAXIMUM_CAPACITY) {
// oldCap >= 2^30 不扩容
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 假定newCap = oldCap * 2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// newThr也double
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// oldCap = 0 且 oldThr > 0走到这
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// oldCap = 0 且 oldThr = 0走到这, 说明这是一个未初始化的map
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// 设置 threshold 的值，假定为 newCap * loadFactory, 不能超过 Integer.MAX_VALUE
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的重新分桶方法
((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;
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);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
2.3 添加元素 put(Key, Value)
- put(Key, Value)
- 先检查table数组是否初始化，如果没有，调用resize()将桶的数量初始化成 16
- 定位key在哪个桶，如果桶为空，直接加到桶里， 如果key冲突（hash相同且equals返回true），覆盖
- 如果桶已经有元素了
- 桶没有树化且链表长度小于 8，key冲突则覆盖，不冲突就追加到末尾
- 桶没有树化且链表长度等于 8，key冲突则覆盖，不冲突先树化后追加到树里
- 桶已经树化， key冲突则覆盖，否则追加
- 检查容量，是否扩容
- 若覆盖，返回被覆盖的值，否则返回null
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果 table为空或者是长度为0， 初始化table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// n 为resize（）之后tab（table）的长度
// (n-1) & hash 来定位 index（怎么保证 index < n?）
if ((p = tab[i = (n - 1) & hash]) == null)
// tab[index]为空，说明是index这个桶为空，直接添加
tab[i] = newNode(hash, key, value, null);
else {
// p为table[index]存储的Node
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) // 依然是使用 hash相等和equals相等来判断，使用 == 兼容 null
e = p; // key相等
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // p 的类型为treeNode,
else {
// key 与table[index]的key不相等
for (int binCount = 0; ; ++binCount) { // 死循环遍历p
if ((e = p.next) == null) {
// 遍历到末尾
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash); // 链表长度大于8时，树化
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; // 找到需要覆盖的节点
}
}
if (e != null) { // existing mapping for key
// 覆盖并返回原value
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 没找到匹配的key
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
2.4 get(key)
- get(Key) 委托给了下面这个方法，没什么技术含量，先定位key所在的桶，然后比较第一个。
如果第一个key不是，再根据这个桶是否树化，如果没有树化，就是用单向链表迭代比较，如果树化了就调用二叉查找树的search方法
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 && // 根据key的hash定位桶
(first = tab[(n - 1) & hash]) != null) {
// 桶里有元素走到这里
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;
}
// TreeNode里的方法
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
2.5 树化
- 树化 这个就不看细节了，我们知道红黑树是一个二叉查找树，所以避免不了需要比较两个key的大小，在java中如果一个类实现了Comparable接口，
可以很方便地定义两个key的大小，但是如果作为Key的类没有实现这个接口，树化的过程是怎么做的呢？看TreeNode的treeify(Node[])方法- 如果Key实现了Comprable接口，使用这个接口比较
- 如果Key没实现Comprable接口， 静态方法tieBreakOrder(a, b)进行比较
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
// 以下几行代码说明，如果Key的类实现了Comparable接口,使用Compareable接口
// 否则调用默认的方法 tieBreakOrder(k, pk)
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
3 总结
Q1: 为什么桶的数量要设置为 2^n
A1: 对一个普通的长度为l的哈希表，我们分桶的时候需要取模%来定位元素在哪个桶，如果哈希表的长度为 2^n，因为 2^-1 的二进制永远是前面为0后面跟着一串1，这样就可以使用效率更高的 位与& 运算来代替模运算了
Q2: loadFactory的作用是什么？怎么设置？
A2: loadFactory可以在作为构造器参数传入 new HashMap<>(initCapacity, loadFactory), 用来衡量Map的饱满度，因为决定扩容的阈值 threshold = 桶的数量 * loadFactory, 当Map的元素数量大于threshold时，就会触发扩容， 所以loadFactory越大就越不容易触发扩容机制，此时就是用更少的桶存储更多的节点，空间利用率变高，但是由于桶的数量少，分到同一个桶的key就越多，再put和get的效率就越低。相反，如果loadFactory设置地很小，就越容易触发扩容，桶的数量就越多，每个桶的链表长度或树的长度就会越短，也更快达到扩容上限，put和get的效率就会越高，但是因为Map不饱满，空间利用率就很低。所以，当你对Map的性能要求高，而且内存充足的时候，可以把loadFactory设置小一点，反之设置大一点。没有特殊要求的化就用默认的0.75,这是大佬觉得比较均衡的一种策略。
Q3: 为什么要进行树化?为什么是红黑树?为什么不一开始就使用红黑树
A3: 单向链表长度过长的时候，迭代查找的时间复杂度 O(n),使用红黑树的时间复杂度为O(lgn).优先使用链表的原因是，我们期望我们的算法有较少的冲突，而且因为扩容的原因，我们不断增加桶来稀释这种冲突，链表在节点少的时候性能不错，空间利用率高。使用红黑树只是在情况不妙的时候做的备选。
Q4: 在初始化HashMap的时候传入的值是实际初始化桶的数量吗？
A4: 不一定，实际桶的数量永远是2^n, 初始化的时候initCapacity被用来确定初始的threshold。只有在第一次调用put方法时才会真正初始化table数组
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
