★ HashMap 底层原理是什么？为何 1.8 引入红黑树？

结论先行：HashMap 底层是数组 + 链表 + 红黑树。key 的 hash 经扰动后用于定位桶位，哈希冲突时以链表挂接；JDK 1.8 中当链表长度 ≥ 8 且数组容量 ≥ 64 时链表转为红黑树，把单桶最坏查找从 O(n) 降到 O(log n)。默认容量 16、负载因子 0.75，扩容按 2 倍进行并原地拆分节点。

关键机制

机制	说明
桶定位	(n - 1) & hash 替代取模，前提是容量为 2 的幂
冲突解决	链表尾插；树化条件：桶长 ≥ 8 且容量 ≥ 64
树退化	红黑树节点数 < 6 时转回链表
扩容	容量翻倍，节点按“高位是否为 1”拆分高低两组，不必全部重算 hash
负载因子 0.75	空间与时间的折中，元素数 ≥ 容量 × 0.75 时触发扩容

树化与退化阈值（8/6）故意留缓冲，避免链表与红黑树在边界频繁互转造成抖动。

为何引入红黑树

哈希分布极差或被恶意构造时，链表查找退化为 O(n)，等于拒绝服务攻击；红黑树自平衡，把单桶最坏查询降为 O(log n)。1.8 相对 1.7 还有两处变化：尾插法避免并发扩容成环，以及扩容时节点拆分重排。

注意树化门槛是双条件：桶长 ≥ 8 且 容量 ≥ 64；容量不足 64 时优先扩容而不是转树。

import java.util.HashMap;
import java.util.Map;

public class HashMapDemo {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>(16); // 可预估容量防扩容
        map.put("a", 1);

        int n = 16;                          // 容量恒为 2 的幂
        int h = "a".hashCode();
        int hash = h ^ (h >>> 16);           // 扰动示意：高 16 位混入低位
        int index = (n - 1) & hash;          // 定位桶位，等价取模
        System.out.println("桶位=" + index + ", 取值=" + map.get("a"));
    }
}

常见追问 / 记忆点

• 记忆点：1.8 三大变化——尾插、树化（≥8 且容量 ≥64）、扩容高低位拆分。
• 追问：为什么 1.7 头插在并发扩容时会成环——1.8 改尾插后仍有覆盖丢失问题，并发请用 ConcurrentHashMap。
• 追问：key 为 null 时 hash 取 0，固定落在 0 号桶，这是 HashMap 允许 null key 的原因之一。
• 追问：无参构造在首次 put 时才创建容量 16 的散列表，属于懒初始化。