深入解析Java HashMap的高性能扩容机制与树化优化
Java中的HashMap是一个基于哈希表实现的键值对（key-value）存储数据结构。它属于Java Collections
Framework的一部分，用于高效地存储和检索数据。以下是对Java HashMap的一些详细探讨：
基本特性
- 键值对存储：HashMap存储键值对，每个键对应一个值。键和值都可以是任意类型的对象。
- 键的唯一性：HashMap中的键是唯一的，即不允许有重复的键。若尝试存储一个已经存在的键，其对应的值将被新的值替换。
- 无序存储：HashMap不保证键值对的顺序，这意味着存储的顺序与遍历的顺序可能不同。
主要操作
- put(K key, V value)：将指定的键值对插入到HashMap中。如果键已经存在，则更新对应的值。
- get(Object key)：根据键获取对应的值，如果键不存在，则返回null。
- remove(Object key)：移除指定键的键值对。
- containsKey(Object key)：判断HashMap中是否包含指定的键。
- containsValue(Object value)：判断HashMap中是否包含指定的值。
- size()：返回HashMap中键值对的数量。
- isEmpty()：判断HashMap是否为空。
内部工作原理
HashMap的核心在于哈希表（hash table）实现。以下是其基本工作流程：
- 哈希函数：通过键的hashCode()方法计算哈希值，然后用哈希值对数组长度取模，确定键值对在哈希表中的位置。
- 冲突处理：当不同的键计算得到的哈希值相同时，会发生哈希冲突。Java使用链表法（即链地址法）来处理冲突：在哈希表的每个位置上，实际存储的是一个链表，所有哈希值相同的键值对都存储在该链表中。
扩容机制(最后部分重点解释)：HashMap有一个负载因子（默认0.75），当实际存储的键值对数量超过capacity * loadFactor时，HashMap会进行扩容（通常是原来容量的两倍），并重新散列所有的键值对到新的哈希表中。
优缺点
优点
- 快速存取：在理想情况下，HashMap的插入、删除和查找操作的时间复杂度为O(1)。
- 灵活性：HashMap允许使用null值和null键，这在某些应用场景下非常灵活。
缺点
- 非线程安全：HashMap不是线程安全的。如果多个线程同时操作同一个HashMap实例而没有适当的同步措施，会导致数据不一致。线程安全请参考全面解读CourrentHashMap
- 性能退化：在极端情况下（如所有键的哈希值都相同），HashMap的性能会退化为O(n)。
扩容机制（结合treeifyBin方法）
在Java 8中，HashMap在处理哈希冲突时引入了树化机制。当某个桶中的链表长度超过一定阈值时（默认是8），链表会被转换成红黑树，以提高查询效率。这一过程被称为树化（treeify），而具体的树化操作则是在treeifyBin方法中进行的。下面我们结合treeifyBin方法和扩容过程来详细讲解。
treeifyBin 方法
首先，让我们看一下treeifyBin方法的实现：
final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; 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 { 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); } }
关键点分析
- 树化的触发条件：
当某个桶中的链表长度超过阈值（默认8）时，会触发树化。但是，在进行树化之前，会检查哈希表的容量。如果当前哈希表的容量小于最小树化容量（默认64），则会进行扩容而不是树化：
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize();
MIN_TREEIFY_CAPACITY的默认值是64。这意味着，如果当前哈希表的容量小于64，即使链表长度超过阈值，也不会进行树化，而是优先扩容。这是为了避免在容量较小的哈希表中引入树结构，进而影响性能。
- 链表转换为红黑树：
如果哈希表的容量大于或等于最小树化容量，会将链表节点转换为红黑树节点：
else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; 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); }
这里，首先遍历链表，将每个普通节点（Node）转换为红黑树节点（TreeNode）。然后，将转换后的树节点构建成一个双向链表，最后调用红黑树节点的treeify方法将链表转换为红黑树。
- replacementTreeNode 方法：
- 该方法用于将普通节点转换为红黑树节点：
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { return new TreeNode<>(p.hash, p.key, p.value, next, null); }
- treeify方法 ：
红黑树节点的treeify方法将链表转换为红黑树：
final void treeify(Node<K,V>[] tab) { // Implementation details... }
扩容与树化的关系
在HashMap中，扩容与树化是两种不同的性能优化手段。当哈希表的容量不足时，扩容是首选的优化手段，而当哈希表容量足够大且某个桶中的链表过长时，才会进行树化操作。扩容的主要目的是减少哈希冲突，从而降低链表长度，而树化则是通过将链表转换为红黑树来提高查找效率。
扩容过程中处理树节点
- 在扩容过程中，如果旧哈希表中某个桶已经是红黑树结构，那么在将这些节点重新哈希到新哈希表时，需要保持红黑树结构。这一点在扩容的
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) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; } else if (oldThr > 0) // 初始阈值 newCap = oldThr; else { // 使用默认值 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 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; }
TreeNode 的 split 方法
TreeNode的split方法将当前红黑树节点分割为两个链表，一个保留在原位置，另一个移动到新位置：
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { TreeNode<K,V> b = this; // 两个新的链表头 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) tab[index] = loHead; if (hiHead != null) tab[index + bit] = hiHead; // 将链表转换为红黑树 if (lc <= UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map); else if (loHead != null) loHead.treeify(tab); if (hc <= UNTREEIFY_THRESHOLD) tab[index + bit] = hiHead.untreeify(map); else if (hiHead != null) hiHead.treeify(tab); }
在扩容过程中，split方法会将当前红黑树节点分成两部分，然后判断链表长度是否低于树化阈值（UNTREEIFY_THRESHOLD，默认6）。如果低于阈值，则将红黑树退化为链表；否则，保持红黑树结构。
总结
通过treeifyBin方法和resize方法的源码分析，可以看出Java 8中HashMap在处理哈希冲突和扩容方面的优化手段：
- 树化：当桶中链表长度超过阈值时，将链表转换为红黑树，以提高查询效率。
- 扩容优先：如果哈希表容量不足，则优先进行扩容，而不是树化，以避免在小容量时引入树结构。
- 扩容处理树节点：在扩容过程中，保留红黑树结构，并根据新链表长度决定是否退化为链表。
这些机制共同保证了HashMap在处理大量数据时的高效性。理解这些实现细节有助于在实际使用中优化HashMap的性能。
