1. 从数组到哈希表为什么我们需要它如果你写过几年代码肯定用过数组。数组是个好东西按下标array[0]就能直接拿到第一个元素时间复杂度是 O(1)快得飞起。但它的缺点也很明显你想找某个特定的值比如“张三”的电话号码你就得从头到尾遍历整个数组挨个比对时间复杂度是 O(n)。当数据量一大比如有十万个联系人这个查找速度就慢得让人难以忍受。于是我们有了另一种结构链表。链表在插入和删除上很灵活但查找同样需要遍历O(n) 的复杂度跑不掉。有没有一种数据结构既能像数组一样通过“下标”快速访问又能像链表一样灵活存储并且这个“下标”可以是任意类型比如字符串“张三”而不是枯燥的数字 0, 1, 2 呢哈希表Hash Table就是为了解决这个问题而生的。它的核心思想非常巧妙它使用一个哈希函数Hash Function把任意长度的输入比如一个字符串“张三”映射到一个固定范围的数组下标上。然后我们就把“张三”对应的数据比如电话号码存储在这个数组下标对应的位置里。下次要找“张三”我们再用同样的哈希函数算一下“张三”对应的下标然后直接去数组的那个位置取数据就行了。理想情况下这又是一个 O(1) 的操作。听起来很完美对吧但魔鬼藏在细节里。这个“映射”过程会引出一系列经典问题如果两个不同的键比如“张三”和“李四”经过哈希函数计算后得到了同一个数组下标怎么办这就是哈希冲突。哈希表所有的精妙设计和性能权衡几乎都围绕着如何高效、优雅地解决哈希冲突展开。在实际开发中哈希表无处不在。Java 里的HashMap、HashSetPython 里的dict、setJavaScript 里的Object、Map其底层核心都是哈希表。理解哈希表不仅是掌握一种数据结构更是理解现代编程语言中高频使用的容器类是如何工作的这对于写出高性能、无隐患的代码至关重要。接下来我们就剥开哈希表的外壳看看它内部到底是如何运转的。2. 哈希表的核心三要素数组、哈希函数与冲突解决要理解哈希表必须吃透它的三个核心组成部分一个底层数组通常称为桶数组 Bucket Array、一个哈希函数、以及一套冲突解决机制。这三者环环相扣共同决定了哈希表的性能和行为。2.1 底层桶数组存储的骨架哈希表的基础是一个固定大小的数组。这个数组的每个位置我们称之为一个“桶”Bucket。初始时这些桶可能是空的。当我们插入一个键值对Key-Value Pair时过程是这样的对键Key应用哈希函数得到一个整型的哈希值Hash Code。将这个哈希值映射到数组的索引范围内通常通过取模运算hashCode % arrayLength。将值Value存储在该索引对应的桶中。这个数组的大小容量Capacity是哈希表的一个重要参数。如果数组太小即使哈希函数分布均匀也极易发生冲突如果数组太大又会浪费内存空间。因此一个设计良好的哈希表需要具备动态扩容的能力。2.2 哈希函数从键到下标的魔法哈希函数是哈希表的灵魂。一个好的哈希函数需要满足以下几个条件确定性相同的输入必须始终产生相同的输出。高效性计算速度要快毕竟每次插入和查找都要调用它。均匀性尽可能将不同的键均匀地分布到整个数组空间减少冲突。对于不同的数据类型哈希函数的实现也不同。整数整数本身就可以作为哈希值或者进行一个简单的混淆。字符串这是最常见的场景。一种经典的算法是“多项式滚动哈希”。例如对于字符串 “abc”我们可以计算hash (a * p^2 b * p^1 c * p^0) % M其中p是一个质数如31M是一个大数。Java 的String.hashCode()采用的就是类似的思路。对象通常基于对象内部各个字段的哈希值进行组合计算。这里有一个关键点哈希函数计算出来的是一个int或long范围的哈希码我们需要将它“压缩”到数组下标范围内。最常用的方法是取模运算index hashCode % capacity。为了性能当容量是2的幂时可以用更快的位运算代替取模index hashCode (capacity - 1)。这也是为什么很多哈希表实现如 HashMap的默认容量是162^4的原因。2.3 哈希冲突的解决开放寻址与链地址法无论哈希函数多完美只要数组容量是有限的而可能的键是无限的冲突就必然发生。“张三”和“李四”映射到了同一个桶里怎么办主流解决方案有两种。2.3.1 链地址法Separate Chaining这是最直观、最常用的方法JavaHashMap在JDK8之前就采用此法。它的思想很简单数组的每个桶不再直接存储一个值而是存储一个链表的头节点或红黑树的根节点。当发生冲突时新的键值对就被添加到这个桶对应的链表末尾。桶数组: [0] - null [1] - (键1值1) - (键2值2) - null // 冲突形成链表 [2] - null ...插入计算索引找到对应桶遍历链表。如果发现已存在相同键则更新值否则将新节点插入链表通常采用头插法或尾插法。查找计算索引找到对应桶遍历链表比对键是否相等。删除计算索引找到对应桶遍历链表找到节点并删除。链地址法的优点是对负载因子元素总数/桶数量容忍度较高即使链表变长性能也是逐渐下降。缺点是链表节点需要额外内存存储指针且对CPU缓存不友好节点内存不连续。2.3.2 开放寻址法Open Addressing这种方法规定所有元素都直接存放在桶数组里。当发生冲突时它会按照某种探测序列Probing Sequence去寻找下一个空闲的桶。最常见的探测方法有线性探测Linear Probing如果位置i被占则尝试i1,i2,i3... 直到找到空位。二次探测Quadratic Probing按i 1^2,i 2^2,i 3^2... 的步长寻找减少聚集。双重哈希Double Hashing使用第二个哈希函数来计算探测步长。桶数组: [0]: 空 [1]: (键1值1) // 理想位置 [2]: (键2值2) // 键2本应去1但1被占线性探测到2 [3]: 空插入计算索引如果该桶为空则插入否则沿探测序列寻找下一个空桶插入。查找计算索引从该桶开始沿探测序列依次比对键。注意遇到空桶时查找必须终止因为目标键不可能在更后面否则插入时就会放在这个空桶了。删除这是开放寻址法的麻烦之处。不能简单地将桶置空否则会切断后续元素的探测路径导致查找失败。通常采用“懒删除”标记或者需要后续元素“重新插入”。开放寻址法的优点是所有数据都存储在连续数组中对CPU缓存友好内存利用率高没有指针开销。缺点是对负载因子非常敏感当负载因子较高时如0.7性能会急剧下降且必须保证有足够的空桶以供探测。选择哪种链地址法实现更简单在大多数情况下是默认选择。开放寻址法在内存紧凑、追求极致缓存性能的场景下更有优势。现代HashMap如JDK8实际上采用了混合策略默认使用链表但当单个桶的冲突达到一定阈值默认8时会将链表转换为红黑树以应对极端哈希冲突下的性能退化。3. 手撕一个简易哈希表从零实现理解细节理论讲得再多不如动手实现一遍。我们来用 Java 实现一个采用链地址法的简易哈希表MyHashMap支持putgetremove基本操作。这个过程会让你对之前讲的所有概念有刻骨铭心的理解。3.1 定义数据结构与构造函数首先我们需要定义存储键值对的节点类以及哈希表本身的核心字段。/** * 哈希表节点类用于链地址法中的链表 */ class NodeK, V { K key; V value; NodeK, V next; // 指向下一个节点的指针 Node(K key, V value) { this.key key; this.value value; this.next null; } } /** * 简易哈希表实现 */ public class MyHashMapK, V { // 底层桶数组 private NodeK, V[] table; // 当前哈希表中键值对的数量 private int size; // 桶数组的容量长度 private int capacity; // 默认初始容量 private static final int DEFAULT_CAPACITY 16; // 默认负载因子阈值 private static final float DEFAULT_LOAD_FACTOR 0.75f; // 实际负载因子阈值 private float loadFactor; /** * 无参构造使用默认容量和负载因子 */ public MyHashMap() { this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR); } /** * 带参构造 * param initCapacity 初始容量 * param loadFactor 负载因子 */ SuppressWarnings(unchecked) public MyHashMap(int initCapacity, float loadFactor) { if (initCapacity 0) throw new IllegalArgumentException(Illegal initial capacity); if (loadFactor 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException(Illegal load factor); this.capacity initCapacity; this.loadFactor loadFactor; this.table (NodeK, V[]) new Node[capacity]; // 初始化桶数组 this.size 0; } }关键点解析Node类是一个标准的单向链表节点。table是核心的桶数组每个元素是一个Node链表的头节点。size记录元素总数用于判断是否需要扩容。capacity是桶数组的长度这里我们暂时固定后续会实现扩容。loadFactor负载因子是一个极其重要的概念它等于size / capacity。它衡量哈希表的“拥挤程度”。当size capacity * loadFactor时冲突概率会大大增加性能下降此时就需要扩容Rehashing。0.75是经过统计学验证的一个较好权衡值。3.2 实现哈希函数与索引计算我们需要一个方法来计算任意对象的哈希值并将其映射到数组下标。/** * 计算键的哈希值模仿HashMap的扰动函数 */ private int hash(K key) { if (key null) return 0; // 允许null键将其哈希值定为0 int h key.hashCode(); // 高位参与运算减少哈希冲突 return h ^ (h 16); } /** * 根据哈希值和当前容量计算桶索引 */ private int getIndex(int hash) { // 利用位运算代替取模要求capacity是2的幂 return hash (capacity - 1); }关键点解析直接调用key.hashCode()是基础但这样高位信息可能用不到。h ^ (h 16)这一步叫做“扰动函数”。它将哈希值的高16位与低16位进行异或目的是让高位的变化也能影响到最终索引的计算从而让哈希分布更加均匀。这是JDKHashMap中的经典操作。getIndex方法中hash (capacity - 1)等价于hash % capacity但位运算效率远高于取模。这要求capacity必须是2的幂这样才能保证capacity - 1的二进制形式是全1例如16-115二进制1111使得操作能均匀映射。3.3 实现put操作插入与更新put操作需要处理插入新键、更新旧值、解决冲突、触发扩容等多个逻辑。/** * 插入或更新键值对 */ public V put(K key, V value) { // 1. 检查扩容 if (size capacity * loadFactor) { resize(); } int hash hash(key); int index getIndex(hash); // 2. 遍历链表检查键是否已存在 NodeK, V head table[index]; NodeK, V cur head; while (cur ! null) { // 注意判断键相等要用equals并且要处理null键 if (keysEqual(cur.key, key)) { // 键已存在更新值 V oldValue cur.value; cur.value value; return oldValue; } cur cur.next; } // 3. 键不存在创建新节点并插入链表头部头插法简单高效 NodeK, V newNode new Node(key, value); newNode.next head; // 新节点的next指向原头节点 table[index] newNode; // 桶的头节点更新为新节点 size; return null; // 之前没有旧值返回null } /** * 安全的键比较方法处理null情况 */ private boolean keysEqual(K key1, K key2) { // 先比较引用再调用equals return key1 key2 || (key1 ! null key1.equals(key2)); }关键点解析扩容检查在插入前先判断如果当前元素数量已达到阈值容量*负载因子则先扩容。这是保证性能的关键。遍历查找计算索引后需要遍历该桶的链表检查是否已存在相同的键。这里使用了keysEqual方法来安全地比较键包括处理null。更新与插入如果找到则更新值并返回旧值如果没找到则创建新节点。头插法我们将新节点插入链表头部。因为新插入的数据更可能被马上访问时间局部性原理头插法效率更高O(1)。JDK7的HashMap就采用头插法但在并发环境下会形成环形链表导致死循环JDK8已改为尾插法。我们这里为了简化使用头插法。3.4 实现get与remove操作get和remove的逻辑与put中的查找部分类似。/** * 根据键获取值 */ public V get(K key) { int hash hash(key); int index getIndex(hash); NodeK, V cur table[index]; while (cur ! null) { if (keysEqual(cur.key, key)) { return cur.value; } cur cur.next; } return null; // 未找到 } /** * 根据键删除键值对 */ public V remove(K key) { int hash hash(key); int index getIndex(hash); NodeK, V head table[index]; NodeK, V prev null; NodeK, V cur head; while (cur ! null) { if (keysEqual(cur.key, key)) { // 找到要删除的节点 if (prev null) { // 要删除的是头节点 table[index] cur.next; } else { // 要删除的是中间或尾部节点 prev.next cur.next; } size--; return cur.value; } prev cur; cur cur.next; } return null; // 未找到要删除的键 }关键点解析get操作很简单就是计算索引遍历链表找到相等的键则返回值。remove操作需要维护链表的前驱节点prev。因为删除单链表中的节点需要知道其前一个节点。如果要删除的是头节点则直接更新table[index]为下一个节点。3.5 实现动态扩容Rehashing这是哈希表实现中最精妙也最容易出错的部分。扩容不仅仅是创建一个更大的数组还需要将旧数组中的所有元素重新哈希到新数组中。/** * 扩容重哈希 */ SuppressWarnings(unchecked) private void resize() { int newCapacity capacity * 2; // 通常扩容为原来的2倍 NodeK, V[] newTable (NodeK, V[]) new Node[newCapacity]; // 遍历旧表中的每一个桶 for (int i 0; i capacity; i) { NodeK, V oldNode table[i]; while (oldNode ! null) { NodeK, V nextNode oldNode.next; // 保存下一个节点的引用因为要断开链接 // 重新计算在新表中的索引 int newHash hash(oldNode.key); // 注意这里要重新计算hash因为capacity变了 int newIndex newHash (newCapacity - 1); // 使用新容量计算索引 // 将旧节点插入到新表的对应链表头部头插法 oldNode.next newTable[newIndex]; newTable[newIndex] oldNode; // 处理旧链表中的下一个节点 oldNode nextNode; } // 旧桶置空帮助GC table[i] null; } // 更新哈希表的容量和底层数组引用 capacity newCapacity; table newTable; }关键点解析为什么扩容通常是2倍为了保持容量是2的幂这样可以使用高效的hash (capacity-1)来计算索引。扩容2倍后新容量依然是2的幂。为什么需要重新哈希因为索引计算公式是hash (capacity-1)。容量capacity变了capacity-1的二进制掩码就变了同一个键在新旧两个数组中计算出的索引很可能不同。所以必须对每个键重新应用哈希函数和索引计算。遍历与迁移外层循环遍历旧数组的每个桶内层循环遍历桶内的链表。对于每个节点计算其在新数组中的位置然后采用头插法插入新数组的对应链表中。这里必须保存oldNode.next的引用因为在将oldNode插入新表时会修改它的next指针。时间复杂度扩容操作是 O(n) 的其中 n 是元素个数。但摊还分析下平均每次put操作的成本仍是 O(1)。至此一个具备基本功能的简易哈希表就完成了。你可以写个测试用例跑一下感受它如何工作。这个实现省略了红黑树转换、迭代器等高级特性但核心原理已经全部涵盖。4. 工业级哈希表的进阶特性与优化我们手写的简易哈希表理解了基本原理但离生产级别的实现如 JavaHashMap还有很大距离。工业级哈希表做了大量优化来保证在各类场景下的高性能、高稳定性和线程安全性或明确标识非线程安全。了解这些是你真正驾驭哈希表的关键。4.1 红黑树化应对极端哈希冲突在JDK8之前的HashMap中冲突链表过长会导致查找性能退化为 O(n)。在JDK8中引入了一个重要优化当同一个桶中的链表长度超过一定阈值TREEIFY_THRESHOLD默认为8并且当前哈希表的总容量达到一定规模MIN_TREEIFY_CAPACITY默认为64时该链表会被转换为一个红黑树TreeMap。// JDK8 HashMap 中的相关常量 static final int TREEIFY_THRESHOLD 8; static final int UNTREEIFY_THRESHOLD 6; static final int MIN_TREEIFY_CAPACITY 64;为什么是红黑树红黑树是一种自平衡的二叉查找树它能保证在最坏情况下查找、插入、删除的时间复杂度都是 O(log n)。当链表很长时O(log n) 远比 O(n) 要好。为什么阈值是8这是基于泊松分布的统计结果。在理想的随机哈希下单个桶中链表长度超过8的概率极低小于千万分之一。将阈值设为8意味着在绝大多数正常使用情况下链表都不会转树从而避免了维护红黑树带来的额外开销。这是一种“用空间换时间”的权衡只为应对人为构造的劣质哈希函数攻击或极端情况。为什么转树需要容量64在哈希表很小时桶很少优先考虑的是扩容而不是转树因为扩容能更有效地分散元素。反向操作当扩容后或者删除元素导致树中节点数过少时小于等于UNTREEIFY_THRESHOLD默认为6红黑树会退化为链表以节省内存。4.2 容量与扩容策略的深层次考量我们简易实现中的扩容策略2倍扩容是通用的但工业实现有更多细节。容量始终为2的幂这不仅是为了用位运算代替取模更重要的是在扩容时元素的新位置可以通过一个非常巧妙的规律计算出来。对于一个键其新索引newIndex只可能是oldIndex或者oldIndex oldCapacity。这是因为扩容后掩码(newCapacity-1)比(oldCapacity-1)多了一位高位的1。通过判断键的哈希值在新增的那一位上是0还是1就能决定它该去哪个新位置。这大大提升了扩容时数据迁移的效率。负载因子的选择0.75是默认值但你可以通过构造函数指定。更高的负载因子如0.9能节省内存但会增加冲突降低查找插入性能。更低的负载因子如0.5能提升性能但会浪费内存。0.75是时间和空间成本的一个较好平衡点。初始容量的设定如果你能预估要存储的元素数量N那么最佳的初始容量应该是(N / loadFactor) 1并且向上取整到最近的2的幂。这样可以避免或减少扩容次数提升初始化性能。4.3 哈希表的线程安全问题与ConcurrentHashMap重要警告HashMap不是线程安全的在多线程环境下同时对一个HashMap进行put等结构性修改操作可能会导致数据错乱两个线程同时修改链表导致一个线程的更新丢失。死循环在JDK7及之前并发扩容时的头插法可能导致链表形成环后续的get操作将陷入死循环。JDK8改为尾插法修复了死循环但数据错乱问题依然存在。如果你需要在多线程环境下使用哈希表有几种选择使用Hashtable古老的全表锁实现性能极差不推荐。使用Collections.synchronizedMap(new HashMap())用一个同步包装器包裹HashMap所有方法都用synchronized加锁性能一般。使用ConcurrentHashMap这是目前的首选方案。它采用了分段锁JDK7或更先进的 CAS synchronized 锁桶或链表头/树根的机制JDK8实现了更细粒度的并发控制在高并发下性能远优于前两者。4.4 键对象的约束hashCode与equals的契约这是使用哈希表时最容易出错的地方之一。如果一个类的对象要作为HashMap的键必须正确重写hashCode()和equals(Object)方法并且遵守以下契约如果两个对象根据equals()方法是相等的那么调用它们的hashCode()方法必须返回相同的整数。如果两个对象的hashCode()值相等它们不一定通过equals()相等这就是哈希冲突。违反契约的后果假设你有一个Person类只重写了equals没重写hashCode。p1.equals(p2)返回true但p1.hashCode() ! p2.hashCode()。当你把p1作为键存入HashMap后再用p2去get因为哈希值不同HashMap会去不同的桶里找根本找不到p1存入的值导致逻辑错误。正确重写示例public class Person { private String name; private int age; Override public boolean equals(Object o) { if (this o) return true; if (o null || getClass() ! o.getClass()) return false; Person person (Person) o; return age person.age Objects.equals(name, person.name); } Override public int hashCode() { // 使用Objects.hash可以方便地组合多个字段的哈希值 return Objects.hash(name, age); } }5. 哈希表实战性能调优与经典应用场景理解了原理和实现最终要落到实际应用上。如何用好哈希表避免踩坑并发挥其最大威力5.1 性能调优要点初始化容量如前所述预估数据量并设置合适的初始容量避免多次扩容。扩容是一个相对昂贵的操作。键的选择使用不可变对象如StringInteger作为键是最佳实践。如果键在放入哈希表后其字段被修改导致hashCode()发生变化那么这个键将无法被正确找到也可能会造成内存泄漏对象困在错误的桶里。如果一定要用可变对象需确保放入后不再修改其参与hashCode计算的字段。自定义对象的哈希函数如果你为自定义类重写hashCode()要保证计算速度快并且尽可能让不同对象的值分布均匀。Objects.hash(field1, field2, ...)是一个简单可靠的选择。监控负载因子在性能敏感的场景可以通过调整负载因子来权衡时间和空间。追求极致查询速度可以设小一点如0.5内存紧张可以设大一点如0.9。5.2 经典应用场景剖析缓存Cache这是哈希表的天然应用场景。键是查询条件值是查询结果。HashMap可以实现一个简单的内存缓存。更复杂的缓存如LRU缓存可以在HashMap的基础上结合双向链表来实现。频率统计统计一段文本中每个单词出现的次数。MapString, Integer freqMap new HashMap(); for (String word : words) { freqMap.put(word, freqMap.getOrDefault(word, 0) 1); }去重Set的实现HashSet的内部就是封装了一个HashMap键是元素值是一个固定的Object常量。对象关联映射在Web开发中Session、缓存数据、配置项等经常用HashMap来存储。两数之和/三数之和等算法题利用哈希表 O(1) 的查找能力将算法时间复杂度从 O(n²) 降低到 O(n)。例如“两数之和”遍历数组对于每个元素num检查target - num是否在之前遍历时存入的哈希表中。5.3 一个真实的踩坑案例误用可变对象作为键我曾经在项目中遇到一个诡异的Bug一个用于缓存计算结果的HashMap偶尔会“丢失”数据。排查了很久最后发现是因为用作键的对象是一个自定义的RequestContext里面包含了一些可变的配置参数。这个上下文对象在放入缓存后其内部的一个标志位被后续流程修改了。这导致后续用“看起来一样”的上下文去查缓存时因为hashCode()变了计算出的桶索引不同所以查不到。更糟糕的是原先那个被修改过的键值对被永久地留在了旧的桶里随着时间推移造成了内存泄漏。解决方案最佳实践将键对象设计为不可变的。对于RequestContext我们提取出真正决定计算结果的几个核心字段如参数ID、类型封装成一个不可变的CacheKey对象。如果必须可变确保放入Map后绝不修改任何影响hashCode()和equals()的字段。并在文档中明确警告。哈希表是编程世界中的瑞士军刀简单而强大。从理解数组和链表的局限开始到哈希函数的设计、冲突的解决、动态扩容的巧妙再到工业级的红黑树优化和线程安全考量每一步都充满了计算机科学的智慧。希望这篇超详细的解读能帮你不仅知道HashMap怎么用更能透彻理解它为什么这样设计以及如何在实践中扬长避短用好这把利器。