面向 Java / Android 高级开发岗位的复习文档。本文以JDK 8 的java.util.HashMap为主线重点讲清数据结构、hash扰动、put/get、冲突处理、扩容、红黑树、线程安全与高频追问。版本提醒不同 JDK 版本的实现细节可能变化。面试回答时最好明确“以 JDK 8 为例”。目录HashMap 是什么底层数据结构Node 节点结构hash 扰动函数为什么容量通常是 2 的幂put 的完整流程hash 冲突与 equalsget 的查找流程扩容条件、负载因子与阈值resize 扩容迁移原理链表为什么转红黑树JDK 7 与 JDK 8 的主要区别HashMap 为什么线程不安全HashMap 的 null 规则时间复杂度与性能equals 和 hashCode 的契约迭代器与 fail-fast如何正确初始化容量与 ConcurrentHashMap 的区别高频面试题速答源码阅读路线与总结1. HashMap 是什么HashMapK, V是 Java 集合框架中的键值映射容器。它根据 key 的哈希值定位存储桶再通过 key 的相等性判断找到具体映射。MapString,IntegerscoresnewHashMap();scores.put(Tom,90);scores.put(Jerry,85);Integerscorescores.get(Tom);// 90主要特点以常见 JDK 8 实现为准不保证 key 的迭代顺序。允许一个nullkey允许多个nullvalue。非线程安全多个线程并发修改需要额外同步或使用并发容器。平均情况下put、get、remove接近 O(1)。容量不足时会扩容冲突严重的桶可能树化。面试回答模板HashMap 是基于哈希表的 Map 实现。JDK 8 中底层是 Node 数组桶内元素通过链表或红黑树组织。它先对 key 的 hashCode 做扰动再通过(n - 1) hash定位桶发生冲突时比较 hash 并结合、equals()判断 key 是否相同。元素数量超过阈值时会扩容。HashMap 不保证顺序也不是线程安全容器。2. 底层数据结构JDK 8 的主要结构HashMap | -- table: NodeK,V[] | -- bucket[0] - null -- bucket[1] - Node - Node - ... -- bucket[2] - TreeNode树化后 -- ...数组table根据 hash 快速定位桶。链表多个元素映射到同一桶时且该桶尚未树化就通过链表保存。红黑树桶内冲突严重且满足条件时用平衡树降低查找复杂度。为什么采用这种组合单纯链表查找可能退化到 O(n)。单纯红黑树会增加节点结构和维护成本。数组 链表 红黑树在常规场景下兼顾效率和空间。3. Node 节点结构JDK 8 中普通节点的核心结构可概括为staticclassNodeK,VimplementsMap.EntryK,V{finalinthash;finalKkey;Vvalue;NodeK,Vnext;publicfinalinthashCode(){returnObjects.hashCode(key)^Objects.hashCode(value);}publicfinalKgetKey(){returnkey;}publicfinalVgetValue(){returnvalue;}publicfinalVsetValue(VnewValue){Voldvalue;valuenewValue;returnold;}}重点hash插入时计算并保存的扰动后哈希值。key声明为final节点创建后不能换成另一个 key 引用。value可以更新。next链表中的下一个节点树化节点使用TreeNode扩展结构。同一个 key 再次put时一般是更新已有节点的value而不是插入重复 key。4. hash 扰动函数JDK 8 的核心逻辑staticfinalinthash(Objectkey){inth;return(keynull)?0:(hkey.hashCode())^(h16);}4.1 为什么不直接使用key.hashCode()桶索引计算为index(n-1)hash;当容量n 16时n - 1 15二进制是0000...1111。与它做 AND实际上主要取 hash 的低 4 位。如果多个 key 的低位相同即使高位不同也可能被放进同一个桶。4.2(h 16)是什么是无符号右移。对 32 位int右移 16 位相当于把原来的高 16 位移到低 16 位。再执行h ^ (h 16)让原 hash 的高位信息参与低位计算。简化示意原 h: [ 高 16 位 ][ 低 16 位 ] h 16: [ 0 ][ 原高16位 ] 异或结果: [ 高 16 位 ][ 低位与高位混合 ]目的不是保证绝不冲突而是让 hash 的低位分布更充分降低部分冲突概率。5. 为什么容量通常是 2 的幂HashMap 用下面的方式计算桶索引index(n-1)hash;当n是 2 的幂时n - 1的二进制低位全为 1。例如n 16 - 00010000 n - 1 15 - 00001111这样可以通过位运算快速取出低位作为索引避免使用取模运算。JDK 8 在构造时传入非 2 的幂容量通常会通过tableSizeFor()将其调整为大于等于目标值的最小 2 的幂受最大容量限制。注意容量为 2 的幂是为了让索引计算与扩容优化成立不是说只要容量为 2 的幂就能完全避免哈希冲突。6. put 的完整流程调用map.put(key,value);总体流程put(key, value) | v 计算扰动后的 hash | v table 是否初始化-- 否 -- 初始化数组 | v index (n - 1) hash | -- 桶为空直接创建节点 | -- 桶非空 | -- 首节点 key 相同更新 value | -- 桶是红黑树调用树插入逻辑 | -- 桶是链表遍历查找 | -- 找到相同 key更新 value | -- 没找到追加新节点 | -- 达到树化判断条件尝试树化 | v 若是新映射sizemodCount | v size threshold-- 是 -- resize()6.1 延迟初始化if((tabtable)null||(ntab.length)0)n(tabresize()).length;new HashMap()通常不会立即分配默认的 16 个桶。第一次插入时才初始化内部数组这叫延迟初始化。6.2 桶为空tab[i]newNode(hash,key,value,null);直接将新节点放到该桶。6.3 首节点是否为相同 keyif(p.hashhash((kp.key)key||(key!nullkey.equals(k)))){ep;}判断顺序先比较 hashhash 不同则一定不是同一个映射 key。再判断引用是否相同。最后用equals()判断逻辑相等。6.4 链表遍历遍历链表如果找到 hash 相同且 key 相等的节点更新其 value。如果走到链表末尾仍未找到则创建新节点追加。新节点插入后可能触发树化判断。6.5 更新 value 的返回值put返回旧 value如果之前没有该 key则返回null。因此返回null不一定能区分“原来没有 key”和“原来的 value 就是 null”。7. hash 冲突与 equals7.1 什么是 hash 冲突不同 key 的 hash 值可能相同即使 hash 值不同也可能在取桶索引时得到同一个 index。keyA - hashA - bucket[3] keyB - hashB - bucket[3]这就是桶冲突。哈希值是有限位数而 key 的可能数量远远更多因此冲突不可避免。7.2 为什么必须调用 equalshashCode()不是唯一标识。HashMap 不能仅凭 hash 相同就认定 key 相同。StringanewString(abc);StringbnewString(abc);System.out.println(ab);// false不同对象System.out.println(a.equals(b));// true内容相等System.out.println(a.hashCode()b.hashCode());// trueHashMap 通过 hash 缩小范围再通过/equals()精确判断。7.3 自定义 key 示例finalclassUserKey{privatefinalintid;UserKey(intid){this.idid;}OverridepublicinthashCode(){return1;// 故意制造冲突仅用于演示}Overridepublicbooleanequals(Objectobj){if(thisobj)returntrue;if(!(objinstanceofUserKey))returnfalse;UserKeyother(UserKey)obj;returnidother.id;}}MapUserKey,StringmapnewHashMap();map.put(newUserKey(1),A);map.put(newUserKey(2),B);System.out.println(map.size());// 2hash 相同但 equals 为 falsemap.put(newUserKey(1),C);System.out.println(map.size());// 2逻辑上相同的 key更新 value8. get 的查找流程Vget(Objectkey)核心步骤计算 key 的扰动 hash。根据(n - 1) hash找到桶。检查桶的第一个节点。如果首节点不匹配若为树节点按红黑树逻辑查找否则遍历链表。找到 hash 相同且 key 相等的节点后返回 value找不到返回null。逻辑示意get(key) | 计算 hash 与 index | 定位 table[index] | 比较 hash / equals | 链表遍历或红黑树查找 | 返回 value / null9. 扩容条件、负载因子与阈值常见默认值DEFAULT_INITIAL_CAPACITY16;DEFAULT_LOAD_FACTOR0.75f;阈值通常为thresholdcapacity*loadFactor;默认容量 16 时阈值通常是 12。新映射插入后如果size threshold会触发扩容。9.1 负载因子是什么负载因子控制数组空间利用率和冲突程度之间的折中较低更早扩容通常冲突更少但占用更多数组空间。较高空间利用率更高但桶冲突可能更多。0.75是 JDK 的常用默认折中并不是所有业务下的数学最优值。9.2 是不是每次 put 都可能扩容不是。通常只有新增映射后size超过threshold才会触发容量扩展更新已有 key 的 value 不增加size不会因为这次更新而触发该扩容判断。9.3 构造参数注意事项newHashMap(64);参数表示初始容量需求不是“插入 64 个元素才扩容”的阈值。内部容量会调整为合适的 2 的幂阈值再根据负载因子计算。10. resize 扩容迁移原理这是 JDK 8 的高频重点。10.1 容量翻倍常规情况下16 - 32 - 64 - 128源码通过newCapoldCap1;实现容量翻倍。10.2 为什么元素只会留在原位置或移动oldCap旧索引oldIndexhash(oldCap-1);新容量为newCap oldCap * 2新索引newIndexhash(newCap-1);新掩码相比旧掩码只多出oldCap对应的那一位。因此新索引只有两种可能newIndex oldIndex 或 newIndex oldIndex oldCap10.3(e.hash oldCap) 0是什么含义if((e.hasholdCap)0){// 留在原索引 j}else{// 移到 j oldCap}oldCap本身是 2 的幂它对应扩容时新增的那一位。与运算结果为 0新增位为 0留在j。与运算结果非 0新增位为 1移动到j oldCap。10.4 示例16 扩到 32旧桶索引为 5扩容后只可能去 5 或 21原位置5 新位置5 16 21源码通过hash 16判断不需要重新调用key.hashCode()也不必重新计算完整 hash。10.5 链表拆分JDK 8 将旧桶链表拆成两条lo链表留在原索引j。hi链表移动到j oldCap。通过 head/tail 方式拼接保持各自链表中节点的相对顺序并在结尾将尾节点的next置为null。10.6 扩容成本扩容需要创建新数组并迁移已有节点因此一次扩容是 O(n) 级别操作。不过在容量逐步翻倍的情况下普通put的摊还时间复杂度仍通常为 O(1)。11. 链表为什么转红黑树JDK 8 常见常量TREEIFY_THRESHOLD8;UNTREEIFY_THRESHOLD6;MIN_TREEIFY_CAPACITY64;需要理解的细节TREEIFY_THRESHOLD 8是触发树化判断的阈值不应简单说成“链表一到 8 个节点就一定树化”。在putVal的链表插入逻辑中binCount的计数方式会影响触发时机。如果 table 容量小于 64treeifyBin()通常优先尝试扩容而不是立即树化。扩容拆分树桶时如果拆分后的某一侧节点数较少可能退化为链表UNTREEIFY_THRESHOLD常用于相关判断。为什么红黑树可以改善性能链表查找最坏 O(n)。红黑树保持近似平衡查找通常为 O(log n)。引入树结构也有额外内存和维护成本所以只在冲突严重时采用。12. JDK 7 与 JDK 8 的主要区别对比点JDK 7典型实现JDK 8桶内结构数组 链表数组 链表 红黑树冲突严重时链表可能很长满足条件时树化插入链表典型实现使用头插使用尾部追加便于保持拆分顺序扩容迁移重新计算/定位元素位置利用hash oldCap将节点拆到原位置或原位置 oldCap并发安全不安全仍然不安全不要把“JDK 8 解决了 HashMap 线程安全问题”当成结论JDK 8 的 HashMap 依旧不是线程安全容器。13. HashMap 为什么线程不安全HashMap 没有为普通并发读写提供完整的同步保障。多个线程同时修改可能出现更新覆盖、数据丢失。size等内部状态不符合调用方预期。并发扩容或链表修改期间出现不一致的结构与读取结果。读线程可能看不到另一个线程刚写入的值没有同步关系时也不具备所需的可见性保证。JDK 7 的某些并发扩容交错可能导致链表成环、读取时循环JDK 8 改了迁移实现但不代表并发修改变安全。解决方式有同步需求时使用ConcurrentHashMap。简单场景可用Collections.synchronizedMap(new HashMap())但遍历时也要按其要求同步。多线程只读且安全发布、无后续修改的场景需要根据具体对象生命周期判断。14. HashMap 的 null 规则HashMap 允许map.put(null,A);// 允许map.put(name,null);// 允许map.put(age,null);// 允许nullkey 最多一个因为 Map 中 key 不能重复。nullvalue 可以有多个。JDK 8 的hash(null)返回 0null key 会映射到索引 0因为索引计算为(n - 1) 0。注意get(key) null可能表示 key 不存在也可能表示该 key 对应的 value 就是 null。可以用containsKey(key)区分。15. 时间复杂度与性能操作 / 情况常见复杂度说明get/put平均情况O(1)hash 分布较好、冲突较少链表桶查找O(k)k 为该桶链表长度树化桶查找通常 O(log k)红黑树结构扩容O(n)需要迁移已有节点全量遍历O(capacity size)需要扫描 table 与元素面试时不要无条件回答“HashMap 查询永远是 O(1)”。更准确的说法是平均 O(1)具体取决于 hash 分布、桶结构和扩容等情况。16. equals 和 hashCode 的契约Java 的基本约定如果a.equals(b)为true则a.hashCode() b.hashCode()必须成立。hashCode()相同不要求equals()为true。在参与比较的字段未改变时多次调用hashCode()应保持一致。错误示例只重写equals()却没有正确重写hashCode()。逻辑上相等的对象可能被分配到不同桶导致 Map 查找异常。更重要的实践建议不要修改已经作为 HashMap key 的对象中参与equals()/hashCode()计算的字段。例如插入时id 1后来把id改成 2查找时新 hash 可能定位到另一个桶原映射就可能难以通过该 key 找到。17. 迭代器与 fail-fastHashMap 的迭代器通常使用modCount检测结构性修改。新增或删除映射通常属于结构性修改。只更新已有 key 的 value 通常不属于结构性修改。迭代过程中检测到未通过迭代器自身允许的结构性修改可能抛出ConcurrentModificationException。这叫fail-fast快速失败。重要fail-fast 是尽力而为的错误检测机制不能作为线程同步手段也不保证每次并发修改都一定抛异常。18. 如何正确初始化容量如果预估要放入expectedSize个元素且希望在插入期间尽量避免扩容可以按负载因子估算所需容量再让 HashMap 调整到合适的 2 的幂。intexpectedSize100;floatloadFactor0.75f;intinitialCapacity(int)(expectedSize/loadFactor)1;MapInteger,StringmapnewHashMap(initialCapacity);这只是常见估算方式极大容量要注意整数溢出和最大容量限制。不要简单认为new HashMap(100)就一定能无扩容存放 100 个元素因为构造参数和最终阈值不是同一个概念。19. 与 ConcurrentHashMap 的区别对比点HashMapConcurrentHashMapJDK 8线程安全否是支持并发访问并发控制无内置完整同步CAS、synchronized等机制nullkey/value允许不允许冲突结构链表 / 红黑树链表 / 红黑树扩容普通单线程迁移逻辑可由多个线程协助扩容适用场景无并发修改或外部同步多线程共享映射ConcurrentHashMap 不是简单地给整个 HashMap 加一把大锁。JDK 8 通过 CAS、桶级同步以及协助扩容等机制提高并发度。20. 高频面试题速答Q1HashMap 底层是什么JDK 8 中是 Node 数组桶内使用链表或红黑树。数组用于快速定位桶链表和红黑树处理冲突。Q2(h key.hashCode()) ^ (h 16)是什么hash 扰动函数。将高 16 位信息混入低位改善低位分布降低部分冲突概率。Q3为什么用(n - 1) hash容量为 2 的幂时n - 1的低位全为 1可以用位运算快速得到桶索引。Q4hash 相同就认为 key 相同吗不是。hash 只用于定位或缩小范围还要通过引用相同或equals()判断 key 是否相同。Q5为什么要重写 equals 和 hashCode让逻辑相等的对象具有一致的 hash 值并能按业务定义判断相等否则 Map 的查找和去重行为可能不符合预期。Q6默认容量和负载因子是多少常见默认值是容量 16、负载因子 0.75内部 table 通常延迟到首次插入时初始化。Q7什么时候扩容新映射插入后如果size threshold通常触发扩容。默认容量 16、负载因子 0.75 时初始阈值通常为 12。Q8JDK 8 扩容为什么看hash oldCap容量翻倍只新增一个索引位。该位为 0节点留在原位置为 1节点移动到原位置 oldCap。Q9链表达到 8 个节点就一定树化吗不一定。树化触发判断还与插入计数有关若数组容量小于 64通常先尝试扩容。Q10HashMap 线程安全吗不安全。并发修改可能导致更新丢失、状态不一致等问题共享并发场景应考虑 ConcurrentHashMap 或适当同步。Q11HashMap 为什么允许一个 null keyJDK 8 对 null key 的 hash 直接返回 0因此会映射到索引 0。Map 的 key 唯一性规则仍然适用所以最多一个 null key。Q12get()返回 null 代表什么可能 key 不存在也可能 key 存在但 value 为 null。使用containsKey()可进一步判断。Q13HashMap 的迭代顺序稳定吗不保证。不要依赖它的遍历顺序需要可预测顺序时考虑 LinkedHashMap 或 TreeMap具体按需求选择。Q14扩容时为什么不用重新调用 key.hashCode()节点已经保存了扰动后的hash字段。JDK 8 可以利用这个 hash 和新增索引位完成迁移不需要再次调用 key 的hashCode()。Q15把可变对象当 key 有什么风险如果参与equals()/hashCode()的字段在插入后发生变化查找时可能定位到不同桶从而无法按预期找到原映射。21. 源码阅读路线与总结建议按以下顺序阅读 JDK 8 的HashMaphash(Object key)看扰动函数。put()/putVal()看桶定位、key 相等判断、链表与树插入。get()/getNode()看查找。resize()看扩容与链表拆分。treeifyBin()看树化条件。TreeNode相关方法了解红黑树插入、查找、拆分。HashIterator看迭代器和modCount。最后把整个过程背成一条链put(key, value) | v hashCode() | v h ^ (h 16) | v (n - 1) hash | v 定位 table[index] | -- 空桶创建节点 | -- 冲突hash / equals | -- 相同 key更新 value | -- 不同 key链表 / 红黑树插入 | v 新映射使 size 增加 | v size threshold | -- 是resize() | v hash oldCap | -- 0留在原位置 | -- 非 0移动到原位置 oldCap面试优先级建议必须讲熟底层结构、hash 扰动、索引计算、putVal()、equals/hashCode、扩容。高级开发要会红黑树条件、负载因子、JDK 7/8 区别、null 规则、fail-fast。专家岗继续深挖resize()的链表拆分、红黑树退化、并发问题、ConcurrentHashMap 的 CAS /synchronized/ 协助扩容。复习时尽量结合源码自己手推一个例子容量从 16 扩到 32某个桶中的多个节点分别根据hash 16留在原位置或移动到原位置 16。能解释清楚这一步就真正理解了 JDK 8 HashMap 扩容的关键设计。