HashMap 构造
数组 + 链表 + 红黑树
链表大于 8 转红黑树，红黑树节点数小于 6 退回链表。
寄存的 key-value 的 Node 节点
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
树形构造的 Node 节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}
他的继承构造是这样，能够看到继承了 Node 节点
看懂一条语句
hash & tab.length-1
代码中多处都能够看到这条代码，实际上这条语句只是做了一个取余（%）的动作。一个 & 怎么做的取余的操作：
HashMap 的容量为 2^n其二进制构造如下
任何数 &2^n-1（01111…）其后果都是去 0xxxx，做了疾速取余的操作。后续会看到该条语句频繁呈现
几个外围参数
- Node<K,V>[] table：寄存 Node 的数组
- int size：示意以后 HashMap 蕴含的键值对数量
- int threshold：示意以后 HashMap 可能接受的最多的键值对数量，一旦超过这个数量 HashMap 就会进行扩容
- final float loadFactor：负载因子，用于扩容
- int DEFAULT_INITIAL_CAPACITY = 16：默认的 table 初始容量
- float DEFAULT_LOAD_FACTOR = 0.75f：默认的负载因子
- int TREEIFY_THRESHOLD = 8: 链表长度大于该参数转红黑树
- int UNTREEIFY_THRESHOLD = 6: 当树的节点数小于等于该参数转成链表
初始化办法
指定了具体的容量，以及负载因子的初始化办法。当晓得须要放入的元素的个数时能够先指定防止屡次扩容造成性能节约。
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
外围办法 public V get(Object key)
参数 key，以及该 key 的 hash
先判断数组是否曾经初始化了，以及数组长度。
在判断 tab[(n – 1) & hash]，前文提到的那一条语句，用 key 的 hash 取余数组长度判断数组中的地位是否存在元素。
- 不存在元素
数组中不存在元素，必定没有产生 hash 抵触，那么元素必定不存在 - 数组以后地位存在元素
判断 key 的 hsah 相等并且（key 的地址相等或者 equals 相等）。那么能够确定元素在数组中。 - 数组以后地位存在元素，然而 key 不相等
接下来会去判断数组中以后地位是否存在 next 元素（Node 节点构造），如果有 next 阐明存在链表或者树形构造。
接下来判断 Node 是否是 TreeNode，如果是则依照遍历树形式遍历失去后果，不是则依照遍历链表的模式遍历失去后果。
final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab = table;
Node<K,V> first = tab[(n - 1) & hash];
Node<K,V> e = first.next;
int n = tab.length;
K k;
// 数组是否曾经初始化
if (tab!= null && n > 0 && first != null) {
//table 中是否有节点，key 是否相等
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
//key 不相等，判断是否有 next，并且判断是树的节点还是链表的节点，再以不同的形式去遍历获取
if (e != 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;
}
外围办法 public V put(K key, V value)
put 办法比拟长，分几种状况解析
- 第一次 put 元素，数组还未初始化：调用 resize()初始化数组，间接放入 table 相应地位。(resize 扩容办法很重要)
- table 中该地位没产生 Hash 抵触：结构节点放入 table 中
- 产生 Hash 抵触，先判断 table 中节点元素 key 是否相等，相等则替换 value
- 产生 Hash 抵触，节点是 TreeNode：按红黑树的形式插入节点
- 产生 Hash 抵触，节点是 Node：结构节点按链表的形式插入，并且查看插入后是否达到转红黑树的阈值 8
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab;
Node<K,V> p;
int n;
int i;
// 第一次 put 元素，数组还未初始化
if ((tab = table) == null || (n = tab.length) == 0)
// 调用 resize()初始化数组
n = (tab = resize()).length;
//table 中该地位没产生 Hash 抵触
if ((p = tab[i = (n - 1) & hash]) == null)
// 结构节点放入 table 中
tab[i] = newNode(hash, key, value, null);
else {
// 产生 Hash 抵触
Node<K,V> e; K k;
//table 中节点元素 key 是否相等
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
// 记录下节点的援用，后续替换 E 节点的值
e = p;
else if (p instanceof TreeNode)
// 节点是 TreeNode：按红黑树的形式插入节点
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 节点是 Node，链表状况
for (int binCount = 0; ; ++binCount) {
// 遍历到链表尾部还未发现雷同的 key, 则结构节点插入到链表
if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
// 查看插入后是否达到转红黑树的阈值 8
treeifyBin(tab, hash);
break;
}
// 查看是否有雷同的 key, 有就退出，e = p.next 曾经记录了 E 的援用
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 上述各种状况下，如果不是插入节点的状况下
// 存在 key 雷同的状况下，实现一个值的替换
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
return oldValue;
}
}
// 查看是否须要扩容 存在的数量 >hashmap 容量 * 负载因子就须要扩容
if (++size > threshold)
resize();
return null;
}
外围办法 Node<K,V>[] resize()
最重要的局部来了，也是面试官最喜爱问的 HashMap 的扩容
- 第一次初始化时候调用
- 寄存的键值对的数量 >hashmap 容量 * 负载因子就须要扩容
初始化时候调用 resize
扩容后失去的是一个 Node 数组。因为第一次初始化，必定是不存在链表，红黑树等构造的，以及 Node 节点的。只是对一些属性做了赋值操作，和返回一个空的 Node 数组。
threshold：HashMap 可能接受的最多的键值对数量；如果指定了容量和负载因子，则 threshold = 指定的容量 * 负载因子；
Node<K,V>[] table：寄存 Node 的数组，创立了一个容量为 16（未指定具体容量时，默认为 16）的 Node 数组。
省略局部与第一次初始化无关代码不重要的代码
final HashMap.Node<K,V>[] resize() {
//16*0.75=12
threshold = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
//16
HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[DEFAULT_INITIAL_CAPACITY];
table = newTab;
return newTab;
}
扩容调用 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) {
// 容量和阈值都扩充成两倍
newCap = oldCap << 1;
newThr = oldThr << 1;
}
// 设置阈值属性
threshold = newThr;
// 新建一个是之前两倍容量的大小的 Node 数组
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) {
// 数据须要迁徙，table 相应地位置空
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 {
// 不须要挪动的链表的头尾指针
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);
// 将链表从新放入 table 数组中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
这里次要剖析一下拆分的根据。
当要将链表中的数据进行拆分，并且调配到不同的 table 下标中。能够明确的是，不能因为扩容影响到 get 办法，所以依据 get 办法 key 的 hash 取余容量能够失去如下两张图片。
未拆之前
拆之后
扩容中读懂一行代码
(e.hash & oldCap) == 0
当元素的 hash &oldCap（前文提到过容量为 2^n，其二进制为 1000…）。
看几个例子
5&16 ==0
21&16！=0
69&16 ==0
Hash 值的构造以红色框为核心：能够看成 右边 Y +table 容量 + 左边 X，Y 是容量的偶数倍数，X 小于容量值，从上述例子中能够看进去后果是否为 0 取决于红色框处是 0 还是 1。
- 为 0 后果恒为 0
Y 是容量的偶数倍数扩容后取余为仍旧 0，余数为 X，余数与扩容之前统一，不须要挪动。 - 为 1 时后果不为 0
Y 是容量的偶数倍数扩容后取余为仍旧 0，余数为容量值 +X，扩容后余数与之前不统一，须要挪动，挪动后的地位为容量 +X（之前所在位置的值）。
最初
欢送关注公众号：前程有光，支付一线大厂 Java 面试题总结 + 各知识点学习思维导 + 一份 300 页 pdf 文档的 Java 外围知识点总结！