刚开始接触数据结构与算法的时候哈希表Hash Table对我来说就是一个“能在 O(1) 时间内完成查找”的神奇容器。那时候只会用 HashMapput 进去 get 出来根本不知道它底层到底怎么做到这么快也不知道为什么有时候重写 equals 就必须重写 hashCode。直到后来去看源码、手写简易版本、再被线上问题毒打几次之后才慢慢把这块彻底吃透。这篇博文就以 Java 为背景把哈希表这个东西从头到尾拆开揉碎讲清楚既是给自己做一个沉淀也希望能帮正在啃算法和集合源码的同学少走一点弯路。这篇文章适合这几类人看准备 Java 面试、正在刷算法题、或者工作中想排查 HashMap 相关的线上问题。内容不会只停留在“HashMap 是数组加链表”这种表面结论而是会讲清楚哈希表为什么设计成这样、JDK 里到底是怎么实现的、哈希冲突怎么处理、容量和负载因子该怎么选、以及手写一个极简哈希表的完整过程。看完之后你不仅能应付面试八股文还能在真正写代码的时候明白自己在用什么、为什么这么用。1. 哈希表的核心思路与设计动机1.1 为什么需要哈希表从数组和链表说起在讲哈希表之前先回想一下我们最基础的两个数据结构数组和链表。数组的特点是内存连续通过下标访问元素的时间复杂度为 O(1)但缺点也很明显查找一个不按下标走的元素时最坏需要遍历整个数组时间复杂度 O(n)。而且数组的插入和删除尤其是中间位置的操作需要移动大量元素成本很高。链表解决了插入删除的问题因为只需要修改指针指向时间复杂度为 O(1)。但链表查找某个值时也必须从头遍历同样逃不过 O(n) 的命运。那有没有一种结构既能享受数组的随机访问速度又能灵活处理动态数据哈希表就是为这个诉求而生的。它通过一个“哈希函数”把元素的键Key映射成数组下标这样一来插入和查找都能直接定位到目标位置理想情况下时间复杂度就是 O(1)。你可以把哈希函数理解成一个“计算器”输入一个键输出一个整数这个整数再经过处理就变成数组下标。整个过程就像你去图书馆找书不需要一本一本翻而是根据索书号直接定位到对应的书架层。1.2 哈希表的基本结构数组加哈希函数一个标准的哈希表由两个核心部分组成一块连续的内存空间通常就是数组用来存储数据一个哈希函数用来把键映射为数组下标插入元素时先计算 key 的哈希值再通过取模等方式转换成数组下标然后把 value 存入数组的该位置。查询元素时也走同样的流程计算哈希值、定位下标、取出数据。这里最关键的设计点是哈希函数的质量。如果哈希函数设计得不好不同 key 算出来的下标很容易相同这就会导致“哈希冲突”。哈希冲突一多查找速度就会从 O(1) 退化到 O(n)哈希表的性能优势就荡然无存了。用生活化的例子来类比哈希函数就好比把一堆快递分到不同货架上的规则。规则越合理每个货架上的快递越少你找快递越快。规则不合理所有快递都堆在同一个货架上找起来就和在一堆杂物里翻东西没区别。2. Java 中 HashMap 的底层实现解析2.1 JDK 1.8 之后的数组加链表加红黑树结构说到 Java 里的哈希表绝大多数人第一个想到的就是 HashMap。JDK 1.8 之后HashMap 的底层结构变成了“数组 链表 红黑树”的复合结构。数组是主体用来存储数据。每个数组位置称为一个“桶”Bucket。当多个元素的哈希值映射到同一个桶时它们就以链表的形式串联起来。但当链表长度超过阈值默认是 8时链表会转换成红黑树目的是把最坏情况下的查找时间复杂度从 O(n) 降到 O(log n)。这个设计解决了一个很实际的问题如果哈希函数的质量不够好或者恶意攻击者故意构造大量哈希值相同的 key典型的哈希碰撞攻击链表会变得很长HashMap 的查询性能会急剧下降。引入红黑树之后即使最坏情况发生了查询性能依然保持在可接受的范围。2.2 put 操作完整流程HashMap 的 put 操作是整个结构的核心入口流程如下对 key 计算哈希值这里 JDK 不是直接使用 key.hashCode() 的原始值而是做了一次扰动处理h key.hashCode() ^ (h 16)。高位和低位做异或目的是让高位的信息也参与到后续的下标计算中减少冲突概率。根据哈希值计算数组下标(n - 1) hash其中 n 是数组长度。因为 n 是 2 的幂次方所以n - 1的二进制全是低位 1这个位运算等价于取模运算但效率更高。如果数组还没有初始化首次 put会先触发 resize 初始化数组。如果目标位置为空直接 new 一个 Node 放进去。如果目标位置不为空说明有冲突分两种情况如果当前桶是普通链表节点就遍历链表。如果找到相同的 key先比较 hash 再比较 equals就替换旧值并返回旧值。如果没找到就在链表尾部插入新节点。插完之后检查链表长度如果超过阈值 8调用 treeifyBin 尝试转换成红黑树。如果当前桶已经是红黑树节点就按照红黑树的插入逻辑处理。插入完成后size加 1。如果size超过阈值threshold容量乘以负载因子执行扩容。2.3 get 操作完整流程get 操作的逻辑相对简单对 key 计算哈希值同样经过扰动处理。计算数组下标取出该位置的节点。如果节点为空直接返回 null。如果节点的 hash 和 key 都与目标匹配直接返回 value。如果不匹配判断节点是链表还是红黑树链表遍历链表逐个比较 hash 和 equals。红黑树调用红黑树的查找方法。这里要注意一个问题hash相同不代表key一定相同因为哈希函数有不确定性。所以判断 key 相等必须走equals方法。这也解释了为什么重写 equals 必须重写 hashCode——如果两个对象 equals 相等但 hashCode 不相等那么它们会映射到不同的桶里HashMap 就找不到了。我试过踩这个坑场景是拿自定义对象做 key只重写了 equals 没重写 hashCode。结果就是同一个逻辑上相等的 key第一次 put 存进去第二次 get 永远取不到。排查了半天才发现是 hashCode 的问题。这个点值得单独拿出来强调equals 相等的两个对象hashCode 必须相等hashCode 相等的两个对象equals 不一定相等。这是 Java 集合框架的黄金法则。3. 哈希冲突的几种解决策略对比3.1 链地址法拉链法链地址法是目前最常用的解决哈希冲突的方法也是 HashMap 采用的方式。思路很简单每个桶不直接存数据而是存一个链表头。冲突的元素依次挂到链表后面。优点是实现简单对哈希函数的要求相对宽松链表只需要在头部或尾部插入即可。缺点是极端情况下链表过长性能下降。JDK 1.8 中 HashMap 对链地址法做了一点改进链表长度超过 8 且数组容量大于等于 64 时链表会转换成红黑树。如果数组容量小于 64会优先扩容而不是转红黑树。这个细节经常出现在面试题里值得注意。3.2 开放地址法开放地址法解决冲突的思路和链地址法截然不同。它不引入额外数据结构而是当发生冲突时在数组内部寻找下一个空闲位置存储。常见探测方式有三种线性探测冲突时依次往后找直到找到空位。缺点是容易产生“堆积”现象即冲突的元素聚集在一起。二次探测探测步长是 1²、2²、3²……这样间隔越来越大避免堆积。双重散列冲突时用另一个哈希函数计算步长也就是走两步一步定位一步探测。Java 中的 ThreadLocalMap 使用的就是开放地址法中的线性探测。它的适用场景是数据量小、哈希表负载因子不高的情况。如果负载因子太高探测次数会急剧上升性能下降很严重。3.3 再哈希法再哈希法的思路更“简单粗暴”准备多个哈希函数第一个冲突了就用第二个第二个冲突了就用第三个。这种方法对哈希函数的分布性要求很高实际应用中不如链地址法和开放地址法普及。Redis 的 rehash 思想和它有些类似但实现上更复杂还涉及渐进式搬迁。三种方式各有优劣简单整理成下面的表格解决策略核心思路优点缺点典型应用链地址法冲突元素链表化实现简单对哈希函数要求低链表过长时性能退化Java HashMap开放地址法数组内找空位空间利用率高无需指针负载因子敏感易堆积ThreadLocalMap再哈希法多个哈希函数冲突概率低需要多个函数计算开销大一般用于缓存场景4. 手写一个极简哈希表从零到可运行4.1 设计目标与关键参数纸上谈兵讲再多原理都不如自己动手写一个来得深刻。这一节带大家手写一个极简的哈希表包含 put、get、remove、扩容这些核心功能。不追求和生产级 HashMap 完全对标重点是把“哈希函数 数组 链表 扩容”这条主链路走通。在动手之前先确定几个关键参数初始容量16负载因子0.75底层结构数组加链表数组中的每个元素是一个 Node 节点Node 里面存哈希值、键、值以及指向下一个节点的引用。4.2 核心代码实现先定义节点类static class NodeK, V { final int hash; final K key; V value; NodeK, V next; Node(int hash, K key, V value, NodeK, V next) { this.hash hash; this.key key; this.value value; this.next next; } }然后是极简哈希表的主体public class SimpleHashMapK, V { static final int DEFAULT_INITIAL_CAPACITY 16; static final float DEFAULT_LOAD_FACTOR 0.75f; private NodeK, V[] table; private int size; private int threshold; private final float loadFactor; public SimpleHashMap() { this.loadFactor DEFAULT_LOAD_FACTOR; this.threshold DEFAULT_INITIAL_CAPACITY; this.table (NodeK, V[]) new Node[DEFAULT_INITIAL_CAPACITY]; } static int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); } private int indexOf(int hash, int length) { return (length - 1) hash; } public V put(K key, V value) { int hash hash(key); int index indexOf(hash, table.length); NodeK, V first table[index]; if (first null) { table[index] new Node(hash, key, value, null); size; if (size threshold) { resize(); } return null; } for (NodeK, V n first; n ! null; n n.next) { if (n.hash hash (n.key key || (key ! null key.equals(n.key)))) { V oldValue n.value; n.value value; return oldValue; } } // 头插法插入新节点 table[index] new Node(hash, key, value, first); size; if (size threshold) { resize(); } return null; } public V get(Object key) { int hash hash(key); int index indexOf(hash, table.length); NodeK, V n table[index]; while (n ! null) { if (n.hash hash (n.key key || (key ! null key.equals(n.key)))) { return n.value; } n n.next; } return null; } public V remove(Object key) { int hash hash(key); int index indexOf(hash, table.length); NodeK, V prev table[index]; if (prev null) { return null; } if (prev.hash hash (prev.key key || (key ! null key.equals(prev.key)))) { table[index] prev.next; size--; return prev.value; } NodeK, V current prev.next; while (current ! null) { if (current.hash hash (current.key key || (key ! null key.equals(current.key)))) { prev.next current.next; size--; return current.value; } prev current; current current.next; } return null; } private void resize() { NodeK, V[] oldTable table; int oldCapacity oldTable.length; int newCapacity oldCapacity 1; NodeK, V[] newTable (NodeK, V[]) new Node[newCapacity]; for (int i 0; i oldCapacity; i) { NodeK, V n oldTable[i]; if (n null) { continue; } oldTable[i] null; while (n ! null) { NodeK, V next n.next; int newIndex indexOf(n.hash, newCapacity); n.next newTable[newIndex]; newTable[newIndex] n; n next; } } table newTable; threshold (int) (newCapacity * loadFactor); } public int size() { return size; } public boolean isEmpty() { return size 0; } }4.3 手写过程中的几个关键决策写这个简易版哈希表的时候有几个点值得展开讲首先是扰动函数。JDK 的 HashMap 把 hashCode 的高 16 位和低 16 位做异或这样即使两个 key 的 hashCode 低位相同、高位不同经过扰动后也能在取模运算中体现差异。我写的版本保持一致因为这是性价比很高的优化。其次是计算下标采用位运算而不是取模。(length - 1) hash只有当 length 是 2 的幂次方时才等价于hash % length。这也是为什么 HashMap 在扩容时总是把容量翻倍而不是随便扩大。这个设计看似简单但一不小心就会踩坑。最后是扩容逻辑。遍历每个桶把桶里的每个节点重新计算新数组的下标并迁移。我这里用的是头插法存在一个隐患在并发环境下可能会形成环。JDK 1.8 改成了尾插法就是为了规避这个问题。但在多线程环境下HashMap 依然不是安全的这个后面会细讲。自己练习的时候头插法足够理解核心逻辑了。写完之后我建议做一轮简单的功能验证public static void main(String[] args) { SimpleHashMapString, Integer map new SimpleHashMap(); map.put(apple, 1); map.put(banana, 2); map.put(cherry, 3); System.out.println(map.get(apple)); System.out.println(map.get(banana)); System.out.println(map.get(cherry)); map.put(apple, 100); System.out.println(map.get(apple)); map.remove(banana); System.out.println(map.get(banana)); for (int i 0; i 100; i) { map.put(key i, i); } System.out.println(map.size()); System.out.println(map.get(key99)); }这段代码覆盖了插入、更新、删除、扩容几个核心场景。如果你看到控制台输出符合预期说明这个简易哈希表基本跑通了。建议多试一些自定义对象做 key 的场景亲身感受一下 hashCode 和 equals 对结果的影响。5. 容量、负载因子与扩容机制深度解读5.1 为什么默认负载因子是 0.75HashMap 的默认负载因子是 0.75f这个数字不是随便拍的而是 JDK 作者在时间和空间成本之间权衡的结果。负载因子越大意味着数组可以容纳更多的元素才扩容空间利用率更高但冲突也会更多查询效率下降。负载因子越小冲突更少查询更快但空间浪费严重频繁扩容也会带来性能开销。0.75 是时空权衡之后的选择在大多数场景下表现均衡。如果业务场景对内存敏感可以适当调大到 0.8 或 0.9如果对查询性能敏感可以调小到 0.5 或 0.6。但注意这个值一旦设置不要频繁变化因为扩容计算依赖它。5.2 为什么容量必须是 2 的幂次方HashMap 要求初始容量为 2 的幂次方即使你传入的初始容量不是它也会计算出大于等于该数的最小 2 的幂次方。原因有两个第一保证(n - 1) hash能正确替代取模运算。当 n 为 2 的幂次方时n - 1的二进制全部为 1低位信息被完整保留。如果 n 不是 2 的幂次方n - 1的二进制会存在 0某些下标永远不可能被映射到造成空间浪费和冲突加剧。第二扩容时可以利用位运算优化元素迁移。扩容后容量变为原来的两倍元素的新位置只可能是“原位置”或者“原位置加旧容量”取决于 hash 的新增那一位是 0 还是 1。这个特性让 JDK 1.8 的扩容实现非常高效不需要重新计算每个元素的 hash。5.3 扩容触发的时机与过程扩容的触发条件是size threshold其中threshold capacity * loadFactor。举个例子初始容量 16负载因子 0.75threshold 就是 12。当元素数量超过 12 时触发扩容数组变成 32threshold 变成 24。扩容的核心操作是创建一个新数组把旧数组中的元素重新分配到新数组。JDK 1.8 使用尾插法按原链表的顺序分割成两条链一条留在原下标一条移动到原下标加旧容量的位置。这样既避免了并发下的死循环问题又比逐个重新哈希效率更高。5.4 预先设置容量避免频繁扩容在实际开发中如果我们能够预估元素数量就应该在创建 HashMap 时指定初始容量避免频繁扩容。这里有个很容易算错的地方指定的初始容量要大于“元素数量除以负载因子”才能保证不提前扩容。举个例子预估要存 1000 个元素如果直接传入 1000那么 threshold 会是1000 * 0.75 750。当存到第 751 个元素时就会扩容一次白费了一次性能开销。正确做法是1000 / 0.75 1333.33向上取整数。但因为 HashMap 会把容量调整为 2 的幂次方所以传入 1334 时会得到 2048 的容量。也可以用new HashMap(1000 * 2)这种粗暴方式保证容量绝对够。6. 常见问题与性能排查实录6.1 HashMap 为什么线程不安全HashMap 在多线程环境下会出各种问题主要有三个典型场景第一多个线程同时 put 时可能导致数据覆盖。两个线程同时定位到同一个空桶都执行了“检查为空”的操作然后一个线程先写入另一个线程后写入前者数据就被覆盖了。第二扩容过程中可能出现数据丢失。多个线程同时触发扩容都在迁移同一个桶里的链表节点很容易出现某个节点的 next 指向被意外修改导致部分节点丢失。第三JDK 1.7 中并发扩容还可能出现循环链表get 操作进入死循环CPU 飙升 100%。1.8 改用尾插法后解决了这个问题但并发安全问题依然存在。所以并发场景必须用 ConcurrentHashMap它通过 CAS 和 synchronizedJDK 1.8 之后等手段保证了线程安全同时锁粒度更细性能更好。6.2 哈希碰撞导致的线上性能问题有一次我排查线上一个接口变慢的问题最终定位到是一个 HashMap 的 key 设计不合理。那个 key 是字符串拼接出来的哈希值分布极度不均匀大量 key 映射到了同一个桶里。因为数据量不大没有触发红黑树转换但链表已经很长了每次查询都在遍历链表性能从 O(1) 退化成了 O(n)。排查思路是这样先在压测环境复现通过 jstack 抓线程栈看到大量线程阻塞在 HashMap.getNode 上。然后写了个小脚本统计 key 哈希值分布发现确实集中在少数几个桶。最后调整了 key 的生成方式让哈希值分布更均匀问题就解决了。这个案例说明哈希表性能好不好哈希函数是关键。即使 HashMap 底层做了扰动处理但 key 本身如果分布极差性能还是会受很大影响。6.3 自定义对象作为 key 的注意事项工作里用的最多的就是 String 和 Integer它们的 hashCode 实现已经非常优化了。但碰见需要自定义对象作为 key 的场景一定要遵守这两条规则重写 equals 时必须重写 hashCode保证 hash 计算所需的字段不可变第一点前面已经说过了。第二点也很重要如果作为 key 的对象的 hashCode 计算字段在放入 HashMap 之后被修改了那么这个对象在 HashMap 中的位置就“失联”了。即使它还存在用同样的 key 去 get 也找不到因为计算出的新下标和存的时候的下标不一样了。这种 bug 非常隐蔽很难排查。6.4 常见问题速查表问题现象可能原因排查建议get 返回 null 但不是真的没有key 的 equals/hashCode 不一致检查是否重写了 hashCode链表过长性能下降key 哈希值分布不均统计哈希值分布调整 key 生成方式并发 put 数据丢失HashMap 线程不安全替换为 ConcurrentHashMap容量没设好频繁扩容初始容量预估不准确按元素数量除以负载因子设定修改 key 字段后找不到元素hashCode 相关字段被修改使用不可变对象作为 key6.5 一个小技巧自定义初始容量在创建 HashMap 时如果知道元素的大致数量可以这样设置// 预估存 1000 个元素 MapString, String map new HashMap((int) (1000 / 0.75f) 1);这个写法按照“容量 元素数量 / 负载因子 1”来计算能有效避免扩容。加 1 是为了处理浮点数向下取整可能导致的边界问题。如果对内存不敏感也可以直接用new HashMap(2048)这种“往大了设”的方式。在 JDK 8 中HashMap 的初始容量只能是 2 的幂次方传入 2048 就是 2048不会再有额外的调整开销。我个人在实际操作中的体会是哈希表这个东西表面上一看就会但真到用的时候很容易踩坑。尤其是扩容机制和 hashCode 的约定面试问得深一点或者是线上排查问题吃亏的基本都是这些细节。手写一个简易版本绝对值得虽然生产环境不会有人用你自己写的哈希表但这个从零到一的过程能把整个数据结构的脉络彻底想通。后续有时间的话我打算写一篇哈希表系列的第二篇重点讲 ConcurrentHashMap 的实现原理和线程安全方案那个东西又是另一套值得仔细拆解的学问了。