在Java中HashMap底层是如何实现的_Java哈希映射结构解析_网络技术

HashMap底层是数组+链表+红黑树，Java 8起当链表长度≥8且数组长度≥64时转为红黑树，否则扩容；hash()二次扰动缓解低位哈希冲突；put过程含哈希计算、桶定位、冲突处理与可能的树化或扩容；非线程安全，多线程put会导致数据覆盖或死循环。

Java 8 开始，HashMap 不再只是“数组 + 链表”，而是在链表长度 ≥ 8 且数组长度 ≥ 64 时，将链表转为红黑树。这个阈值由两个条件共同控制：TREEIFY_THRESHOLD = 8 和 MIN_TREEIFY_CAPACITY = 64。

关键点在于：不是一插入就树化，也不是链表一长就树化——必须同时满足桶（bucket）中节点数 ≥ 8 且整个 table 数组长度 ≥ 64，才会触发 treeifyBin()。

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(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

多个线程同时 put 可能引发两种典型问题：

注意：ConcurrentHashMap 并非简单加锁整个 map，而是采用分段锁（JDK 7）或 CAS + synchronized 锁单个桶（JDK 8+），粒度更细。但即便如此，computeIfAbsent 等复合操作仍需外部同步保障原子性。

真正需要线程安全时，别靠“我只读不写”这种假设——只要存在任何写操作，就必须用 ConcurrentHashMap、Collections.synchronizedMap()，或明确加锁。