1. 引言HashMap 是 Java 开发中最常用的集合类之一也是面试中高频考察的知识点。理解它的底层原理不仅能帮助我们写出更高效的代码还能在遇到并发场景时做出正确的技术选型。本文将从数据结构、hash 扰动、扩容机制、树化条件等方面深入剖析 HashMap 的底层实现并解释它为什么线程不安全最后介绍 ConcurrentHashMap 是如何解决线程安全问题的。2. 数据结构数组 链表 红黑树HashMap 的底层核心是一个数组Node 数组数组的每个位置称为一个桶bucket。当多个键的 hash 值映射到同一个桶时就形成了链表当链表长度超过阈值时链表会转换为红黑树以提升查询效率。2.1 数组Node 数组HashMap 内部维护一个NodeK,V[] table数组默认初始容量为 16负载因子为 0.75。数组的每个元素要么为 null要么指向一个链表或红黑树的头节点。staticclassNodeK,VimplementsMap.EntryK,V{finalinthash;finalKkey;Vvalue;NodeK,Vnext;}2.2 链表当两个不同的 key 经过 hash 计算后落到同一个桶时后插入的元素以链表形式挂在已有元素之后。链表节点通过next指针串联插入采用头插法JDK 7或尾插法JDK 8。2.3 红黑树当链表长度达到阈值默认 8且数组容量达到 64 时链表会转换为红黑树。红黑树是一种自平衡二叉查找树查询时间复杂度从 O(n) 降为 O(log n)有效避免了极端情况下链表过长导致的性能退化。HashMap 底层结构Node 数组桶链表冲突较少时红黑树冲突较多时查询 O(n)查询 O(log n)3. hash 扰动HashMap 在计算 key 的桶位置时并不是直接使用key.hashCode()而是先对 hash 值做一次扰动处理让高位信息也能参与低位运算从而降低哈希冲突的概率。staticfinalinthash(Objectkey){inth;return(keynull)?0:(hkey.hashCode())^(h16);}扰动函数的核心是h ^ (h 16)将 hash 值的高 16 位与低 16 位做异或运算使高位信息混合到低位中。这样即使两个 key 的 hashCode 在高位不同、低位相同经过扰动后也能大概率分布到不同的桶中。桶位置的最终计算方式为index(n-1)hash其中n是数组长度。由于n是 2 的幂次(n - 1) hash等价于hash % n但位运算效率更高。4. 扩容机制当 HashMap 中的元素数量超过容量 × 负载因子时会触发扩容。默认容量 16、负载因子 0.75即元素数超过 12 时扩容。4.1 扩容过程扩容时数组长度翻倍从 n 变为 2n并重新计算每个元素的桶位置。JDK 8 对扩容做了优化由于新容量是旧容量的 2 倍元素在新数组中的位置要么不变要么在原位置基础上偏移旧容量大小。finalNodeK,V[]resize(){// 旧数组、旧容量、旧阈值// 新容量 旧容量 1// 遍历旧数组重新分配每个节点}4.2 扩容的触发条件首次插入元素时若数组为空会先进行初始化扩容分配默认容量 16。元素数量超过threshold capacity * loadFactor时触发扩容。链表转红黑树时若数组容量小于 64会优先扩容而不是树化。5. 树化条件链表转换为红黑树需要同时满足两个条件链表长度达到阈值 8当某个桶的链表长度达到 8 时会尝试树化。数组容量达到 64如果数组容量小于 64即使链表长度达到 8也不会立即树化而是先扩容。为什么阈值是 8这是基于泊松分布的概率计算。在负载因子 0.75 的随机哈希场景下链表长度达到 8 的概率约为千万分之六属于极端情况。此时树化能有效防止哈希碰撞攻击导致的性能退化。staticfinalintTREEIFY_THRESHOLD8;staticfinalintMIN_TREEIFY_CAPACITY64;当红黑树的节点数减少到 6 以下时会从红黑树退化为链表避免树结构在数据量小时带来的额外开销。6. 为什么线程不安全HashMap 在多线程环境下存在多个线程安全问题主要体现在以下几个方面6.1 数据覆盖两个线程同时执行 put 操作当它们计算出的桶位置相同时后写入的线程可能覆盖先写入线程的数据导致数据丢失。6.2 扩容死循环JDK 7JDK 7 采用头插法在多线程并发扩容时链表可能形成环形结构导致后续 get 操作陷入死循环CPU 占用飙升。JDK 8 改为尾插法解决了死循环问题但数据覆盖问题依然存在。6.3 迭代器快速失败HashMap 的迭代器是 fail-fast 的。当多个线程同时修改 HashMap 时迭代器会抛出ConcurrentModificationException导致程序异常终止。// 多线程环境下可能抛出 ConcurrentModificationExceptionfor(Map.EntryString,Stringentry:map.entrySet()){// 其他线程修改 map 时会触发异常}6.4 可见性问题HashMap 的读写没有内存屏障一个线程的修改对其他线程不一定可见可能导致读取到过期数据。7. ConcurrentHashMap 如何解决ConcurrentHashMap 是线程安全的哈希表实现它在保证线程安全的同时尽量提升了并发性能。7.1 JDK 7 的分段锁JDK 7 的 ConcurrentHashMap 采用分段锁Segment机制。整个 Map 被划分为多个 Segment每个 Segment 独立加锁。不同 Segment 的读写互不干扰从而支持并发访问。staticfinalclassSegmentK,VextendsReentrantLock{// 每个 Segment 内部是一个小 HashMap}默认有 16 个 Segment理论上支持 16 个线程并发写入。7.2 JDK 8 的 CAS synchronizedJDK 8 放弃了分段锁改用 CAS synchronized 实现更细粒度的并发控制写入时如果目标桶为空使用 CAS 直接插入无需加锁。桶非空时对桶的头节点加 synchronized 锁锁粒度从 Segment 细化到单个桶。扩容时使用多线程协助扩容提升扩容效率。finalVputVal(Kkey,Vvalue,booleanonlyIfAbsent){// 桶为空时使用 CAS 插入// 桶非空时对头节点加 synchronized 锁}7.3 并发读ConcurrentHashMap 的读操作不加锁依赖 volatile 修饰的 Node 数组和节点字段保证可见性。读操作可以完全并发执行性能接近 HashMap。7.4 与 Hashtable 的对比Hashtable 使用全局 synchronized 锁所有读写操作串行执行并发性能极差。ConcurrentHashMap 通过细粒度锁和 CAS 优化并发性能远优于 Hashtable。8. 总结HashMap 通过数组 链表 红黑树的结构配合 hash 扰动、动态扩容和树化机制在单线程场景下提供了优秀的读写性能。但它不是线程安全的多线程环境下会出现数据覆盖、可见性等问题。ConcurrentHashMap 通过分段锁JDK 7或 CAS synchronizedJDK 8解决了线程安全问题是并发场景下的首选。在实际开发中单线程场景优先使用 HashMap多线程共享场景使用 ConcurrentHashMap避免使用 Hashtable。