予枫个人主页 个人专栏: 《Java 从入门到起飞》《读研码农的干货日常》《Java 面试刷题指南》 Debug 这个世界Return 更好的自己引言面试官“HashMap的哈希冲突怎么解决扩容机制是什么红黑树什么时候转换” 这三个问题几乎是Java面试的必考题也是区分新手和进阶程序员的关键。很多人只背结论却不懂底层源码逻辑面试一被追问就露馅。今天就逐行拆解HashMap源码把哈希冲突、扩容机制、红黑树转换讲透还附带面试官高频追问帮你面试稳拿分文章目录引言一、HASHMAP 核心基础面试铺垫1.1 核心成员变量源码直击二、哈希冲突成因与解决方案核心考点2.1 哈希冲突的成因源码拆解hash(key)方法JDK82.2 HashMap解决哈希冲突的核心方案链地址法结构示意图三、扩容机制什么时候扩怎么扩高频追问3.1 扩容的触发条件3.2 扩容的核心流程源码拆解扩容的关键细节四、红黑树转换什么时候转为什么转4.1 红黑树转换的条件源码核心逻辑源码片段treeifyBin()方法4.2 红黑树转链表的条件4.3 红黑树的核心作用五、全文总结一、HASHMAP 核心基础面试铺垫HashMap是Java中最常用的集合之一核心作用是键值对存储底层基于“数组链表红黑树”的结构实现JDK8及以后兼顾查询和插入效率。先明确两个核心前提帮你快速入门核心优势查询、插入、删除效率接近O(1)前提是哈希函数设计合理减少冲突核心特性key不允许重复重复会覆盖value、key和value都可以为null、非线程安全底层结构演变JDK7是“数组链表”JDK8引入红黑树解决链表过长导致的查询效率下降问题 小提示觉得有用的话点赞收藏避免面试前找不到这篇干货1.1 核心成员变量源码直击先看HashMap的核心成员变量理解它的底层配置基于JDK8源码// 底层存储键值对的数组哈希桶长度始终是2的幂次transientNodeK,V[]table;// 存储所有键值对的集合用于遍历transientSetMap.EntryK,VentrySet;// 键值对的数量transientintsize;// 结构性修改的次数用于快速失败机制transientintmodCount;// 扩容阈值 数组长度 * 负载因子默认16 * 0.75 12intthreshold;// 负载因子默认0.75控制哈希桶的使用率finalfloatloadFactor;// 链表转红黑树的阈值链表长度达到8时触发staticfinalintTREEIFY_THRESHOLD8;// 红黑树转链表的阈值红黑树节点数小于6时触发staticfinalintUNTREEIFY_THRESHOLD6;// 链表转红黑树的最小数组长度数组长度小于64时优先扩容而非转树staticfinalintMIN_TREEIFY_CAPACITY64; 关键总结负载因子0.75是时间和空间的平衡值——值太大哈希冲突增多值太小数组利用率太低。二、哈希冲突成因与解决方案核心考点哈希冲突是HashMap的核心问题也是面试官必问的第一个点。先搞懂“什么是哈希冲突”再看HashMap是怎么解决的。2.1 哈希冲突的成因哈希函数HashMap通过hash(key)方法计算key的哈希值再通过(n-1) hash计算索引n是数组长度冲突本质不同的key经过哈希计算后得到相同的索引就会产生哈希冲突举例key1“abc”和key2“cba”可能计算出相同的索引就会存入同一个哈希桶中源码拆解hash(key)方法JDK8staticfinalinthash(Objectkey){inth;// 1. key为null时哈希值为0所以HashMap的key可以为null// 2. 对key的hashCode进行异或运算右移16位减少哈希碰撞return(keynull)?0:(hkey.hashCode())^(h16);}面试官追问1为什么hash方法要做“h ^ (h 16)”答key的hashCode是32位整数右移16位后高16位和低16位异或能让哈希值的高位也参与索引计算减少因低位重复导致的哈希冲突让索引分布更均匀。2.2 HashMap解决哈希冲突的核心方案链地址法HashMap没有用开放地址法如线性探测而是用链地址法将同一个索引的key-value对以链表或红黑树的形式串联起来。结构示意图索引0索引1索引2索引3哈希桶数组Node1Node2Node3Node4Node5Node6Node7Node8红黑树节点1 小提示JDK7中链表是头插法新节点插入链表头部JDK8改为尾插法新节点插入链表尾部为什么答案在面试官追问环节继续往下看三、扩容机制什么时候扩怎么扩高频追问HashMap的数组长度是固定的初始16当键值对数量达到扩容阈值16*0.7512时就会触发扩容核心目的是减少哈希冲突提升查询效率。3.1 扩容的触发条件满足以下两个条件之一触发扩容键值对数量size≥ 扩容阈值threshold链表长度达到TREEIFY_THRESHOLD8但数组长度MIN_TREEIFY_CAPACITY64此时不转红黑树而是先扩容3.2 扩容的核心流程源码拆解扩容的核心是「创建新数组」「转移旧数组的键值对」关键步骤如下基于JDK8的resize()方法finalNodeK,V[]resize(){NodeK,V[]oldTabtable;// 旧数组长度初始为16intoldCap(oldTabnull)?0:oldTab.length;// 旧扩容阈值初始为12intoldThrthreshold;intnewCap,newThr0;// 1. 计算新数组长度和新扩容阈值if(oldCap0){// 若旧数组长度超过最大值130不再扩容if(oldCapMAXIMUM_CAPACITY){thresholdInteger.MAX_VALUE;returnoldTab;}// 新数组长度 旧数组长度 * 2始终是2的幂次elseif((newCapoldCap1)MAXIMUM_CAPACITYoldCapDEFAULT_INITIAL_CAPACITY)// 新扩容阈值 旧阈值 * 2newThroldThr1;}// 2. 初始化数组第一次put时elseif(oldThr0)newCapoldThr;else{// 默认初始容量16默认阈值16*0.7512newCapDEFAULT_INITIAL_CAPACITY;newThr(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);}// 3. 转移旧数组的键值对到新数组NodeK,V[]newTab(NodeK,V[])newNode[newCap];tablenewTab;if(oldTab!null){for(intj0;joldCap;j){NodeK,Ve;if((eoldTab[j])!null){oldTab[j]null;// 单个节点直接计算新索引并放入新数组if(e.nextnull)newTab[e.hash(newCap-1)]e;// 红黑树节点单独处理拆分红黑树elseif(einstanceofTreeNode)((TreeNodeK,V)e).split(this,newTab,j,oldCap);// 链表节点转移到新数组尾插法else{NodeK,VloHeadnull,loTailnull;NodeK,VhiHeadnull,hiTailnull;NodeK,Vnext;do{nexte.next;// 计算节点在新数组的位置要么在原索引要么在原索引旧数组长度if((e.hasholdCap)0){if(loTailnull)loHeade;elseloTail.nexte;loTaile;}else{if(hiTailnull)hiHeade;elsehiTail.nexte;hiTaile;}}while((enext)!null);// 把两条链表放入新数组对应的索引if(loTail!null){loTail.nextnull;newTab[j]loHead;}if(hiTail!null){hiTail.nextnull;newTab[joldCap]hiHead;}}}}}thresholdnewThr;returnnewTab;}扩容的关键细节新数组长度 旧数组长度 × 2始终保持2的幂次为什么看面试官追问转移链表时JDK8用尾插法避免JDK7头插法在多线程下出现的死循环问题链表转移时会根据e.hash oldCap的结果分成两条链表分别放入新数组的两个索引原索引和原索引旧数组长度面试官追问2HashMap的数组长度为什么必须是2的幂次答核心是为了用(n-1) hash计算索引n是数组长度当n是2的幂次时n-1的二进制全是1能让哈希值的每一位都参与运算索引分布更均匀减少哈希冲突同时扩容时计算新索引更高效无需重新计算hash只需判断高位是否为1。面试官追问3JDK7和JDK8的扩容机制有什么区别答① 链表插入方式JDK7头插法JDK8尾插法② 扩容时索引计算JDK7需重新计算hashJDK8通过e.hash oldCap快速判断新索引③ 多线程问题JDK7扩容可能出现死循环JDK8解决了该问题但仍非线程安全。 互动提示这些面试追问是不是很实用收藏起来面试前快速过一遍避免临场卡壳四、红黑树转换什么时候转为什么转JDK8引入红黑树是为了解决「链表过长导致查询效率下降」的问题——链表查询是O(n)红黑树查询是O(logn)当链表长度达到阈值就会转为红黑树。4.1 红黑树转换的条件源码核心逻辑必须同时满足以下两个条件才会将链表转为红黑树链表长度 ≥ TREEIFY_THRESHOLD8数组长度 ≥ MIN_TREEIFY_CAPACITY64如果链表长度达到8但数组长度64不会转红黑树而是优先扩容因为此时扩容能更高效地减少哈希冲突。源码片段treeifyBin()方法finalvoidtreeifyBin(NodeK,V[]tab,inthash){intn,index;NodeK,Ve;// 数组长度不足64优先扩容if(tabnull||(ntab.length)MIN_TREEIFY_CAPACITY)resize();elseif((etab[index(n-1)hash])!null){// 链表转红黑树的逻辑TreeNodeK,Vhdnull,tlnull;do{TreeNodeK,VpreplacementTreeNode(e,null);if(tlnull)hdp;else{p.prevtl;tl.nextp;}tlp;}while((ee.next)!null);if((tab[index]hd)!null)hd.treeify(tab);}}4.2 红黑树转链表的条件当红黑树的节点数 ≤ UNTREEIFY_THRESHOLD6时会自动转为链表原因是节点数太少时红黑树的维护成本平衡操作高于链表的查询成本转为链表更高效。面试官追问4为什么链表转红黑树的阈值是8转链表是6而不是7答避免频繁转换——如果阈值都是7当链表长度在7左右波动时会频繁在链表和红黑树之间转换增加性能开销8和6之间有一个缓冲区间7减少频繁转换的情况。同时根据泊松分布链表长度达到8的概率极低约0.0000001此时转红黑树性价比最高。4.3 红黑树的核心作用平衡二叉树查询、插入、删除效率稳定在O(logn)避免链表过长如哈希函数设计不合理时导致的查询效率骤降红黑树的平衡规则红节点不相邻、根节点为黑、叶子节点为黑等保证树的高度不会过高五、全文总结HashMap的核心是「数组链表红黑树」的结构围绕“减少哈希冲突、提升效率”展开核心考点总结如下哈希冲突通过hash(key)优化哈希值分布用链地址法解决冲突JDK8用尾插法避免死循环扩容机制数组长度为2的幂次阈值容量×负载因子扩容时转移键值对JDK8优化索引计算红黑树转换链表长度≥8且数组≥64转树节点数≤6转链表平衡查询效率和维护成本面试重点JDK7与JDK8的区别、哈希函数设计、扩容阈值计算、红黑树转换条件