树化：treeifyBin
链表树化为红黑树，要同时满足两个条件：
- 链表长度大于等于 8，也就是属性 > TREEIFY_THRESHOLD
- table 数组长度大于等于 64，也就是属性 > MIN_TREEIFY_CAPACITY
查看该 treeifyBin 方法源码便知，如下：
final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; // 若数组长度 < 64，则调用 resize 进行扩容而不是进行树化 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; do { // 将链表中的每个 Node -> TreeNode // 将 TreeNode 从头到尾的顺序组装成双向链表的结构 > prev、next， 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); } }
该方法执行流程如下：
- 判断当前数组的长度是否大于 64，若小于，则调用 resize 方法优先扩容数组，而不是进行树化操作
因为当 table 数组容量比较小时，键值对节点 hash 碰撞率可能会比较高，进而导致链表长度较长。这个时候应该优先扩容，而不是立马树化
- 将有 hash 冲突的链表 Node 节点，以从头到尾的顺序转换为 TreeNode，最终形成一个双向链表
- 以双向链表中的首个元素 > TreeNode，调用 treeify 方法完成最后的树化逻辑
treeify 方法在这里就不继续往下分析了，它会以红黑树的数据结构特征进行组装
性质1：结点是红色或黑色
性质2：根结点是黑色
性质3： 所有叶子都是黑色。（叶子是NIL结点
性质4：每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
性质5： 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点
// LinkedHashMap.Entry extends HashMap.Node<K,V>，拥有 next 指针 > 后继节点 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // 父节点 TreeNode<K,V> left; // 左节点 TreeNode<K,V> right; // 右节点 TreeNode<K,V> prev; // 前驱节点，跟 next 属性相反的指向 // 左旋 static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) // 右旋 static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) // 树化 final void treeify(Node<K,V>[] tab) // 树退化为链表 final Node<K,V> untreeify(HashMap<K,V> map) // 查找树节点 final TreeNode<K,V> getTreeNode(int h, Object k) // 拆分红黑树 final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) // 删除树节点 final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) // ...... }
红黑树节点不是以对象指针地址作为节点标识的，而是通过节点的哈希值、键值来确定节点位置的
扩容：resize
在执行 putVal、treeifyBin 方法时都调用了 resize 方法，进行数组的扩容的操作；同时你也可以发现在创建 HashMap 实例时并没有马上创建 table 数组，其实它采用懒加载的形式等到 putVal 方法调用时才去创建 table 数组。
HashMap 每次扩容都会新建一个 table 数组，长度、容量阈值都会变为原来的两倍，然后把原数组重新映射到新数组上，先来阅览它底层源码是如何实现的，如下：
/** * 初始化 table 或双倍扩容 table 大小 * 若 table 为空，以初始容量大小分配给 table否则，因为我们是以 2 次幂扩容的， * 原有的节点下标要么与之前的一样，要么就以 2 次幂的偏移下标落在新的 table 中 * @return the table */ final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; // 1、若 oldCap 数组长度大于 0，说明 table 已经初始化过 if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // << 1 左移一位代表扩充 2 倍大小 // 按当前 table 数组长度 2 倍进行扩容，阈值也会变为原来的 2 倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } // 2、若 threshold 阈值大于 0，说明调用了有参构造方法，但数组未初始化 else if (oldThr > 0) // initial capacity was placed in threshold // 将当前阈值，设置为数组初始化容量大小 newCap = oldThr; // 3、若 oldCap、threshold 都小于 0，说明调用了无参构造方法，数据并未初始化 else { // zero initial threshold signifies using defaults // 初始化容量：16、初始化阈值：16 * 0.75=12 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"}) // 创建新的 table 数组，数组初始化也是在这里完成的。 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; // 若旧 table 数组不为空，遍历旧数组的元素重新映射到新的 table 数组中 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; // 1、当前数组元素节点非链式结构，将其重新计算放入到新数组中 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; // 2、当前数组元素节点是红黑树结构，将红黑树进行拆分 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 3、当前数据元素节点是链式结构，rehash -> 重新映射放入到新数组中 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; // e.hash & oldCap ==0 > 索引位置不变 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } // e.hash & oldCap !=0 > 改变索引位置 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; }
resize 方法执行分为几个步骤，如下：
- 首先判断 table 数组长度，若大于 0 说明数组已经被初始化过，在不超出最大长度：MAXIMUM_CAPACITY = 1 << 30 情况下，那就按当前 table 数组长度的 2 倍进行扩容，阈值也变为原来的两倍
- 若 table 数组未被初始化过，threshold 阈值大于 0 情况下，说明调用了 >
public HashMap(int initialCapacity) ｜ public HashMap(int initialCapacity, float loadFactor) 有参构造方法，那么就将数组大小设置为 threshold 阈值 - 若 table 数组未被初始化过，threshold 为 0 情况下，说明调用了 > public HashMap() 无参构造方法，那么就将数组大小设置为 16，阈值设置为 16 * 0.75 = 12.
- 接下来，判断旧数组是否为空，不为空说明不是第一次初始化，要将旧数组的所有元素存入到新数组中，遍历旧数组中每一个元素节点，会分为以下几步进行判断
1、当前元素节点非链式结构，通过
e.hash & (newCap - 1)公式计算好对应的下标，将其放入到新数组中2、当前数组元素节点是红黑树结构，进行红黑树拆分
3、当前数据元素节点是链式结构，通过
e.hash & oldCap) == 0公式确认当前链式上的节点索引位置是否要发生变化
- 遍历旧数组所有的 Bucket 时，首先判断当前的 Bucket 是否为空，若不为空，分为以下几部分进行
1、e.next == null 说明当前是普通数组结构， 通过
e.hash & (newCap - 1)公式计算好数组下标，存入到扩容的新数组中当 e.next 指向的内容不为空时，说明当前 bucket 是链式结构，又可能是红黑树的结构
2、若当前 bucket 是红黑树结构，调用 split 方法进行红黑树的拆分，当链表长度小于 6 时，会调用 untreeify 方法将树转换为单向链表结构，也有可能会重新调用 treeify 方法生成新的红黑树
3、若当前 bucket 为单向链表结构，从前到后组装好链表，维持原有的链表顺序，同时会通过
e.hash & oldCap ==0公式计算出来一个结果为 0 或不为 0，为 0 时继续存放在原有的数组 bucket 中，不为 0 将其迁移一个旧数组长度的步长，最终存放到新的数组 bucket 中
到这里，resize、putVal 方法都已经分析完毕，在 putVal 方法中讲到了尾插法，在这里说到了会重新映射链表节点所在的位置，在 HashMap 1.7、HashMap 1.8 上有着不同的处理方式，如下：
- 插入元素方式不同：HashMap 1.7 是在链表头部插入元素的，在多个线程同时进行插入时，会导致链表节点的顺序错乱，甚至形成环形引用，导致死循环问题；HashMap 1.8 是在链表尾部插入元素的，虽然避免了链表顺序错乱的问题，提高了一定的安全性，但它为了提高性能引入了红黑树结构，毕竟它的一些操作都是未加锁的，所以导致多线程环境下链表转换为红黑树时会发生死循环问题
JDK 8u40 及以后的版本中得到了解决。修复的方法是引入了一个额外的状态标记，确保只有一个线程进行链表到红黑树的转换，其他线程会等待转换完成后再进行操作，避免了死循环的问题
- 扩容时计算链表索引方式不同：在扩容阶段，HashMap 1.7 是一个个去计算链表元素的 hash 值从而重新映射元素索引的 > indexFor(e.hash, newCapacity)；HashMap 1.8 计算链表元素时，先通过
hash & oldCap计算后的值进行判断，若为 0 索引位置则不变，不为 0 索引位置会发生改变 > 新索引 = 原索引 + 旧数组长度.
因为扩容时使用的是 2 的幂次 > 长度扩大为原来的 2 倍，所以元素的位置要么在原来的位置，要么在原位置的基础上再移动 2 次幂的位置；因此，在扩容时，不需要再像 HashMap 1.7 实现的那样去重新计算 hash，只需要观察 hash 值与原数组长度进行位运算以后是否为 0 就可以了，为 0 代表索引不变，不为 0 索引变成原索引+ oldCap
获取元素：get
HashMap 查找元素是非常快的，查找一个元素首先要知道 Key hash 值，在 HashMap 中是通过自定义实现的 hash 方法来计算哈希值，接下来看具体的获取元素源码：
public V get(Object key) { Node<K,V> e; // hash(key) 不等于 key.hashCode // hash(key) > h = key.hashCode()) ^ (h >>> 16 return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { // 指向 table 数组 Node<K,V>[] tab; // first 指向数组中对应下标的第一个节点，e 指向下一个节点 Node<K,V> first, e; // n：数组长度 int n; K k; // (n - 1) & hash -> 通过数组长度 -1 和 hash 值作位运算，得到在数组中的索引位置 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)))) return first; if ((e = first.next) != null) { // 若 first 为红黑树结果，调用查找方法 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; }
下面来分析一下查找元素的方法流程：
- 首先通过自定义 hash 方法计算出 Key 哈希值，计算出所在数组中的索引
- 判断该数组中的索引是否存在节点数据，若没有则返回 null，代表查找不到指定的元素
- 若有的话，首先取出首节点 first 进行 hash 比对，比对成功就说明是要找的元素，直接返回
- 获取首节点的下一个节点，判断当前链表节点是否为红黑树结构，若是红黑树，则调用红黑树的方法去查找元素
- 若不是红黑树，说明它就是简单的链式结构，则依此向后遍历节点，挨个比对进行元素的查找
删除元素：remove
HashMap 删除元素也并不复杂，首先通过 Key 生成对应的 hash 值，定位到数组中对应索引的元素，最后根据不同的结构执行对应的删除操作，该方法源码如下：
public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { // 指向 table 数组 Node<K,V>[] tab; // 待删除元素所在的节点信息 Node<K,V> p; // 数组长度、删除元素对应的下标 int n, index; // 数组不为空、数组长度大于 0、删除元素在数组中不为空 // 1、定位到所在数组中的索引元素 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node<K,V> node = null, e; K k; V v; // 2、匹配到具体要删除的节点 > 普通数组结构、链式结构、红黑树结构 // 这里可能只是普通的数组结构元素，非链式结构 // 传入的键 hash 与定位的当前数组索引元素 hash 一致，则将 p 指向 Node if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; // p.next 不为空说明是链式结构 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); } } // 3、删除节点，会进行链表、红黑树修复的操作 // matchValue：true > 代表值必须完全匹配才删除、false > 只有 Key hash 值匹配即可删除 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; } } return null; }
下面来详细分析一下具体的删除元素过程，如下：
- 通过数组长度、Key hash 值，
(n - 1) & hash计算得到数组对应下标，若不存在对应元素，则返回 null，存在时则赋值给待匹配指针节点 p - 根据指针节点 p，区分不同的结构：数组结构、红黑树结构、链式结构
数组结构：p 所在元素的 Key hash 值与传入的 hash 完全匹配，即 p 节点就是要删除的节点元素
红黑树结构、链式结构的前提是 p.next 所指向的元素不为空
红黑树结构：通过红黑树查找的方法 getTreeNode 定位到要删除的红黑树节点元素
链式结构：依此向下取 next 指针后继节点元素，进行 hash 值匹配，找到要删除的链式节点元素
- 若定位到的删除元素不为空，执行删除节点的操作，先判别该节点结构的类型
红黑树结构：调用红黑树 removeTreeNode 方法执行删除操作，该方法内部可能因为节点变更，会发生变色、左旋、右旋等操作来保证红黑树的平衡结构
数组结构：tab[index] = node.next，由于 node 节点是普通数组元素，它的 next 指针肯定是为空的，将它的值赋值给数组索引所在处，那么该元素就已经处于删除的状态了
链式结构：p.next = node.next，在定位链式结构要删除的元素节点 node 时，p 指针其实就是 node 的前驱节点，通过此操作可以把删除节点空悬出来，即没有任何的节点引用再指向它
遍历元素：keySet、entrySet 方法
在实际开发中，HashMap 遍历操作（keySet、entrySet）也是非常常用的，但是当我们在遍历 HashMap 时进行删除节点时，会抛出 ConcurrentModificationException 异常
在使用 keySet、entrySet 遍历时，有所不同，keySet 是获取所有的 Key 返回 > Set 集合，entrySet 是获取所有的 Key、Value 返回 > Map.Entry 集合，如下：
HashMap<String, Integer> map = new HashMap<>(); map.put("1", 1); map.put("2", 2); map.put("3", 3); for (String key : map.keySet()) { if ("2".equals(key)) { map.remove("2"); } } for (Map.Entry<String, Integer> mapEntry : map.entrySet()) { String key = mapEntry.getKey(); Integer value = mapEntry.getValue(); if ("2".equals(mapEntry.getKey())) { map.remove(mapEntry.getKey()); } }
但是不管使用 keySet 或 entrySet 遍历，在里面调用 remove 方法删除节点，都会抛出 ConcurrentModificationException 异常，这就是前面所说的 fail-fast 快速失败机制，可以追踪它对应的源码，如下：
// keySet > 遍历方式 public final void forEach(Consumer<? super K> action) { Node<K,V>[] tab; if (action == null) throw new NullPointerException(); if (size > 0 && (tab = table) != null) { int mc = 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); } if (modCount != mc) throw new ConcurrentModificationException(); } } // entrySet > 遍历方式 public final void forEach(Consumer<? super Map.Entry<K,V>> action) { Node<K,V>[] tab; if (action == null) throw new NullPointerException(); if (size > 0 && (tab = table) != null) { int mc = modCount; for (int i = 0; i < tab.length; ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) action.accept(e); } if (modCount != mc) throw new ConcurrentModificationException(); } }
上面两种方式，都会判断 modCount != mc 是否相等，它用来表示集合被修改的次数，修改指的是插入节点或删除节点，可以回去看看上面插入删除的源码，在最后都会对 modCount 进行自增
当我们遍历 HashMap 时，每次遍历下一个节点时都会对 modCount 进行判断，若与原来的值不一致，则说明集合被修改过了，然后就会抛出异常，这是 Java 集合的一个特性，我们这里以 keySet 为例，所以我们在开发中要移除节点时，不得不使用迭代器 Iterator 进行节点的移除操作
以 EntrySet 为例，EntrySet#iterator 方法主要是实例化一个 EntryIterator 返回，在它内部其实是继承至 HashIterator 抽象类来操作节点的，源码如下：
abstract class HashIterator { Node<K,V> next; // 下一个要返回的 Entry 节点 Node<K,V> current; // 当前 Entry 节点 int expectedModCount; // 为了防止 fast-fail int index; // current slot HashIterator() { expectedModCount = modCount; Node<K,V>[] t = table; current = next = null; index = 0; if (t != null && size > 0) { // advance to first entry do {} while (index < t.length && (next = t[index++]) == null); } } public final boolean hasNext() { return next != null; } final Node<K,V> nextNode() { Node<K,V>[] t; Node<K,V> e = next; // 遍历时判断 if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); if ((next = (current = e).next) == null && (t = table) != null) { do {} while (index < t.length && (next = t[index++]) == null); } return e; } public final void remove() { Node<K,V> p = current; if (p == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); current = null; K key = p.key; removeNode(hash(key), key, null, false, false); // 重新赋值 expectedModCount = modCount; } }
在初始化 HashIterator 时，会把 modCount 变量值赋值给 expectedModCount，在删除元素时会重新进行赋值，然后通过迭代器遍历时会对比 modCount、expectedModCount 是否相同，在这里，迭代器其实就是维护了一个 expectedModCount 变量来确保集合移除的操作与遍历时是同步进行的，当然，这只能是确保在单线程的情况下执行是安全的
最后总结一点，在遍历时的顺序与插入顺序不一致情况是如何的？
遍历：通过以上 HashIterator 源码可以看出，从前到后遍历数组 bucket，依此从数组中找到包含节点的 bucket，若该数组 bucket 不为空，则一个一个遍历该 bucket，直至该 bucket 为空才直接遍历下一个数组 bucket，直到遍历结束，从遍历上来说，可以看出它是顺序性的取出节点数据的
插入：插入元素时，它是先让通过 Key hash 值定位到具体的数组 bucket，若该数组 bucket 不为空，说明 hash 冲突了，则以链表的结构存入元素进去；若为空，新建一个数组 bucket，存入当前元素；最终，会由于链表过长 & 数组长度过长，形成红黑树结构
总结
该篇博文，主要分析 HashMap 类所使用的数据结构，基于数组、链表、红黑树，说到了它的初始容量 initial capacity、负载因子 load factor 等核心属性，重点分析了该类的一些核心方法：tableSizeFor > 阈值如何计算、putVal > 插入元素如何懒加载扩容以及数组转换为链表，链表又是如何转换为红黑树结构的、resize > 在底层是如何基于 2 次幂实现数组扩容的以及链表结构的形成、红黑树的转换操作，最后，简要分析了获取元素、删除元素、遍历元素时移除元素的 fast-fail 快速失败机制是如何产生的。
如果觉得博文不错，关注我 vnjohn，后续会有更多实战、源码、架构干货分享！
推荐专栏：Spring、MySQL，订阅一波不再迷路
大家的「关注❤️ + 点赞👍 + 收藏⭐」就是我创作的最大动力！谢谢大家的支持，我们下文见！
