本文源码主要基于JDK 1.8 分析
简介
HashMap 主要是用来存放键值对的，是基于哈希表的实现的Map接口，并允许null的值和null键，是常用的Java集合之一。
数据结构
JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。
JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间，具体可以参考 treeifyBin方法。
继承体系结构图
源码解析
重要属性
/** 默认初始容量-必须为2的幂。*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**最大容量，最大为2的30次方。*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/** 默认的装载因子 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/** 当一个桶中的元素个数大于等于8时进行树化*/
static final int TREEIFY_THRESHOLD = 8;
/**当一个桶中的元素个数小于等于6时把树转化为链表*/
static final int UNTREEIFY_THRESHOLD = 6;
/**当桶的个数达到64的时候才进行树化*/
static final int MIN_TREEIFY_CAPACITY = 64;
/* ---------------- Fields -------------- */
/**实际存储数据的数组，又叫作桶（bucket）*/
transient Node<K,V>[] table;
/**作为entrySet()的缓存*/
transient Set<Map.Entry<K,V>> entrySet;
/**元素的数量*/
transient int size;
/**修改次数，用于在迭代的时候执行快速失败策略*/
transient int modCount;
/**扩容阈值，计算方法：threshold = capacity * loadFactor*/
int threshold;
/**装载因子*/
final float loadFactor;说明：
- 容量（capacity）：容量也就是默认的数组长度，也可以说是桶的个数，默认是16，最大是2的30次方，且值必须是2的幂
- 装载因子（loadFactor）：扩容时计算需要用到，默认是0.75f。
- 扩容阈值（threshold）：当实际元素数量 size > threshold 时，会触发扩容操作
resize()； - 树化：当容量达到64且链表的长度达到8时进行树化，当链表的长度小于6时链表化。
内部类
内部类Node
Node 节点是 HashMap 数据存储用到的基本节点，其中Node.hash 为通过 key 计算出来的hashcode值。从Node的结构可以看出Node是一个典型的单向链表结构。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}内部类TreeNode
TreeNode是一个典型的树型节点，其中 prev 是链表中的节点，用于在删除元素的时候可以快速找到它的前置节点。 LinkedHashMap 中的 Entry 节点是一个典型的双向链表节点。
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;
// prev是链表中的上一个节点
TreeNode<K,V> prev; // needed to unlink next upon deletion
// 颜色判断
boolean red;
}
// LinkedHashMap类中的 Entry
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}构造方法
HashMap 一共有4个构造方法：
-
默认无参构造方法
所有的参数都是默认值
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } -
指定初始容量
指定了初始容量，但是使用默认的加载因子
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } -
指定初始容量和加载因子
public HashMap(int initialCapacity, float loadFactor) { // 1.检查初始容量是否小于0 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); // 2.检查初始容量是否大于最大值 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; // 3.检查初始容量是否为0 或者 是否不是数字 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // 4.赋值加载因子 this.loadFactor = loadFactor; // 5.计算并赋值扩容门槛，**扩容门槛为初始容量往上取最近的2的幂** this.threshold = tableSizeFor(initialCapacity); }从最后一段代码可以看出，扩容门槛会被换算成初始容量往上取最近的2的幂，这个很重要，一般人很容易忽略这个点，比如initialCapacity为10的话，计算出来的threshold就是16，但是在后面初始化数组时，threshold字段会回归成扩容阈值的本质，变为capacity * loadFactor。
-
包含另一个Map
public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }
添加元素：put(K key, V value)方法
HashMap 提供给用户的put方法时间调用的是putVal方法
public V put(K key, V value) {
// hash(key) 计算key的hash值
return putVal(hash(key), key, value, false, true);
}在调用putVal的时候首先会调用计算key对应的hashcode方法 hash(Object key)，如果key 为null，那么hash值为0。
/** 计算hash的方法 by：by：[https://jingling.im](https://jingling.im) */
static final int hash(Object key) {
int h;
// 自己的高半区16位和低半区16位做异或，为了混合原始哈希码的高位和低位，以此来加大低位的随机性
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}putVal 方法源码：
/** 添加键值对 by：[https://jingling.im](https://jingling.im) */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 局部变量接收
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1.如果数组还**没有初始化**
if ((tab = table) == null || (n = tab.length) == 0)
// 1.1 调用resize 方法进行初始化
n = (tab = resize()).length;
// 2.如果元素在数组中不存在
if ((p = tab[i = (n - 1) & hash]) == null)
// 2.1 new一个节点，并加入到数组中，(n - 1) & hash 是根据hash计算元素所在的位置
tab[i] = newNode(hash, key, value, null);
else {
// 3. 元素已经存在与数组中了
Node<K,V> e; K k;
// 3.1 如果已经在数组中的元素hash和put元素的hash相等 && key的值相等
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
// 3.1.1 取出旧值，拿到其引用，e为数组桶中的第一个元素
e = p;
else if (p instanceof TreeNode)
// 3.2 如果之前数字中的节点是属于树节点
// 则调用树节点的putTreeVal方法
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 3.3 hash冲突了，也不是树节点
// 遍历e节点这个单向链表，binCount用于记录这个冲突链表的长度
for (int binCount = 0; ; ++binCount) {
// 3.3.1 如果冲突链表所在的最后一个元素，也就是它的下一个节点为空
if ((e = p.next) == null) {
// 3.3.1.2 new一个新的节点
p.next = newNode(hash, key, value, null);
// 3.3.1.3 如果链表的长度大于8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 3.3.1.4 链表树化
treeifyBin(tab, hash);
break;
}
// 3.3.2 如果冲突的元素在冲突链表中找到了，则直接退出遍历链表
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 遍历到冲突元素所在链表的最后一个元素
p = e;
}
}
// 3.4 如果已经存在的key所处的元素不为空 by：[https://jingling.im](https://jingling.im)
if (e != null) { // existing mapping for key
// 3.5.1 取出该元素的旧值
V oldValue = e.value;
// 判断是否要替换旧值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 访问后回调，在LinkedHashMap中用到
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// 4. 到了这里，说明元素之前不存在，是新put的元素，记录修改次数
++modCount;
// 5.判断是否余姚扩容
if (++size > threshold)
resize();
// 访问后回调，同afterNodeAccess，，在LinkedHashMap中用到
afterNodeInsertion(evict);
// 6. 新put的元素返回null
return null;
}添加元素过程总结：
-
计算 key 的 hash 值
-
检查数组 table 是否已经初始化，如果没有则调用
resize()方法进行初始化 -
根据 key 的 hash 值计算索引，查看索引位置元素是否已经存在
-
索引位置元素为空
则 new 一个新的节点，并加入到数组 table 中
-
索引位置元素不为空
2.1 如果 hash 值相等，并且 key 的值相同，则拿到数组 table 索引位置元素的引用
2.2 如果以存在是节点是树节点，则把新 put 进来的节点加入到树节点中去（by：https://jingling.im）
3.3 如果 hash 值相等，但是 key 的值不相等(出现了hash冲突)，则遍历冲突链表，如果在遍历的过程中找到了hash和key都相等的节点，则取出该节点的引用，退出遍历，知道遍历到链表的尾节点，然后把新 put 的节点插入到链表尾部，如果链表的长度大于8，会执行树化的逻辑
3.4 判断是否要替换旧值，并返回旧值
-
-
新put的元素，记录修改次数，判断是否要扩容，返回null
初始化&扩容：resize()方法
resize()方法在put时初始化，也会在put时判断是否会扩容，都会调用这个方法。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
// 数组的长度，初始化时是0 by：[https://jingling.im](https://jingling.im)
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 本次需要扩容的阈值
int oldThr = threshold; // 默认是16
int newCap, newThr = 0;
if (oldCap > 0) { //第一次put元素时oldCap为0
if (oldCap >= MAXIMUM_CAPACITY) {
// 直接赋值为最大容量
threshold = Integer.MAX_VALUE;
return oldTab;
}
// newCap = oldCap << 1 表示新的容量为老的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //新的容量没到最大值，老的容量也大于默认的初始值16
// 扩容阈值也是老的阈值2倍
newThr = oldThr << 1; // double threshold
} else if (oldThr > 0) // initial capacity was placed in threshold
// 新容量赋值为旧扩容阈值
newCap = oldThr;
else { // 0：初始阈值，使用默认值
// 默认初始化容量，值：16 by：[https://jingling.im](https://jingling.im)
newCap = DEFAULT_INITIAL_CAPACITY;
// 默认扩容阈值： 0.75 *16 = 12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) { // 如果扩容门槛为0，还没有计算
float ft = (float)newCap * loadFactor;
// 计算扩容门槛：= 新的容量*扩容因子，但是且最大值为Integer.MAX_VALUE
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
}
// 重新赋值新的扩容阈值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// new 一个新的容量数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// HashMap的table赋值为新的数组
table = newTab;
if (oldTab != null) { // 老数组不为空，说明是扩容，需要搬数据；如果是初始化不会进入到if分支，直接返回数组
// 遍历老的数组
for (int j = 0; j < oldCap; ++j) {
// e为每次遍历的节点
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 将老的数组索引位置上的元素赋值为null，便于GC
oldTab[j] = null;
if (e.next == null)
// 遍历的节点上没有链表，说明之前的索引位置j上没有冲突链，直接把当前元素插入到新的table中。
// e.hash & (newCap - 1) 是计算新的索引位置，继续遍历老数组下一个元素
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 如果元素是树节点，则把这颗树打散成两颗树插入到新桶中去
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// e.next不为空，且不是树节点，说明hash冲突了，还是链表
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 遍历冲突链表，拆分冲突的链表
// 假如老的容量是8，新的容量是16，现在在第3个位置上hash冲突了，冲突链表上的元素有：3、4、5、6、7
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;
// 拆分后的链表：3、5、7 还是原来的j位置上 by：by：[https://jingling.im](https://jingling.im)
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// 拆分后的链表：4、6在新的位置上，新的索引位置为j+oldCap, 即为：3+8 = 11
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// 返回新的数组table
return newTab;
}初始化&扩容过程总结：
-
计算容量和扩容阈值
说明一下，HashMap的容量并不是构造时指定多少就是多少，而是计算出来的，且必须是2的幂，所以传入的如果不是2的幂，会向上找最接近的一个2的幂的数，且不能超过最大值
1.1 如果老的容量等于0，说明此次操作是初始化容量计算规则：
如果构造方法指定了容量，则初始化的容量为计算后的容量大小(必须是2的幂)，如果构造方法没有指定(oldThr == 0)，则全部使用默认值。
1.2 如果老的容量大于0，说明已经初始化过了，执行扩容计算规则：
新的容量计算：newThr = oldThr << 1，也就是乘以2。
-
new 一个新的数组赋值为HashMap table 数组，大小为步骤1计算的容量
-
如果老的 table 不为空，则说明是扩容
-
遍历老的数组
-
取出老的数组索引位置上的节点e，并将老的数组索引位置上的数据置为null
-
如果节点e是一个普通节点，不是链表(e.next ==null)
- 计算新的索引位置，并将节点e加入到新的数组中
-
如果节点e是一个树节点
- 则把这颗树打散成两颗树插入到新桶中去
-
如果这个节点是链表
-
需要遍历链表，并拆分成2个链表，分别加入到新的数组中
假如老的容量是8，新的容量是16，现在在第3个位置上hash冲突了，冲突链表上的元素有：3、4、5、6、7。
拆分后的链表：3、5、7 还是原来的j位置上，拆分后的链表：4、6在新的位置上，新的索引位置为j+oldCap, 即为：3+8 = 11
-
-
-
返回新的数组newTab
获取元素：get(Object key)方法
public V get(Object key) {
Node<K,V> e;
// hash(key) 计算key的hash值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
// 根据hash值查找节点数据并返回节点
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// (n - 1) & hash 是计算这个hash所在的索引位置
// 数组不为空，且长度大于0，并且索引位置上的元素不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
// 如果元素索引位置上第一个元素就满足 hash值相等，key 相等，则直接返回该节点元素
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);
}
}
// 没有找到，返回null
return null;
}查找元素过程总结：
- 计算key值的hash值
- 根据hash值计算索引，计算方法：
(n - 1) & hash - 索引位置的元素不为空，且如果hash值和key值都符合条件，则直接返回该元素
- 如果3不满足且该节点是树节点，则按照树查找的方式查询
- 如果元素是链表，则遍历链表，判断hash值和key值
- 如果都没有找到，返回null
删除元素：remove(Object key)方法
public V remove(Object key) {
Node<K,V> e;
// hash(key)计算key的hash值
return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
// matchValue：true,仅在值相等时删除
// movable：如果为false，则在删除时不要移动其他节点
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
// index：根据hash值计算元素所处在的索引
// p：索引位置index上的元素，后续会更新为目标节点的上一节点
// 如果table不为空，且长度大于0，并且所处索引位置上的元素不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
// node：找到的目标元素，必须hash值相等，key相等的元素
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode).
// 从树中找
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// 从链表中找到目标元素
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 找到了要删除的目标节点，并且不为空
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
// 如果节点属于树节点，则从树节点中删除节点
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
// 如果节点是索引位置上的第一个节点，则直接将索引位置上赋值成当前节点的下一个节点，不用考虑下一个节点是否为空
tab[index] = node.next;
else
// 说明找到的节点是在冲突链表上，并且不是在头结点上，则直接删除该节点
p.next = node.next;
// 记录修改次数和实际数组大小
++modCount;
--size;
// 后置处理
afterNodeRemoval(node);
// 返回删除的节点
return node;
}
}
// 没有找到要删除的key，返回null
return null;
}删除元素过程总结：
- 计算需要删除key的hash值
- 根据hash值计算索引 ：
(n - 1) & hash - 如果索引位置上元素为空，直接返回null
- 索引位置上的元素有三种可能：只有一个元素，是链表，是树
- 如果是树节点，则按照树的方式删除节点
- 如果只有一个元素，直接将数组索引位置上置为null
- 如果是链表，按照链表的方式删除节点
- 记录修改次数和修改实际数组大小，并返回删除的节点
涉及到树相关的操作
①树化：hash冲突后的链表长度大于8时，调用treeifyBin(tab, hash)方法判断是否需要树化：
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 1. 如果数组为空或者数组的**实际长度小于64**，则直接调用扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// 扩容
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 树化操作，e: tab[index = (n - 1) & hash]) 取出数组索引位置上的第一个元素
TreeNode<K,V> hd = null, tl = null; // hd 为头节点（head），tl 为尾节点（tail）
do {
// 循环将链表上的每个节点包装成树节点
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
// 真正执行树化操作，将树形链表转换成红黑树
hd.treeify(tab);
}
}
// 形成从该节点链接的节点树。
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;
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);
}②扩容时，如果冲突的节点已经是树节点，需要拆分冲树，调用方法：e.split(this, newTab, j, oldCap)
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// 重新链接到lo和hi列表，保留顺序
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) { // 如果 loHead 不为空，且链表长度小于等于 6，则将红黑树转成链表
if (lc <= UNTREEIFY_THRESHOLD) // 红黑树转链表阈值 6
tab[index] = loHead.untreeify(map); // 反树化
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map); // 反树化
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}如果拆分后的树节点数小于 6，需要反树化：
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}③添加元素到树中：putTreeVal 方法
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}④从树种查找节点getTreeNode(int h, Object k)
final TreeNode<K,V> getTreeNode(int h, Object k) {
// 从树的根节点开始查找
return ((parent != null) ? root() : this).find(h, k, null);
}
// 找到根节点
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
// 从树中查找节点
// h：查找的目标hash
// k：查找的目标key
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)))
// 查找目标已经找到，hash相等，并且key相等，直接返回
return p;
else if (pl == null)
// hash相等，但是key不相等，左子树为空，就从右子树上查
p = pr;
else if (pr == null)
// hash相等，但是key不相等，右子树为空，就从左子树上查
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
// 通过compare方法比较key值的大小决定使用左子树还是右子树
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
// 尝试从右子树中查找
return q;
else
// 继续从左子树查找
p = pl;
} while (p != null);
// 树遍历完了，没有找到返回null
return null;
}快速失败
因为HashMap是非线程安全的容器，也就是说，多线程访问的时候会有问题，比如一个有一个线程在遍历Map，每遍历一项，执行某个操作（假设耗时2秒），此时另外一个线程对Map做了修改（比如删除了某一项），这个时候就会出现数据不一致的问题，此时HashMap发现这种情况，读线程就会抛出ConcurrentModificationException，防止继续读取脏数据，这个过程叫做快速失败。
实现快速失败，就是使用HashMap中的modCount变量，该变量存储的是map中数据发生变化的次数，每发生一次变化，则modCount加一，比如put操作后modCount会加1；一个线程如果要遍历HashMap，会在遍历之前先记录modCount值，然后每迭代一次（访问下一个元素）时，先判断modCount值是否和最初的modCount是否相等，如果相等，则证明map未被修改过，如果不相等，则证明map被修改过，那么就会抛出ConcurrentModificationException，实现快速失败。
比如HashMap.forEach()方法：
public void forEach(BiConsumer<? super K, ? super V> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount; // 遍历前先记录了modCount
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key, e.value);
}
if (modCount != mc) // modCount 发生了变化，抛出异常
throw new ConcurrentModificationException();
}
}HashMap 总结
- HashMap 的容量要求必须是2的幂，如果传入的初始容量不是2的幂就向上取第一个2的幂作为初始容量
- HashMap 索引计算方法为
(n-1) & hash，n代表数组的长度，hash为key经过计算的hash值 - HashMap 当实际存储容量大于容量*装载因子（
size > threshold）时会触发扩容，扩容机制都是在原容量上翻倍（左位移1位） - HashMap 非线程安全，遍历的时候如果有其他线程修改了HashMap 遍历会抛出异常（ConcurrentModificationException）
- 当出现hash冲突的时候，用的是链表或红黑树来存储冲突元素
- 只有当HashMap的table数组长度大于等于64并且冲突链表的长度大于等于8的时候，冲突链表才会转换成红黑树，小于等于6的时候会由树转化成链表，中间有个差值7作为缓冲，避免不停的插入删除元素时频繁的发生转换。
- by：https://jingling.im
HashMap 常见问题
- HashMap 可以put 进去key为 null 的值吗？ 可以，只不过计算出来的hash为0，详见本文 put() 方法的执行过程。
- HashMap 使用哪种方法来解决哈希冲突（哈希碰撞）？ HashMap 使用链表和红黑树来解决哈希冲突，详见本文 put() 方法的执行过程。
- HashMap 不用红黑树，用二叉查找树可以吗？ 可以。但是二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了），遍历查找就会非常慢。
- 为什么冲突链表长度大于等于8会转换成红黑树，小于等于6才转换成链表，而不是7呢？ 7作为缓冲，避免出现一个线程不停的插入删除元素时，频繁的发生树化和链表化的操作，出现这种情况时效率就会非常低下。红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡。
- HashMap 的扩容为什么是 2^n ？ 这样做的目的是为了让散列更加均匀，从而减少哈希碰撞，以提供代码的执行效率。还有一个就是代码里面写的是位移操作, 计算效率更高。
- HashMap 初始化时传10000，然后put 1w条数据的时候会扩容吗？ 传入的初始化容量并非是HashMap的实际容量，通过查看构造方法得知，容量必须是2的幂，1w向上取第一个2的幂是16384，默认的加载因子是0.75，所以首次触发扩容的容量是16384*0.75 = 12288，所以这时候并不会扩容
- Hash冲突的链表长度大于8之后一定会转换成树吗 ？ 不一定，必须还要达成条件数组的实际长度达到64，才会执行树化操作。
- by：https://jingling.im