HashMap核心结构与源码解析

HashMap是Java集合框架中最为常用的数据结构之一，它基于哈希表实现了Map接口，提供了键值对的存储与检索功能。其核心数据结构在JDK 1.8之后经历了重要演进，从“数组+链表”转变为“数组+链表+红黑树”的组合结构。这一设计的根本目的在于优化在哈希冲突严重时，链表过长导致的查询效率下降问题。

当我们向HashMap中放入一个键值对时，首先会调用键（Key）对象的`hashCode()`方法计算哈希值。此哈希值会经过HashMap内部的`hash()`方法进行二次处理，目的是为了扰乱低位，使得哈希分布更加均匀，减少冲突。随后，通过`(n - 1) & hash`（其中n为数组长度）这个位运算，快速计算出该键值对应在底层数组（常称为“桶”bucket）中的索引位置。

扰动函数与索引计算

HashMap的`hash()`方法（扰动函数）是一个关键优化点。它通过将键的原始哈希码的高16位与低16位进行异或运算（`(h = key.hashCode()) ^ (h >>> 16)`），使得高位的变化也能影响到最终的索引计算。因为数组长度n通常较小，直接使用原始哈希码的低位进行索引计算，如果高位变化很大而低位不变，依然会产生大量冲突。扰动函数有效地混合了高位信息，增加了低位的随机性，从而让数据分布更散列。

链表与红黑树的转换机制

当多个键值对映射到同一个桶时，就会发生哈希冲突。在JDK 1.8之前，HashMap完全采用链表来解决冲突。但当链表过长时，查询性能会退化为O(n)。为此，JDK 1.8引入了红黑树。当一个桶中的链表长度超过阈值（默认为8），并且当前HashMap的容量（数组长度）大于等于最小树化容量（默认为64）时，该链表将被转换为红黑树。红黑树是一种自平衡的二叉查找树，能将查询、插入、删除的时间复杂度维持在O(log n)，极大地提升了在极端情况下的性能。反之，当树中的节点数因删除操作减少到另一个阈值（默认为6）时，红黑树会退化为链表，以节省空间。

扩容机制：resize方法详解

当HashMap中的元素数量超过`容量 负载因子`（默认负载因子为0.75）时，会触发扩容（resize）。扩容会创建一个新的、容量为原来两倍的数组。之后，需要将所有已存在的键值对重新计算索引位置（rehash），并迁移到新数组中。JDK 1.8对扩容过程做了巧妙优化。在迁移链表节点时，它发现由于新数组容量是原数组的2倍，每个节点在新数组中的新位置要么保持原索引`j`，要么变为`j + oldCap`。通过判断节点哈希值与旧容量的位与操作结果是否为0，可以快速将原链表拆分成两个链表（低位链表和高位链表），并分别放到新数组的`j`和`j+oldCap`位置。这个过程避免了JDK 1.7中链表反转可能导致的死循环问题，并且提升了扩容效率。

HashMap的线程不安全问题

HashMap在设计上不是线程安全的，这意味着在多线程并发环境下使用它可能导致数据不一致、死循环（主要发生在JDK 1.7的扩容过程中）等问题。究其根源，问题主要出现在put操作引发扩容，以及多线程同时修改同一个链表或树结构时。

JDK 1.7中的死循环问题

在JDK 1.7中，HashMap采用头插法将新节点插入链表。在并发扩容时，执行transfer方法进行链表迁移，头插法会导致迁移后的链表顺序与原链表相反。如果两个线程同时触发扩容，在执行transfer方法时，可能会形成环状链表。之后，当有线程对该桶进行查询时，就可能陷入死循环，导致CPU占用率飙升。

数据覆盖与丢失

这是所有版本HashMap都存在的主要并发问题。当两个线程同时执行put操作，并且计算出的桶位置相同，它们可能同时判断该位置为空，然后相继写入新的节点。这样，后一个线程写入的操作会覆盖前一个线程的操作，导致数据丢失。

并发优化实践：如何安全高效地使用HashMap

鉴于HashMap的线程不安全性，Java提供了多种方案来满足并发场景下的需求。

使用Hashtable或Collections.synchronizedMap

这是两种传统的同步方案。Hashtable是一个古老的线程安全类，它在所有方法上都加上了`synchronized`关键字进行同步，保证同一时刻只有一个线程能操作Map。`Collections.synchronizedMap(new HashMap())`也是类似的原理，它返回一个同步包装器，将所有方法委托给原始HashMap，但使用一个互斥锁进行同步。这两种方式的优点是实现简单，能保证强一致性。缺点是性能瓶颈严重，因为锁的粒度太粗，整个对象被锁定，高并发下性能较差。

并发王者：ConcurrentHashMap

为了在高并发环境下获得更好的性能，Java引入了ConcurrentHashMap。它在不同JDK版本中也有显著的演化。

JDK 1.7的实现： 采用“分段锁”（Segment）机制。ConcurrentHashMap内部由一个Segment数组组成，每个Segment本质上是一个小的Hashtable。不同的Segment互不干扰。当线程访问不同Segment的数据时，可以真正实现并行。这种机制降低了锁的粒度，提升了并发度。

JDK 1.8及以后的实现： 放弃了分段锁，采用了更优化的技术。它使用Node数组作为主体，借鉴了HashMap的很多思想。其线程安全策略包括：1. CAS（Compare-And-Swap）操作： 在初始化数组、插入空桶等无竞争场景下，使用CPU原子指令CAS来保证操作的原子性，避免了加锁的开销。2. synchronized锁细化： 当发生哈希冲突，需要操作链表或红黑树时，ConcurrentHashMap只对冲突的那个桶（即链表的头节点或树的根节点）进行`synchronized`加锁。这样，只要线程访问的是不同的桶，它们就可以完全并发执行，锁的粒度从Segment级别细化到了桶级别，并发性能得到了巨大提升。此外，ConcurrentHashMap的size()方法也通过维护一个基础计数变量和计数器数组（Cell[]），采用类似于LongAdder的分段计数思想，来避免高并发下的竞争，提供更准确的元素数量估算。

实践建议与总结

在选择使用哪种Map时，应遵循以下原则：在单线程环境下，HashMap因其优异的性能是首选。在低并发、且需要强一致性的场景下，可以考虑使用Collections.synchronizedMap。而在高并发场景下，ConcurrentHashMap是毋庸置疑的最佳选择，它通过精细的锁设计和CAS操作，在保证线程安全的同时，提供了接近于HashMap的卓越性能。理解其从源码到并发优化的演进历程，有助于开发者根据实际需求做出最合适的技术选型，并编写出高效、健壮的并发程序。