1. 哈希表到底解决了什么问题1.1 先看看数组和链表的局限我在带新人的时候经常被问到同一个问题“哈希表为什么不直接叫Hash Map非要叫哈希表”其实名字不关键关键是你得先搞清楚在没有哈希表之前我们查数据有多痛苦。假设你维护了一个员工名单存放在一个数组里数组的每个元素是一个员工对象包含工号、姓名和部门。现在给你一个工号让你把这个员工找出来。最笨的办法就是从头到尾遍历一遍运气好第一个就找到了运气不好最后一个才找到时间复杂度是O(n)。如果名单有一万个人平均要比较五千次才能找到目标。这种模型的痛点在于存储位置和查找关键字之间没有任何关系你只能靠挨个比对来碰运气。有没有一种办法让我拿着一个工号直接就算出它应该存在哪个格子连比较都不用做答案是肯定的这就是哈希表的出发点。再来看链表。链表解决了数组插入和删除时元素搬移的问题但查找依然是O(n)。而且在Java里链表对象本身有额外的节点开销每个节点需要存储前后指针内存占用并不小。哈希表就是冲着“查找也要快”这个目标去的它把数组的“随机访问”能力保留下来又通过一个哈希函数把任意关键字映射到数组下标从而做到平均O(1)的查找、插入和删除。1.2 哈希表的设计思路哈希表的整体思路可以浓缩成一句话用一个哈希函数把键Key映射成数组下标然后把值Value存到这个下标对应的位置。这里有个生活化的类比你去图书馆还书管理员不是一本一本翻书架找空位而是根据书号的后几位直接算出这本书应该放到哪个书架哪个格子。找书的时候也一样按同一个规则算出来直接走到那个格子取书不用全馆扫描。哈希表干的就是这件事。但这里冒出来一个绕不开的问题如果两个不同的键算出来的下标一样怎么办比如键是字符串“abc”和“cba”经过某个哈希函数都得到数值5那它们俩该放同一个格子还是分开这就是哈希冲突。哈希表的设计核心其实有一半工作量都在处理冲突另一半才是哈希函数本身。所以你要真正掌握哈希表第一件事就是把“哈希函数冲突处理”这对孪生兄弟搞清楚。2. 哈希函数与哈希冲突核心原理拆解2.1 哈希函数怎么选哈希函数的作用是把任意长度的输入字符串、数字、对象压缩成一个固定范围的整数。这个整数再经过一次取模运算就得到数组下标。这里要注意一个细节哈希函数算出来的数字不一定直接就是数组下标。因为哈希函数的输出范围通常远大于数组长度比如Java里Object类的hashCode方法返回的是int范围有2的32次方那么大而数组长度可能只有16。所以Java的做法是先拿到hashCode再做一次扰动然后通过“(n - 1) hash”这样的位运算得到一个落在数组范围内的下标。那“好的哈希函数”长什么样三个标准分布均匀不同的键尽量均匀地散落到各个桶里不要让某些桶挤爆、某些桶空着。计算高效哈希函数本身不能太复杂否则算一个下标要花大量CPU时间得不偿失。确定性同一个键任何时候算出来的结果必须一致否则存得进去取不出来。以Java的String为例它的hashCode实现是“s[0]*31^(n-1) s[1]*31^(n-2) ... s[n-1]”每次计算结果都一样满足确定性。31这个系数是经过大量实验选出来的因为它是一个不大不小的质数既能减少冲突又不会让乘法溢出得太离谱。但即便哈希函数选得很好冲突也只能减少不能消除。因为你的输入空间远大于数组空间根据鸽笼原理必然存在至少两个输入映射到同一个位置。所以冲突处理方案是必须具备的。2.2 两大冲突解决方案冲突处理的主流方案有两种链地址法和开放定址法。链地址法也叫拉链法思路非常直白数组每个下标位置不再直接存元素而是存一个链表后来Java 8升级成链表红黑树。当多个键映射到同一个下标时就把它们依次挂到这个链表后面。查找时先通过哈希函数定位到链表头再在链表里做线性查找。如果链表不长查找代价很小如果链表被恶意构造得很长比如所有键的哈希值都相同查找就退化成了O(n)这是哈希表最怕的极端场景。开放定址法思路是既然这个格子被占了那我就按某种规则去找下一个空位。常见的有线性探测依次往后找、二次探测按1、4、9…的步长跳和双重哈希用第二个哈希函数决定步长。这个方法的好处是不需要额外指针内存紧凑适合数据量可控、删除操作少的场景。但它的缺点也很明显删除操作麻烦因为你不能直接把某个格子清空否则会截断探测链导致后续元素查不到。ThreadLocalMap用的就是开放定址法这也是为什么它容量必须严格控制在某个比例以下。Java的HashMap选的是链地址法。原因很简单实现起来直接删除方便而且对哈希函数的均匀性要求没那么苛刻。更关键的是链地址法在冲突严重时可以退化成红黑树来兜底这是开放定址法做不到的。提示面试里如果被问到“HashMap和Hashtable有什么区别”底层冲突方案都可以顺带提一嘴。Hashtable和HashMap在冲突处理上都用链地址法但HashMap在Java 8之后引入树化机制这是两者底层实现的关键代差。3. Java里的哈希表家族HashMap实战必备3.1 HashMap底层结构演进JDK7到JDK8的变化很多老程序员是从JDK 7时代走过来的那会儿HashMap的底层结构是“数组链表”。到了JDK 8底层结构变成了“数组链表红黑树”。这个变化不是炫技而是针对哈希碰撞攻击和极端场景的防御性优化。在JDK 7里如果所有键都映射到同一个桶链表会无限变长查找一个元素的时间成了O(n)。这给了攻击者一个思路构造一堆哈希值相同的字符串塞进去就能把HashMap的查找性能拖垮这就是Hash攻击。JDK 8的解决方案是当链表长度超过阈值8时把链表转换成红黑树。红黑树的高度被严格限制在2log(n1)以内所以即使在最坏情况下查找时间也能控制在O(log n)。为什么要选8作为树化阈值源码里的注释解释过根据泊松分布在负载因子0.75的情况下桶中链表长度达到8的概率是千万分之六概率极低。所以8这个数字是“正常业务几乎不可能达到只有被刻意攻击或哈希函数完全失效时才可能”的警戒线。还有个细节新手容易忽略JDK 8的链表插入方式从“头插法”改成了“尾插法”。JDK 7的头插法在扩容时如果多个线程同时操作链表会出现环形引用直接导致CPU 100%。JDK 8改成尾插法之后虽然不能完全避免并发问题但至少不会出现环形链表这种致命bug了。3.2 三个关键参数初始容量、负载因子、树化阈值HashMap有三个构造参数分别是初始容量initialCapacity、负载因子loadFactor和树化阈值treeifyThreshold。树化阈值在前文中已经讲了固定值是8这里重点说前两个。初始容量默认是16必须是2的幂。为什么必须是2的幂因为HashMap计算下标用的不是取模而是位运算“hash (n - 1)”。这个公式只有在n是2的幂时才等价于“hash % n”而且位运算比取模快得多。如果你在构造时传了一个不是2的幂的数HashMap会帮你向上取整到最近的2的幂。比如你传17它实际会用到32。负载因子默认是0.75。它表示“当元素个数超过容量乘以负载因子时触发扩容”。扩容后的容量是原来的两倍。0.75是时间和空间成本的折中调小了比如0.5空间浪费严重但冲突少、查询快调大了比如1.0空间利用率高但冲突多、链表变长查询变慢。经验上默认值不要动除非你明确知道自己在做什么。这里给一个实操建议如果你预先知道要存多少数据最好在构造时就指定初始容量比如要存100个元素那就设成128之后就不会发生扩容。扩容是很贵的要重新计算所有元素的哈希值并把它们搬到新数组里这是一次完整的O(n)操作。// 预知100个元素主动指定容量避免扩容 MapString, Integer map new HashMap(128);3.3 HashMap与Hashtable、HashSet怎么选Java里有三个表面相似的类HashMap、Hashtable、HashSet。很多人分不清其实关系很清晰Hashtable是JDK 1.0时代遗留的线程安全哈希表所有方法都加了synchronized但这是粗粒度锁并发性能很差。它的另一个特点是不允许null键和null值。现在的新代码基本不会用它需要用线程安全的哈希表时选ConcurrentHashMap。HashMap是线程不安全的但性能最好允许null键和null值。单线程场景首选多线程场景可以搭配Collections.synchronizedMap()包装但在高并发下还是推荐ConcurrentHashMap。HashSet底层就是包装了一个HashMap键存元素本身值统一为一个固定的Object占位符。所以HashSet的contains方法本质上是HashMap的containsKey。这里补充一个冷知识HashMap允许null键但null键的上哈希值恒为0所以它永远会被放到数组下标为0的那个桶里。也就是说最多只能有一个null键。4. 从源码层面理解put/get/扩容4.1 put方法到底做了什么我习惯带着学员一行一行读put方法的源码。读完之后你就会发现之前记住的那些结论全部串起来了。final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { NodeK,V[] tab; NodeK,V p; int n, i; // 如果table还没初始化先触发resize() if ((tab table) null || (n tab.length) 0) n (tab resize()).length; // 计算下标如果这个桶是空的直接放一个新节点 if ((p tab[i (n - 1) hash]) null) tab[i] newNode(hash, key, value, null); else { NodeK,V e; K k; // 第一个节点的key就相等直接覆盖 if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) e p; // 如果已经是红黑树节点走红黑树插入 else if (p instanceof TreeNode) e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value); else { // 遍历链表统计长度 for (int binCount 0; ; binCount) { // 遍历到链表尾部追加新节点 if ((e p.next) null) { p.next newNode(hash, key, value, null); // 链表长度达到树化阈值转换红黑树 if (binCount TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } // 链表里找到了相同的key跳出覆盖 if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) break; p e; } } // 覆盖旧值 if (e ! null) { V oldValue e.value; if (!onlyIfAbsent || oldValue null) e.value value; afterNodeAccess(e); return oldValue; } } modCount; // 超过了扩容阈值触发扩容 if (size threshold) resize(); afterNodeInsertion(evict); return null; }读这段源码建议盯住三个关键分支第一个分支是数组对应位置为空直接放新节点这是哈希表最理想的情况O(1)完成。第二个分支是命中了一个链表或树此时需要遍历去查找key是否已经存在。如果存在就覆盖value如果不存在就在尾部追加新节点。这里有个隐藏的成本点链表遍历是O(m)m是链表长度。如果业务数据出现大量哈希碰撞put就会从O(1)恶化成O(m)。第三个分支是扩容判断。注意size threshold这个判断在插入之后执行意味着“先插入、后扩容”。扩容之后所有元素的桶位置都要重新计算。4.2 get的查找流程get的逻辑比put简单但同样有几个容易被忽略的细节final NodeK,V getNode(int hash, Object key) { NodeK,V[] tab; NodeK,V first, e; int n; K k; if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) { // 检查第一个节点 if (first.hash hash ((k first.key) key || (key ! null key.equals(k)))) return first; // 后续节点树节点走树查找链表节点走循环扫描 if ((e first.next) ! null) { if (first instanceof TreeNode) return ((TreeNodeK,V)first).getTreeNode(hash, key); do { if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) return e; } while ((e e.next) ! null); } } return null; }注意这里判断key相等用的是(key ! null key.equals(k))这说明你放在HashMap里的keyequals方法一定要正确实现。如果两个对象equals相等但hashCode不一致或者hashCode一致但equals不相等都会导致get不到预期的值。这就是大家常说的hashCode与equals的约定。更精确地说两个对象equals相等则hashCode必须相等两个对象hashCode相等equals不一定相等。前一个是硬性要求违反了它HashMap直接失效后一个是哈希冲突可以接受。所以小小的自定义类型放进HashMap时equals和hashCode必须同时重写否则就等着线上莫名其妙的bug吧。4.3 resize扩容最耗时的操作扩容是HashMap里开销最大的操作没有之一。它做了两件事第一把数组长度扩大到原来的两倍第二把旧数组里的所有节点重新分配到新数组里。在JDK 8的扩容实现里节点迁移不是简单地把每个节点重新走下标的取模流程而是用了一个非常巧妙的优化。因为扩容是乘以2所以每个节点的新下标只有两种可能要么是原下标要么是原下标加上旧数组长度。判断的关键在于新取的那一位bit是0还是1。源码里用(e.hash oldCap)来判断结果为0留在原位置结果为1移动到“原位置oldCap”。举个例子旧数组长度是16某个节点的hash是5那它能占到下标n-1 hash的结果是5。扩容到32之后新下标是32-1 5还是5。但另一个节点hash是21它在旧数组中下标是16-1 21 5在新数组中下标是32-1 21 21正好是516。所以“原下标”还是“原下标16”取决于hash从低到高的第5位因为16对应二进制的第5位是0还是1。这个优化让扩容不用重新计算每个节点的整条哈希链只需看一个bit位性能提升非常大。它同时也是理解ConcurrentHashMap扩容的基础。5. 手写一个简单HashMap可直接复制的版本5.1 设计思路读源码读得再多都不如自己动手写一个来得通透。我在带训练营的时候会布置这样一个任务用Java手写一个支持泛型的简易HashMap要求能put、get、remove能自动扩容并且正确处理哈希冲突。设计思路分四步走数据结构底层用一个Node数组每个Node是一个单向链表节点包含key、value、hash和next。哈希函数用key的hashCode再做一次扰动减少低位的碰撞概率。这里为了演示简单直接用“key.hashCode() ^ (key.hashCode() 16)”。下标计算假设数组长度是2的幂用“(len - 1) hash”算下标。冲突处理链表法新节点挂链表尾部。同时维护size和thresholdsize超过threshold就扩容。5.2 核心实现代码public class SimpleHashMapK, V { // 链表节点 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; } } private static final int DEFAULT_CAPACITY 16; // 这里为了演示负载因子取0.75 private static final float DEFAULT_LOAD_FACTOR 0.75f; private NodeK, V[] table; private int size; private int threshold; SuppressWarnings(unchecked) public SimpleHashMap(int initialCapacity) { int capacity 1; // 确保容量是2的幂 while (capacity initialCapacity) { capacity 1; } table (NodeK, V[]) new Node[capacity]; threshold (int) (capacity * DEFAULT_LOAD_FACTOR); } public SimpleHashMap() { this(DEFAULT_CAPACITY); } private int hash(K key) { if (key null) { return 0; } int h key.hashCode(); return h ^ (h 16); } private int indexFor(int hash, int length) { return (length - 1) hash; } public void put(K key, V value) { int hash hash(key); int index indexFor(hash, table.length); NodeK, V first table[index]; if (first null) { table[index] new Node(hash, key, value, null); size; } else { NodeK, V cur first; while (cur ! null) { if (cur.hash hash (cur.key key || (cur.key ! null cur.key.equals(key)))) { cur.value value; return; } if (cur.next null) { break; } cur cur.next; } cur.next new Node(hash, key, value, null); size; } if (size threshold) { resize(); } } public V get(K key) { int hash hash(key); int index indexFor(hash, table.length); NodeK, V cur table[index]; while (cur ! null) { if (cur.hash hash (cur.key key || (cur.key ! null cur.key.equals(key)))) { return cur.value; } cur cur.next; } return null; } public V remove(K key) { int hash hash(key); int index indexFor(hash, table.length); NodeK, V prev null; NodeK, V cur table[index]; while (cur ! null) { if (cur.hash hash (cur.key key || (cur.key ! null cur.key.equals(key)))) { if (prev null) { table[index] cur.next; } else { prev.next cur.next; } size--; return cur.value; } prev cur; cur cur.next; } return null; } SuppressWarnings(unchecked) private void resize() { NodeK, V[] oldTable table; NodeK, V[] newTable (NodeK, V[]) new Node[oldTable.length * 2]; for (NodeK, V node : oldTable) { while (node ! null) { NodeK, V next node.next; int newIndex (newTable.length - 1) node.hash; node.next newTable[newIndex]; newTable[newIndex] node; node next; } } table newTable; threshold (int) (table.length * DEFAULT_LOAD_FACTOR); } public int size() { return size; } }这个版本大概60行核心逻辑覆盖了哈希表最关键的能力。注意我在resize里用了“头插法”来提高效率演示版本里可以这么写因为它是单线程的不会出现并发环链。但你在JDK 8源码里看到的是尾插法这是有讲究的并发场景下头插法更容易产生环所以JDK团队在8里改了。5.3 测试与踩坑写完之后我会让学生跑几个测试用例put 1000个随机键值对、get全部读回来、remove一半、再put另一半。这样能验证基本功能但不能验证哈希函数的质量。真正要检验哈希分布得自己写一段统计代码往里面put一万个键统计每个桶里链表长度的标准差。标准差越小说明分布越均匀。我第一次写这个demo时踩过一个坑忘记处理key为null的情况。虽然HashMap允许null键但我的hash方法里没有对null做特殊处理直接调用key.hashCode()结果一放null键就空指针了。后来加上if (key null) return 0;才解决。这个坑也侧面说明了简单性背后全是细节。还有一个坑在resize方法里。如果newTable的长度计算错了或者indexFor里用的是旧表长度扩容后数据全部错乱get就什么都查不到了。排查这个问题的最好办法不是debug而是写一个“先扩容后立即get全部旧数据”的测试一旦有遗漏立刻暴露。6. 高频面试题能进大厂的哈希表八股文6.1 基础问答速查我把近几年Java面试里跟哈希表相关的题目整理成了一张速查表覆盖了90%以上的概率会问到的问题。问题关键得分点HashMap的底层数据结构是什么JDK 8之前是数组加链表JDK 8之后是数组加链表加红黑树为什么链表转红黑树的阈值是8泊松分布下链表长度到8的概率极低属于极端场景的兜底负载因子0.75是怎么来的时间和空间成本的折中这是Hashtable和JDK源码注释里的经验值HashMap为什么线程不安全并发put可能导致数据覆盖JDK 7扩容可能产生环形链表JDK 8不会有环但仍有数据丢失问题HashMap怎么扩容的扩容为原长度的两倍用(e.hash oldCap)判断新位置要么原地不动要么加oldCap为什么容量必须是2的幂下标计算公式(n-1)hash只有在n是2的幂时才等价于取模而且可以用位运算加速hashCode和equals的关系equals相等则hashCode必须相等hashCode相等equals不一定相等HashMap允许null键和null值吗允许Hashtable不允许null键固定放在下标0的桶HashMap与HashSet的关系HashSet底层就是一个特殊HashMapvalue统一为固定占位对象高并发下用什么ConcurrentHashMapJava 8底层用CAS加synchronized锁粒度更细这十道题基本是“背多分”但光背答案是不够的。面试官只要追问一句“为什么8而不是10”或者“扩容时具体怎么迁移”你如果只停留在背结论立刻就会被识别出来。所以下面这些进阶细节才是真正拉分的点。6.2 容易翻车的进阶细节第一个翻车点是树化和反树化的条件。很多人知道链表长度到8会转红黑树但不知道还有一个前置条件数组长度必须达到64。如果链表长度已经是8但数组长度还不到64HashMap会优先扩容而不是树化。反树化也有条件红黑树中节点数降到6以下时会转回链表。为什么要留2的差值因为如果频繁插入删除导致长度在6到8之间震荡反复树化和反树化是很大的开销留个缓冲区间可以避免这种抖动。第二个翻车点是扩容时的并发问题。在JDK 7里两个线程同时resizeA线程的链表被B线程覆盖可能产生环形链表CPU瞬间飙到100%。JDK 8改进了这一点但并发put时仍可能出现数据覆盖两个线程同时put都发现桶是空的同时newNode后写的把先写的覆盖掉了。而且size本身不是原子的要分读-加-写三步并发下size会偏小导致该扩容时不扩容。所以记住HashMap不是线程安全的这不是选择题是定论。第三个翻车点是自定义key时的hashCode实现。有一次线上排查一个HashMap明明存了3000个元素get的性能却比刚创建时慢了百倍。最后定位到原因业务方自定义了一个对象当key它的hashCode方法被重写成了固定返回1。这导致所有元素都挤到同一个桶的链表里查询退化成O(n)。排查这类问题的思路很简单统计桶分布如果出现严重倾斜优先检查key的hashCode实现是否合理。7. 常见问题与性能调优实录7.1 常见问题速查表这一节整理我实际排查和指导过程中遇到的高频问题比算法题更贴近真实开发。现象根本原因解决方案key为null时map.put抛出NullPointerException自定义的api实现里没有处理null键包装一层null键时用特殊占位值两个对象equals一样但map里能同时存在两个key只重写了equals没重写hashCode同时重写两个方法用IDE的generate工具生成map.get频繁返回null但业务上确定存在该keykey对象在不同地方new出来时equals不一致检查equals实现和参与equals计算的字段哈希表插入性能正常但查询很慢大量key哈希值相同链表或红黑树过长检查hashCode实现改用String、Integer等自带高质量hashCode的key多线程环境偶发数据丢失HashMap并发put导致覆盖改用ConcurrentHashMap频繁扩容导致GC压力增大初始容量设置过小预估数据量提前设置容量或改用size预初始化迭代时抛ConcurrentModificationException遍历过程中做了结构性修改使用迭代器的remove方法操作7.2 从一次线上事故理解容量初始化有一次我帮朋友排查线上服务现象是老年代内存持续增长Full GC频繁但业务量并没有明显上升。用jmap dump之后发现内存里躺着上百个HashMap每个容量都从16开始经过多次扩容才达到几千的量级。每一个HashMap实例都带着一堆废弃的旧数组等着GC回收累积起来的垃圾量非常夸张。优化方案其实一句话在构造HashMap时显式传入初始容量。假设预估要存5000条数据那么初始容量可以直接设置成8192避免中间的多次扩容。这里我给出一个估算公式预估元素个数 目标数据量 / 负载因子 初始容量 向上取整到2的幂比如目标存5000个元素按负载因子0.75计算5000除以0.75约等于6667向上取整到2的幂正好是8192。这样从头到尾只需要分配一次数组。有同学会问容量设大了会不会浪费内存会但这是一个成本权衡。预留容量带来的空间浪费是固定的而扩容带来的CPU和GC开销是持续性的。在高频访问的场景下宁可多留一点容量也不要频繁触发扩容。还有一个更隐蔽的坑很多人以为new HashMap(5000)就能直接装5000条不出问题但这是错的。这个构造器只是让你指定容量它内部的table长度会被取整到8192threshold会被设置成(8192 * 0.75 6144)。也就是说你put到第6145个元素时就扩容了。如果你真的要装5000条给8000或者8192作为构造参数更稳妥。我给一个偷懒的通用建议如果要放n个元素构造时传(int)(n / 0.75f) 1这样一劳永逸不用担心threshold比n小的问题。8. 从入门到精通这些路线值得收藏如果你看完了上面的内容其实已经摸到了“精通”的门槛。Java哈希表这棵树的根是数组加链表的物理结构主干是哈希函数与冲突处理展开的枝丫覆盖HashMap底层实现、并发容器、面试考点和线上排查方法论。把这几条线串起来你脑子里自然就会形成一张完整的地图。我个人在实际操作中的体会是理解哈希表最有效的办法不是背八股文而是自己动手写一遍简易实现。等到亲手踩过“null键空指针”“扩容后数据错乱”“hashCode写成一坨导致性能雪崩”这几个坑之后那些源码里的细节才能真正长在你身上而不只是停留在收藏夹里吃灰。最后再分享一个小技巧在看任何Java集合类源码时始终带着三个问题去读——这个集合怎么存、怎么取、满了怎么办。一旦养成这个阅读习惯不仅是HashMapArrayList、LinkedList、TreeMap这些类你都能在半小时内摸清脉络。如果这篇文章对你有那么一点帮助动动手指点个收藏等真正要手写数据结构或者刷面试题的时候再翻出来对照着看一定会有新的收获。 深入理解哈希表：HashMap源码解析、冲突处理与性能调优
1. 哈希表到底解决了什么问题1.1 先看看数组和链表的局限我在带新人的时候经常被问到同一个问题“哈希表为什么不直接叫Hash Map非要叫哈希表”其实名字不关键关键是你得先搞清楚在没有哈希表之前我们查数据有多痛苦。假设你维护了一个员工名单存放在一个数组里数组的每个元素是一个员工对象包含工号、姓名和部门。现在给你一个工号让你把这个员工找出来。最笨的办法就是从头到尾遍历一遍运气好第一个就找到了运气不好最后一个才找到时间复杂度是O(n)。如果名单有一万个人平均要比较五千次才能找到目标。这种模型的痛点在于存储位置和查找关键字之间没有任何关系你只能靠挨个比对来碰运气。有没有一种办法让我拿着一个工号直接就算出它应该存在哪个格子连比较都不用做答案是肯定的这就是哈希表的出发点。再来看链表。链表解决了数组插入和删除时元素搬移的问题但查找依然是O(n)。而且在Java里链表对象本身有额外的节点开销每个节点需要存储前后指针内存占用并不小。哈希表就是冲着“查找也要快”这个目标去的它把数组的“随机访问”能力保留下来又通过一个哈希函数把任意关键字映射到数组下标从而做到平均O(1)的查找、插入和删除。1.2 哈希表的设计思路哈希表的整体思路可以浓缩成一句话用一个哈希函数把键Key映射成数组下标然后把值Value存到这个下标对应的位置。这里有个生活化的类比你去图书馆还书管理员不是一本一本翻书架找空位而是根据书号的后几位直接算出这本书应该放到哪个书架哪个格子。找书的时候也一样按同一个规则算出来直接走到那个格子取书不用全馆扫描。哈希表干的就是这件事。但这里冒出来一个绕不开的问题如果两个不同的键算出来的下标一样怎么办比如键是字符串“abc”和“cba”经过某个哈希函数都得到数值5那它们俩该放同一个格子还是分开这就是哈希冲突。哈希表的设计核心其实有一半工作量都在处理冲突另一半才是哈希函数本身。所以你要真正掌握哈希表第一件事就是把“哈希函数冲突处理”这对孪生兄弟搞清楚。2. 哈希函数与哈希冲突核心原理拆解2.1 哈希函数怎么选哈希函数的作用是把任意长度的输入字符串、数字、对象压缩成一个固定范围的整数。这个整数再经过一次取模运算就得到数组下标。这里要注意一个细节哈希函数算出来的数字不一定直接就是数组下标。因为哈希函数的输出范围通常远大于数组长度比如Java里Object类的hashCode方法返回的是int范围有2的32次方那么大而数组长度可能只有16。所以Java的做法是先拿到hashCode再做一次扰动然后通过“(n - 1) hash”这样的位运算得到一个落在数组范围内的下标。那“好的哈希函数”长什么样三个标准分布均匀不同的键尽量均匀地散落到各个桶里不要让某些桶挤爆、某些桶空着。计算高效哈希函数本身不能太复杂否则算一个下标要花大量CPU时间得不偿失。确定性同一个键任何时候算出来的结果必须一致否则存得进去取不出来。以Java的String为例它的hashCode实现是“s[0]*31^(n-1) s[1]*31^(n-2) ... s[n-1]”每次计算结果都一样满足确定性。31这个系数是经过大量实验选出来的因为它是一个不大不小的质数既能减少冲突又不会让乘法溢出得太离谱。但即便哈希函数选得很好冲突也只能减少不能消除。因为你的输入空间远大于数组空间根据鸽笼原理必然存在至少两个输入映射到同一个位置。所以冲突处理方案是必须具备的。2.2 两大冲突解决方案冲突处理的主流方案有两种链地址法和开放定址法。链地址法也叫拉链法思路非常直白数组每个下标位置不再直接存元素而是存一个链表后来Java 8升级成链表红黑树。当多个键映射到同一个下标时就把它们依次挂到这个链表后面。查找时先通过哈希函数定位到链表头再在链表里做线性查找。如果链表不长查找代价很小如果链表被恶意构造得很长比如所有键的哈希值都相同查找就退化成了O(n)这是哈希表最怕的极端场景。开放定址法思路是既然这个格子被占了那我就按某种规则去找下一个空位。常见的有线性探测依次往后找、二次探测按1、4、9…的步长跳和双重哈希用第二个哈希函数决定步长。这个方法的好处是不需要额外指针内存紧凑适合数据量可控、删除操作少的场景。但它的缺点也很明显删除操作麻烦因为你不能直接把某个格子清空否则会截断探测链导致后续元素查不到。ThreadLocalMap用的就是开放定址法这也是为什么它容量必须严格控制在某个比例以下。Java的HashMap选的是链地址法。原因很简单实现起来直接删除方便而且对哈希函数的均匀性要求没那么苛刻。更关键的是链地址法在冲突严重时可以退化成红黑树来兜底这是开放定址法做不到的。提示面试里如果被问到“HashMap和Hashtable有什么区别”底层冲突方案都可以顺带提一嘴。Hashtable和HashMap在冲突处理上都用链地址法但HashMap在Java 8之后引入树化机制这是两者底层实现的关键代差。3. Java里的哈希表家族HashMap实战必备3.1 HashMap底层结构演进JDK7到JDK8的变化很多老程序员是从JDK 7时代走过来的那会儿HashMap的底层结构是“数组链表”。到了JDK 8底层结构变成了“数组链表红黑树”。这个变化不是炫技而是针对哈希碰撞攻击和极端场景的防御性优化。在JDK 7里如果所有键都映射到同一个桶链表会无限变长查找一个元素的时间成了O(n)。这给了攻击者一个思路构造一堆哈希值相同的字符串塞进去就能把HashMap的查找性能拖垮这就是Hash攻击。JDK 8的解决方案是当链表长度超过阈值8时把链表转换成红黑树。红黑树的高度被严格限制在2log(n1)以内所以即使在最坏情况下查找时间也能控制在O(log n)。为什么要选8作为树化阈值源码里的注释解释过根据泊松分布在负载因子0.75的情况下桶中链表长度达到8的概率是千万分之六概率极低。所以8这个数字是“正常业务几乎不可能达到只有被刻意攻击或哈希函数完全失效时才可能”的警戒线。还有个细节新手容易忽略JDK 8的链表插入方式从“头插法”改成了“尾插法”。JDK 7的头插法在扩容时如果多个线程同时操作链表会出现环形引用直接导致CPU 100%。JDK 8改成尾插法之后虽然不能完全避免并发问题但至少不会出现环形链表这种致命bug了。3.2 三个关键参数初始容量、负载因子、树化阈值HashMap有三个构造参数分别是初始容量initialCapacity、负载因子loadFactor和树化阈值treeifyThreshold。树化阈值在前文中已经讲了固定值是8这里重点说前两个。初始容量默认是16必须是2的幂。为什么必须是2的幂因为HashMap计算下标用的不是取模而是位运算“hash (n - 1)”。这个公式只有在n是2的幂时才等价于“hash % n”而且位运算比取模快得多。如果你在构造时传了一个不是2的幂的数HashMap会帮你向上取整到最近的2的幂。比如你传17它实际会用到32。负载因子默认是0.75。它表示“当元素个数超过容量乘以负载因子时触发扩容”。扩容后的容量是原来的两倍。0.75是时间和空间成本的折中调小了比如0.5空间浪费严重但冲突少、查询快调大了比如1.0空间利用率高但冲突多、链表变长查询变慢。经验上默认值不要动除非你明确知道自己在做什么。这里给一个实操建议如果你预先知道要存多少数据最好在构造时就指定初始容量比如要存100个元素那就设成128之后就不会发生扩容。扩容是很贵的要重新计算所有元素的哈希值并把它们搬到新数组里这是一次完整的O(n)操作。// 预知100个元素主动指定容量避免扩容 MapString, Integer map new HashMap(128);3.3 HashMap与Hashtable、HashSet怎么选Java里有三个表面相似的类HashMap、Hashtable、HashSet。很多人分不清其实关系很清晰Hashtable是JDK 1.0时代遗留的线程安全哈希表所有方法都加了synchronized但这是粗粒度锁并发性能很差。它的另一个特点是不允许null键和null值。现在的新代码基本不会用它需要用线程安全的哈希表时选ConcurrentHashMap。HashMap是线程不安全的但性能最好允许null键和null值。单线程场景首选多线程场景可以搭配Collections.synchronizedMap()包装但在高并发下还是推荐ConcurrentHashMap。HashSet底层就是包装了一个HashMap键存元素本身值统一为一个固定的Object占位符。所以HashSet的contains方法本质上是HashMap的containsKey。这里补充一个冷知识HashMap允许null键但null键的上哈希值恒为0所以它永远会被放到数组下标为0的那个桶里。也就是说最多只能有一个null键。4. 从源码层面理解put/get/扩容4.1 put方法到底做了什么我习惯带着学员一行一行读put方法的源码。读完之后你就会发现之前记住的那些结论全部串起来了。final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { NodeK,V[] tab; NodeK,V p; int n, i; // 如果table还没初始化先触发resize() if ((tab table) null || (n tab.length) 0) n (tab resize()).length; // 计算下标如果这个桶是空的直接放一个新节点 if ((p tab[i (n - 1) hash]) null) tab[i] newNode(hash, key, value, null); else { NodeK,V e; K k; // 第一个节点的key就相等直接覆盖 if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) e p; // 如果已经是红黑树节点走红黑树插入 else if (p instanceof TreeNode) e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value); else { // 遍历链表统计长度 for (int binCount 0; ; binCount) { // 遍历到链表尾部追加新节点 if ((e p.next) null) { p.next newNode(hash, key, value, null); // 链表长度达到树化阈值转换红黑树 if (binCount TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } // 链表里找到了相同的key跳出覆盖 if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) break; p e; } } // 覆盖旧值 if (e ! null) { V oldValue e.value; if (!onlyIfAbsent || oldValue null) e.value value; afterNodeAccess(e); return oldValue; } } modCount; // 超过了扩容阈值触发扩容 if (size threshold) resize(); afterNodeInsertion(evict); return null; }读这段源码建议盯住三个关键分支第一个分支是数组对应位置为空直接放新节点这是哈希表最理想的情况O(1)完成。第二个分支是命中了一个链表或树此时需要遍历去查找key是否已经存在。如果存在就覆盖value如果不存在就在尾部追加新节点。这里有个隐藏的成本点链表遍历是O(m)m是链表长度。如果业务数据出现大量哈希碰撞put就会从O(1)恶化成O(m)。第三个分支是扩容判断。注意size threshold这个判断在插入之后执行意味着“先插入、后扩容”。扩容之后所有元素的桶位置都要重新计算。4.2 get的查找流程get的逻辑比put简单但同样有几个容易被忽略的细节final NodeK,V getNode(int hash, Object key) { NodeK,V[] tab; NodeK,V first, e; int n; K k; if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) { // 检查第一个节点 if (first.hash hash ((k first.key) key || (key ! null key.equals(k)))) return first; // 后续节点树节点走树查找链表节点走循环扫描 if ((e first.next) ! null) { if (first instanceof TreeNode) return ((TreeNodeK,V)first).getTreeNode(hash, key); do { if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) return e; } while ((e e.next) ! null); } } return null; }注意这里判断key相等用的是(key ! null key.equals(k))这说明你放在HashMap里的keyequals方法一定要正确实现。如果两个对象equals相等但hashCode不一致或者hashCode一致但equals不相等都会导致get不到预期的值。这就是大家常说的hashCode与equals的约定。更精确地说两个对象equals相等则hashCode必须相等两个对象hashCode相等equals不一定相等。前一个是硬性要求违反了它HashMap直接失效后一个是哈希冲突可以接受。所以小小的自定义类型放进HashMap时equals和hashCode必须同时重写否则就等着线上莫名其妙的bug吧。4.3 resize扩容最耗时的操作扩容是HashMap里开销最大的操作没有之一。它做了两件事第一把数组长度扩大到原来的两倍第二把旧数组里的所有节点重新分配到新数组里。在JDK 8的扩容实现里节点迁移不是简单地把每个节点重新走下标的取模流程而是用了一个非常巧妙的优化。因为扩容是乘以2所以每个节点的新下标只有两种可能要么是原下标要么是原下标加上旧数组长度。判断的关键在于新取的那一位bit是0还是1。源码里用(e.hash oldCap)来判断结果为0留在原位置结果为1移动到“原位置oldCap”。举个例子旧数组长度是16某个节点的hash是5那它能占到下标n-1 hash的结果是5。扩容到32之后新下标是32-1 5还是5。但另一个节点hash是21它在旧数组中下标是16-1 21 5在新数组中下标是32-1 21 21正好是516。所以“原下标”还是“原下标16”取决于hash从低到高的第5位因为16对应二进制的第5位是0还是1。这个优化让扩容不用重新计算每个节点的整条哈希链只需看一个bit位性能提升非常大。它同时也是理解ConcurrentHashMap扩容的基础。5. 手写一个简单HashMap可直接复制的版本5.1 设计思路读源码读得再多都不如自己动手写一个来得通透。我在带训练营的时候会布置这样一个任务用Java手写一个支持泛型的简易HashMap要求能put、get、remove能自动扩容并且正确处理哈希冲突。设计思路分四步走数据结构底层用一个Node数组每个Node是一个单向链表节点包含key、value、hash和next。哈希函数用key的hashCode再做一次扰动减少低位的碰撞概率。这里为了演示简单直接用“key.hashCode() ^ (key.hashCode() 16)”。下标计算假设数组长度是2的幂用“(len - 1) hash”算下标。冲突处理链表法新节点挂链表尾部。同时维护size和thresholdsize超过threshold就扩容。5.2 核心实现代码public class SimpleHashMapK, V { // 链表节点 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; } } private static final int DEFAULT_CAPACITY 16; // 这里为了演示负载因子取0.75 private static final float DEFAULT_LOAD_FACTOR 0.75f; private NodeK, V[] table; private int size; private int threshold; SuppressWarnings(unchecked) public SimpleHashMap(int initialCapacity) { int capacity 1; // 确保容量是2的幂 while (capacity initialCapacity) { capacity 1; } table (NodeK, V[]) new Node[capacity]; threshold (int) (capacity * DEFAULT_LOAD_FACTOR); } public SimpleHashMap() { this(DEFAULT_CAPACITY); } private int hash(K key) { if (key null) { return 0; } int h key.hashCode(); return h ^ (h 16); } private int indexFor(int hash, int length) { return (length - 1) hash; } public void put(K key, V value) { int hash hash(key); int index indexFor(hash, table.length); NodeK, V first table[index]; if (first null) { table[index] new Node(hash, key, value, null); size; } else { NodeK, V cur first; while (cur ! null) { if (cur.hash hash (cur.key key || (cur.key ! null cur.key.equals(key)))) { cur.value value; return; } if (cur.next null) { break; } cur cur.next; } cur.next new Node(hash, key, value, null); size; } if (size threshold) { resize(); } } public V get(K key) { int hash hash(key); int index indexFor(hash, table.length); NodeK, V cur table[index]; while (cur ! null) { if (cur.hash hash (cur.key key || (cur.key ! null cur.key.equals(key)))) { return cur.value; } cur cur.next; } return null; } public V remove(K key) { int hash hash(key); int index indexFor(hash, table.length); NodeK, V prev null; NodeK, V cur table[index]; while (cur ! null) { if (cur.hash hash (cur.key key || (cur.key ! null cur.key.equals(key)))) { if (prev null) { table[index] cur.next; } else { prev.next cur.next; } size--; return cur.value; } prev cur; cur cur.next; } return null; } SuppressWarnings(unchecked) private void resize() { NodeK, V[] oldTable table; NodeK, V[] newTable (NodeK, V[]) new Node[oldTable.length * 2]; for (NodeK, V node : oldTable) { while (node ! null) { NodeK, V next node.next; int newIndex (newTable.length - 1) node.hash; node.next newTable[newIndex]; newTable[newIndex] node; node next; } } table newTable; threshold (int) (table.length * DEFAULT_LOAD_FACTOR); } public int size() { return size; } }这个版本大概60行核心逻辑覆盖了哈希表最关键的能力。注意我在resize里用了“头插法”来提高效率演示版本里可以这么写因为它是单线程的不会出现并发环链。但你在JDK 8源码里看到的是尾插法这是有讲究的并发场景下头插法更容易产生环所以JDK团队在8里改了。5.3 测试与踩坑写完之后我会让学生跑几个测试用例put 1000个随机键值对、get全部读回来、remove一半、再put另一半。这样能验证基本功能但不能验证哈希函数的质量。真正要检验哈希分布得自己写一段统计代码往里面put一万个键统计每个桶里链表长度的标准差。标准差越小说明分布越均匀。我第一次写这个demo时踩过一个坑忘记处理key为null的情况。虽然HashMap允许null键但我的hash方法里没有对null做特殊处理直接调用key.hashCode()结果一放null键就空指针了。后来加上if (key null) return 0;才解决。这个坑也侧面说明了简单性背后全是细节。还有一个坑在resize方法里。如果newTable的长度计算错了或者indexFor里用的是旧表长度扩容后数据全部错乱get就什么都查不到了。排查这个问题的最好办法不是debug而是写一个“先扩容后立即get全部旧数据”的测试一旦有遗漏立刻暴露。6. 高频面试题能进大厂的哈希表八股文6.1 基础问答速查我把近几年Java面试里跟哈希表相关的题目整理成了一张速查表覆盖了90%以上的概率会问到的问题。问题关键得分点HashMap的底层数据结构是什么JDK 8之前是数组加链表JDK 8之后是数组加链表加红黑树为什么链表转红黑树的阈值是8泊松分布下链表长度到8的概率极低属于极端场景的兜底负载因子0.75是怎么来的时间和空间成本的折中这是Hashtable和JDK源码注释里的经验值HashMap为什么线程不安全并发put可能导致数据覆盖JDK 7扩容可能产生环形链表JDK 8不会有环但仍有数据丢失问题HashMap怎么扩容的扩容为原长度的两倍用(e.hash oldCap)判断新位置要么原地不动要么加oldCap为什么容量必须是2的幂下标计算公式(n-1)hash只有在n是2的幂时才等价于取模而且可以用位运算加速hashCode和equals的关系equals相等则hashCode必须相等hashCode相等equals不一定相等HashMap允许null键和null值吗允许Hashtable不允许null键固定放在下标0的桶HashMap与HashSet的关系HashSet底层就是一个特殊HashMapvalue统一为固定占位对象高并发下用什么ConcurrentHashMapJava 8底层用CAS加synchronized锁粒度更细这十道题基本是“背多分”但光背答案是不够的。面试官只要追问一句“为什么8而不是10”或者“扩容时具体怎么迁移”你如果只停留在背结论立刻就会被识别出来。所以下面这些进阶细节才是真正拉分的点。6.2 容易翻车的进阶细节第一个翻车点是树化和反树化的条件。很多人知道链表长度到8会转红黑树但不知道还有一个前置条件数组长度必须达到64。如果链表长度已经是8但数组长度还不到64HashMap会优先扩容而不是树化。反树化也有条件红黑树中节点数降到6以下时会转回链表。为什么要留2的差值因为如果频繁插入删除导致长度在6到8之间震荡反复树化和反树化是很大的开销留个缓冲区间可以避免这种抖动。第二个翻车点是扩容时的并发问题。在JDK 7里两个线程同时resizeA线程的链表被B线程覆盖可能产生环形链表CPU瞬间飙到100%。JDK 8改进了这一点但并发put时仍可能出现数据覆盖两个线程同时put都发现桶是空的同时newNode后写的把先写的覆盖掉了。而且size本身不是原子的要分读-加-写三步并发下size会偏小导致该扩容时不扩容。所以记住HashMap不是线程安全的这不是选择题是定论。第三个翻车点是自定义key时的hashCode实现。有一次线上排查一个HashMap明明存了3000个元素get的性能却比刚创建时慢了百倍。最后定位到原因业务方自定义了一个对象当key它的hashCode方法被重写成了固定返回1。这导致所有元素都挤到同一个桶的链表里查询退化成O(n)。排查这类问题的思路很简单统计桶分布如果出现严重倾斜优先检查key的hashCode实现是否合理。7. 常见问题与性能调优实录7.1 常见问题速查表这一节整理我实际排查和指导过程中遇到的高频问题比算法题更贴近真实开发。现象根本原因解决方案key为null时map.put抛出NullPointerException自定义的api实现里没有处理null键包装一层null键时用特殊占位值两个对象equals一样但map里能同时存在两个key只重写了equals没重写hashCode同时重写两个方法用IDE的generate工具生成map.get频繁返回null但业务上确定存在该keykey对象在不同地方new出来时equals不一致检查equals实现和参与equals计算的字段哈希表插入性能正常但查询很慢大量key哈希值相同链表或红黑树过长检查hashCode实现改用String、Integer等自带高质量hashCode的key多线程环境偶发数据丢失HashMap并发put导致覆盖改用ConcurrentHashMap频繁扩容导致GC压力增大初始容量设置过小预估数据量提前设置容量或改用size预初始化迭代时抛ConcurrentModificationException遍历过程中做了结构性修改使用迭代器的remove方法操作7.2 从一次线上事故理解容量初始化有一次我帮朋友排查线上服务现象是老年代内存持续增长Full GC频繁但业务量并没有明显上升。用jmap dump之后发现内存里躺着上百个HashMap每个容量都从16开始经过多次扩容才达到几千的量级。每一个HashMap实例都带着一堆废弃的旧数组等着GC回收累积起来的垃圾量非常夸张。优化方案其实一句话在构造HashMap时显式传入初始容量。假设预估要存5000条数据那么初始容量可以直接设置成8192避免中间的多次扩容。这里我给出一个估算公式预估元素个数 目标数据量 / 负载因子 初始容量 向上取整到2的幂比如目标存5000个元素按负载因子0.75计算5000除以0.75约等于6667向上取整到2的幂正好是8192。这样从头到尾只需要分配一次数组。有同学会问容量设大了会不会浪费内存会但这是一个成本权衡。预留容量带来的空间浪费是固定的而扩容带来的CPU和GC开销是持续性的。在高频访问的场景下宁可多留一点容量也不要频繁触发扩容。还有一个更隐蔽的坑很多人以为new HashMap(5000)就能直接装5000条不出问题但这是错的。这个构造器只是让你指定容量它内部的table长度会被取整到8192threshold会被设置成(8192 * 0.75 6144)。也就是说你put到第6145个元素时就扩容了。如果你真的要装5000条给8000或者8192作为构造参数更稳妥。我给一个偷懒的通用建议如果要放n个元素构造时传(int)(n / 0.75f) 1这样一劳永逸不用担心threshold比n小的问题。8. 从入门到精通这些路线值得收藏如果你看完了上面的内容其实已经摸到了“精通”的门槛。Java哈希表这棵树的根是数组加链表的物理结构主干是哈希函数与冲突处理展开的枝丫覆盖HashMap底层实现、并发容器、面试考点和线上排查方法论。把这几条线串起来你脑子里自然就会形成一张完整的地图。我个人在实际操作中的体会是理解哈希表最有效的办法不是背八股文而是自己动手写一遍简易实现。等到亲手踩过“null键空指针”“扩容后数据错乱”“hashCode写成一坨导致性能雪崩”这几个坑之后那些源码里的细节才能真正长在你身上而不只是停留在收藏夹里吃灰。最后再分享一个小技巧在看任何Java集合类源码时始终带着三个问题去读——这个集合怎么存、怎么取、满了怎么办。一旦养成这个阅读习惯不仅是HashMapArrayList、LinkedList、TreeMap这些类你都能在半小时内摸清脉络。如果这篇文章对你有那么一点帮助动动手指点个收藏等真正要手写数据结构或者刷面试题的时候再翻出来对照着看一定会有新的收获。