在Java中HashMap底层是如何实现的_Java哈希映射结构解析
HashMap底层是数组+链表+红黑树，Java 8起当链表长度≥8且数组长度≥64时转为红黑树，否则扩容；hash()二次扰动缓解低位哈希冲突；put过程含哈希计算、桶定位、冲突处理与可能的树化或扩容；非线程安全，多线程put会导致数据覆盖或死循环。
HashMap 的底层数据结构是数组 + 链表 + 红黑树
Java 8 开始，HashMap 不再只是“数组 + 链表”，而是在链表长度 ≥ 8 且数组长度 ≥ 64 时，将链表转为红黑树。这个阈值由两个条件共同控制：TREEIFY_THRESHOLD = 8 和 MIN_TREEIFY_CAPACITY = 64。
关键点在于：不是一插入就树化，也不是链表一长就树化——必须同时满足桶（bucket）中节点数 ≥ 8 且 整个 table 数组长度 ≥ 64，才会触发 treeifyB。
- 数组长度不足 64 时，即使某桶有 10 个冲突节点，也只会先扩容（resize），而不是树化
- 红黑树节点是
TreeNode类型，它继承自Node，但额外携带了parent、left、right等字段 - 当树中节点数 ≤ 6 时，会退化回链表（通过
untreeify()）
hash() 方法为什么二次扰动？
HashMap 对 key.hashCode() 做了位运算扰动：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}这是为了把高位也参与低位的索引计算，缓解哈希值低位相似导致的聚集问题（比如 HashMap 存的是 Integer，且数值集中在小范围，原始 hashCode 就是自身值，低位重复率高）。
如果不扰动，仅用 (n - 1) & hash 计算下标，那么 n 是 2 的幂次（如 16），n-1 就是 0b1111，只取 hash 低 4 位——高位完全被丢弃，容易造成大量碰撞。
put() 过程中如何处理哈希冲突与扩容
调用 put(K, V) 时，核心流程是：计算 hash → 定位桶（tab[i = (n-1) & hash]）→ 若桶为空则直接新建 Node；否则遍历链表或树节点比对 key.equals()。
- 如果找到相同 key（
hash相等且equals()为 true），则覆盖 value，并返回旧值 - 如果没找到，新节点插入链表尾部（JDK 8 后不再是头插，避免多线程扩容死链）
- 插入后若链表长度达到 8，且数组长度 ≥ 64，则树化；否则若
size >= threshold（默认 0.75 × capacity），触发 resize() - 扩容时新数组长度翻倍，原节点根据 hash 的新增 bit 位决定留在原索引还是落到
i + oldCap
为什么 HashMap 不是线程安全的？典型表现是什么
多个线程同时 put 可能引发两种典型问题：
- 数据覆盖：两个线程计算出同一桶位置，都判断该桶为空，各自新建 Node 写入，后者直接覆盖前者
-
死循环（JDK 7）：多线程扩容时头插法导致链表成环，
get()遍历时无限循环（JDK 8 改为尾插，消除了该问题，但并发写仍不安全）
注意：ConcurrentHashMap 并非简单加锁整个 map，而是采用分段锁（JDK 7）或 CAS + synchronized 锁单个桶（JDK 8+），粒度更细。但即便如此，computeIfAbsent 等复合操作仍需外部同步保障原子性。
真正需要线程安全时，别靠“我只读不写”这种假设——只要存在任何写操作，就必须用 ConcurrentHashMap、Collections.synchronizedMap()，或明确加锁。
