从一个经典的面试问题开始“你讲一下HashMap的put过程和get过程。”别急着背八股文。背诵源码只是表象如果你真的把jdk1.7与1.8的底层实现差异带着“设计动机”去理解那么面试官在你面前就是个同学。而且不夸张地说HashMap的源码原理贯穿了hash算法、位运算、红黑树、并发问题以及Java集合框架的设计哲学。绝大多数人在讲HashMap的时候只会说“数组链表红黑树”但追问下去比如“为什么树化阈值是8”“扩容为什么是2倍”“1.7头插法和1.8尾插法有什么区别”立刻就会卡壳。我今天带你串联一遍HashMap以jdk1.8为主对比1.7的差异的核心源码同时标记出面试官最爱挖坑的地方。你读完这篇文章至少能给自己打出7分的自信剩下的3分靠手势和眼神。一、前置知识一个“桶”和它的灵魂三问先从内存结构说起。HashMap底层是一个NodeK,V[] table数组这个数组的每个元素叫“桶”bucket。桶里存什么如果只有一个元素直接存Node如果发生哈希冲突这里会形成链表当链表长度超过阈值默认8链表会转为红黑树。面试官此刻百分之百会问“为什么不直接用数组存全部数据为什么要用链表处理冲突”原因在于如果直接用大数组那么key的哈希值范围是-21亿到21亿你不可能为了放一个元素分配长度为42亿的数组。因此HashMap需要对hash值再做一次取模运算让所有key落在一个有限大小的数组里。取模的结果相同就说明发生碰撞此时用链表或树来存储同一数组下标下的多个元素。这就引出了第一个核心金句HashMap的设计本质就是用空间换时间并且用有限的数组下标去包容无限的Key空间。二、hash函数1.7和1.8的区别究竟在哪里“说说HashMap的hash函数。”这个问题如果你只答一个“扰动函数”那只有20分。要拿到高分你需要对比jdk1.7和1.8的hash实现差别并解释为什么这么改。在jdk1.7中hash函数长这样static int hash(int h) { h ^ (h 20) ^ (h 12); return h ^ (h 7) ^ (h 4); }而在1.8中变成了static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }看出来了吗1.8的代码量大大减少了。它只做了一次异或运算高16位与低16位异或。做得少了效果反而差了吗不这正是“大道至简”。因为1.8引入了红黑树对哈希冲突的容忍度大幅提升不再需要用复杂的四次扰动去尽量降低碰撞概率。而为什么要让高16位参与运算因为数组取模只用了低位导致高位信息丢失。通过h 16把高位“拉下来”与低位异或从而让高位信息也参与决定数组下标。这是位运算在提高哈希散列均匀性上的经典体现。非常值得加粗HashMap的hash函数核心目标是让高位信息尽量参与低位索引计算从而降低碰撞概率。三、put方法的“身世之谜”从索引计算到树化你敲下的map.put(key, value)到底经历了什么第一步计算哈希定位桶下标。int hash hash(key); int i (n - 1) hash;注意这里的(n - 1) hash——它是取模运算的高性能等价形式但前提是数组长度n必须是2的整数次幂。为什么因为当n2^k时n-1的二进制全是低位1与hash进行与运算相当于截取出hash的低k位。这就是为什么HashMap的初始容量是16扩容成32、64……始终是2的幂。第二步判断桶内状态。如果桶是null直接newNode放入。如果桶非空则比较链表的第一个节点即桶中唯一的元素或红黑树的根节点看是否可以直接覆盖。如果结构是红黑树调用putTreeVal。如果是链表遍历链表如果找到了相同key则覆盖value如果没找到则在链表尾部插入。注意1.8是尾插法而1.7是头插法。面试官会追问这个变化的原因答案主要是解决1.7扩容时的循环依赖问题。第三步检查是否需要树化。if (binCount TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash);这里TREEIFY_THRESHOLD 8。面试官会接着问“阈值为什么是8”这个问题的标准答案要结合概率论。源码注释显示理想情况下随机哈希码导致链表长度分布服从泊松分布。长度为8的概率只有0.00000006几乎不会发生。因此设置为8是时间与空间的一个平衡点——如果树化阈值设置得太小树化频繁红黑树查找O(log n)的优势没有完全发挥反而增加了旋转成本如果太大链表的O(n)查找会恶化。一句话8这个阈值是理论与实践结合的最优点既规避了偶发的哈希碰撞恶化危机又不至于过度早地触发树化导致空间和时间的双重浪费。四、resize扩容为什么HashMap的扩容操作会“害人”任何面试问到HashMap扩容机制是必考项。当你发现size threshold时threshold capacity loadFactor默认0.75会调用resize()。扩容分为两步新数组长度翻倍旧数据rehash到新数组。为什么容量是2倍源于(n - 1) hash公式的约束如果n是2的幂那么n-1高位是连续的1rehash时每个元素要么停留在原索引要么移动到“原索引旧数组长度”的位置不需要再重新计算hash。这大幅提高了扩容的效率。源码中用一条非常精巧的位运算实现了这个判断if ((e.hash oldCap) 0)则位置不变否则新位置 index oldCap。你看这里没判断 1而是判断 0因为oldCap是2的幂形如1000...0与hash做与运算只关注被oldCap遮盖的那一位是0还是1。1.8中resize对数据的迁移采用了尾插法有效避免了1.7中多线程扩容带来的死循环问题。来把这句话圈起来jdk1.7的头插法在多线程并发扩容时会导致环形链表造成get操作死循环这是HashMap被诟病为“线程不安全”的最直接体现。1.8改用尾插法后该问题从根本上被解决但HashMap依然线程不安全因为put和get之间没有同步机制会出现数据覆盖。五、红黑树代码量最大但面试只要讲透这四点红黑树的源码占了HashMap将近一半的篇幅但面试不需要你背几十行左旋右旋代码。你需要讲清楚以下四点为什么用红黑树而不是二叉平衡树红黑树的旋转次数较少对于插入频繁的场景性能优于严格平衡的AVL树。树化的目的只是把查找时间从链表的O(n)优化到O(log n)不需要完美平衡而牺牲插入效率。劣化条件如果扩容后树的节点数小于UNTREEIFY_THRESHOLD6树会退化为链表。避免树结构维持过大、浪费内存。compare(key, key) 的影响当两个key的hash相同且key不可比较即未实现Comparable接口或比较结果也为0时HashMap会通过System.identityHashCode来最终判断。这是为了在红黑树中给不同key一个确定的比较顺序保证树的正常运作。一个反常识的坑不是说链表长度达到8就一定会树化。treeifyBin里还有一个条件if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY64如果数组长度小于64,不会树化而是先扩容resize。原因很简单当哈希冲突导致某桶链表很长时往往意味着哈希函数本身的散列效果已经不好数组太小了。此时优先通过扩容来重新散列数据让元素分布更均匀而不是直接启用相对复杂的红黑树。六、Fail-Fast机制ConcurrentModificationException的起源当你在遍历HashMap的同时另外的线程或同一线程在迭代过程中调用map.put/remove修改了map的结构增加或删除元素会抛出ConcurrentModificationException。这是通过记录modCount修改次数实现的。必须指出的是这种快速失败是尽力而为的检测行为不能依赖它来保证程序的正确性。面试官会追问“如果单线程中在迭代过程中用iterator.remove()删除元素会抛异常吗”答案是不会。因为Iterator的remove方法会同步更新modCount和expectedModCount。而直接用map.remove则不会。这是面试中的一个核心陷阱不要以为Fail-Fast机制可以替代多线程并发安全的设计。七、面试中必须会答的三个“为什么”1. 为什么负载因子默认0.75简单回答是“时间和空间的权衡”。深入回答可以是太小的负载因子比如0.5导致数组利用率低虽然碰撞少但浪费内存。太大的负载因子比如1.0导致数组可能全满了才扩容但此时桶内链表长度已经很长查找效率急剧下降。0.75是从数学统计和大量实验中得出的最优值符合泊松分布模型下性能与容量的平衡点。2. HashMap和HashTable的区别这个题有基础版和高级版。基础版HashTable加了synchronized线程安全但性能差不允许null。同时HashTable的初始容量是11扩容是2倍1而其hash函数是直接使用key的hashCode不进行扰动。3. 如何让自定义类正确作为HashMap的Key必须重写equals()和hashCode()且保证两个方法的一致性equals为true时hashCode必须相同反之不必。另外尽量不要让Key对象的hash值在执行put之后发生改变比如用final或不可变对象像String、Integer。否则你将无法从HashMap中通过get查找该键因为它的桶已经发生了变化。可以抛出这样一个金句一个不遵守hashCode协议的自定义对象等于亲手掩埋了在HashMap中定位它的所有路径。八、从源码到生产你真的会用HashMap吗面试再深入一步会结合多线程场景考察你“为什么HashMap线程不安全并发put会造成什么后果”数据覆盖jdk1.8的put方法中当两个线程同时判断桶为null都会执行tab[i] newNode(…)后写入的会覆盖先写入的导致数据丢失。size计数丢失HashMap中有size操作它不是原子操作并发下会导致size计数不准比如两次put结果size只增加了1。jdk1.7的死循环前面提过1.7的头插法在扩容时多线程操作会导致环形链表。生产环境的黄金法则需要线程安全时用ConcurrentHashMap单线程里请把HashMap设置为final成员变量同时在整个生命周期里谨慎对待rehash带来的性能抖动——初始化时如果已知数据量最好指定合适的初始化容量减少扩容次数。计算公式capacity (int) (expectedSize / loadFactor) 1。九、从面试回答看你对HashMap的理解深度我想强调一个观点面试官不是在背诵重述机他是在通过HashMap这个“经典题目”来看你是不是一个会深入思考的工程师。如果你能讲清楚哈希函数的位运算设计动机能辨析1.7和1.8树化、插入次序、扩容迁移的具体差异能理解泊松分布与树化阈值8的关系还能扛得住关于并发场景下的挖坑问题——那这场面试已经稳了大半。最后送上一段源码里最值得你反复阅读的注释我把它的内在含义翻译成一句话HashMap是一个极致追求性能、同时保有优雅设计、又处处透露着妥协的艺术品。读懂它你不仅懂了一个容器更懂了程序设计中时间、空间与复杂性的三角博弈。把这篇文字消化掉下一场面试碰到HashMap你不只是能答你还能成为主导对话的人。
从一个经典的面试问题开始“你讲一下HashMap的put过程和get过程。”别急着背八股文。背诵源码只是表象如果你真的把jdk1.7与1.8的底层实现差异带着“设计动机”去理解那么面试官在你面前就是个同学。而且不夸张地说HashMap的源码原理贯穿了hash算法、位运算、红黑树、并发问题以及Java集合框架的设计哲学。绝大多数人在讲HashMap的时候只会说“数组链表红黑树”但追问下去比如“为什么树化阈值是8”“扩容为什么是2倍”“1.7头插法和1.8尾插法有什么区别”立刻就会卡壳。我今天带你串联一遍HashMap以jdk1.8为主对比1.7的差异的核心源码同时标记出面试官最爱挖坑的地方。你读完这篇文章至少能给自己打出7分的自信剩下的3分靠手势和眼神。一、前置知识一个“桶”和它的灵魂三问先从内存结构说起。HashMap底层是一个NodeK,V[] table数组这个数组的每个元素叫“桶”bucket。桶里存什么如果只有一个元素直接存Node如果发生哈希冲突这里会形成链表当链表长度超过阈值默认8链表会转为红黑树。面试官此刻百分之百会问“为什么不直接用数组存全部数据为什么要用链表处理冲突”原因在于如果直接用大数组那么key的哈希值范围是-21亿到21亿你不可能为了放一个元素分配长度为42亿的数组。因此HashMap需要对hash值再做一次取模运算让所有key落在一个有限大小的数组里。取模的结果相同就说明发生碰撞此时用链表或树来存储同一数组下标下的多个元素。这就引出了第一个核心金句HashMap的设计本质就是用空间换时间并且用有限的数组下标去包容无限的Key空间。二、hash函数1.7和1.8的区别究竟在哪里“说说HashMap的hash函数。”这个问题如果你只答一个“扰动函数”那只有20分。要拿到高分你需要对比jdk1.7和1.8的hash实现差别并解释为什么这么改。在jdk1.7中hash函数长这样static int hash(int h) { h ^ (h 20) ^ (h 12); return h ^ (h 7) ^ (h 4); }而在1.8中变成了static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }看出来了吗1.8的代码量大大减少了。它只做了一次异或运算高16位与低16位异或。做得少了效果反而差了吗不这正是“大道至简”。因为1.8引入了红黑树对哈希冲突的容忍度大幅提升不再需要用复杂的四次扰动去尽量降低碰撞概率。而为什么要让高16位参与运算因为数组取模只用了低位导致高位信息丢失。通过h 16把高位“拉下来”与低位异或从而让高位信息也参与决定数组下标。这是位运算在提高哈希散列均匀性上的经典体现。非常值得加粗HashMap的hash函数核心目标是让高位信息尽量参与低位索引计算从而降低碰撞概率。三、put方法的“身世之谜”从索引计算到树化你敲下的map.put(key, value)到底经历了什么第一步计算哈希定位桶下标。int hash hash(key); int i (n - 1) hash;注意这里的(n - 1) hash——它是取模运算的高性能等价形式但前提是数组长度n必须是2的整数次幂。为什么因为当n2^k时n-1的二进制全是低位1与hash进行与运算相当于截取出hash的低k位。这就是为什么HashMap的初始容量是16扩容成32、64……始终是2的幂。第二步判断桶内状态。如果桶是null直接newNode放入。如果桶非空则比较链表的第一个节点即桶中唯一的元素或红黑树的根节点看是否可以直接覆盖。如果结构是红黑树调用putTreeVal。如果是链表遍历链表如果找到了相同key则覆盖value如果没找到则在链表尾部插入。注意1.8是尾插法而1.7是头插法。面试官会追问这个变化的原因答案主要是解决1.7扩容时的循环依赖问题。第三步检查是否需要树化。if (binCount TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash);这里TREEIFY_THRESHOLD 8。面试官会接着问“阈值为什么是8”这个问题的标准答案要结合概率论。源码注释显示理想情况下随机哈希码导致链表长度分布服从泊松分布。长度为8的概率只有0.00000006几乎不会发生。因此设置为8是时间与空间的一个平衡点——如果树化阈值设置得太小树化频繁红黑树查找O(log n)的优势没有完全发挥反而增加了旋转成本如果太大链表的O(n)查找会恶化。一句话8这个阈值是理论与实践结合的最优点既规避了偶发的哈希碰撞恶化危机又不至于过度早地触发树化导致空间和时间的双重浪费。四、resize扩容为什么HashMap的扩容操作会“害人”任何面试问到HashMap扩容机制是必考项。当你发现size threshold时threshold capacity loadFactor默认0.75会调用resize()。扩容分为两步新数组长度翻倍旧数据rehash到新数组。为什么容量是2倍源于(n - 1) hash公式的约束如果n是2的幂那么n-1高位是连续的1rehash时每个元素要么停留在原索引要么移动到“原索引旧数组长度”的位置不需要再重新计算hash。这大幅提高了扩容的效率。源码中用一条非常精巧的位运算实现了这个判断if ((e.hash oldCap) 0)则位置不变否则新位置 index oldCap。你看这里没判断 1而是判断 0因为oldCap是2的幂形如1000...0与hash做与运算只关注被oldCap遮盖的那一位是0还是1。1.8中resize对数据的迁移采用了尾插法有效避免了1.7中多线程扩容带来的死循环问题。来把这句话圈起来jdk1.7的头插法在多线程并发扩容时会导致环形链表造成get操作死循环这是HashMap被诟病为“线程不安全”的最直接体现。1.8改用尾插法后该问题从根本上被解决但HashMap依然线程不安全因为put和get之间没有同步机制会出现数据覆盖。五、红黑树代码量最大但面试只要讲透这四点红黑树的源码占了HashMap将近一半的篇幅但面试不需要你背几十行左旋右旋代码。你需要讲清楚以下四点为什么用红黑树而不是二叉平衡树红黑树的旋转次数较少对于插入频繁的场景性能优于严格平衡的AVL树。树化的目的只是把查找时间从链表的O(n)优化到O(log n)不需要完美平衡而牺牲插入效率。劣化条件如果扩容后树的节点数小于UNTREEIFY_THRESHOLD6树会退化为链表。避免树结构维持过大、浪费内存。compare(key, key) 的影响当两个key的hash相同且key不可比较即未实现Comparable接口或比较结果也为0时HashMap会通过System.identityHashCode来最终判断。这是为了在红黑树中给不同key一个确定的比较顺序保证树的正常运作。一个反常识的坑不是说链表长度达到8就一定会树化。treeifyBin里还有一个条件if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY64如果数组长度小于64,不会树化而是先扩容resize。原因很简单当哈希冲突导致某桶链表很长时往往意味着哈希函数本身的散列效果已经不好数组太小了。此时优先通过扩容来重新散列数据让元素分布更均匀而不是直接启用相对复杂的红黑树。六、Fail-Fast机制ConcurrentModificationException的起源当你在遍历HashMap的同时另外的线程或同一线程在迭代过程中调用map.put/remove修改了map的结构增加或删除元素会抛出ConcurrentModificationException。这是通过记录modCount修改次数实现的。必须指出的是这种快速失败是尽力而为的检测行为不能依赖它来保证程序的正确性。面试官会追问“如果单线程中在迭代过程中用iterator.remove()删除元素会抛异常吗”答案是不会。因为Iterator的remove方法会同步更新modCount和expectedModCount。而直接用map.remove则不会。这是面试中的一个核心陷阱不要以为Fail-Fast机制可以替代多线程并发安全的设计。七、面试中必须会答的三个“为什么”1. 为什么负载因子默认0.75简单回答是“时间和空间的权衡”。深入回答可以是太小的负载因子比如0.5导致数组利用率低虽然碰撞少但浪费内存。太大的负载因子比如1.0导致数组可能全满了才扩容但此时桶内链表长度已经很长查找效率急剧下降。0.75是从数学统计和大量实验中得出的最优值符合泊松分布模型下性能与容量的平衡点。2. HashMap和HashTable的区别这个题有基础版和高级版。基础版HashTable加了synchronized线程安全但性能差不允许null。同时HashTable的初始容量是11扩容是2倍1而其hash函数是直接使用key的hashCode不进行扰动。3. 如何让自定义类正确作为HashMap的Key必须重写equals()和hashCode()且保证两个方法的一致性equals为true时hashCode必须相同反之不必。另外尽量不要让Key对象的hash值在执行put之后发生改变比如用final或不可变对象像String、Integer。否则你将无法从HashMap中通过get查找该键因为它的桶已经发生了变化。可以抛出这样一个金句一个不遵守hashCode协议的自定义对象等于亲手掩埋了在HashMap中定位它的所有路径。八、从源码到生产你真的会用HashMap吗面试再深入一步会结合多线程场景考察你“为什么HashMap线程不安全并发put会造成什么后果”数据覆盖jdk1.8的put方法中当两个线程同时判断桶为null都会执行tab[i] newNode(…)后写入的会覆盖先写入的导致数据丢失。size计数丢失HashMap中有size操作它不是原子操作并发下会导致size计数不准比如两次put结果size只增加了1。jdk1.7的死循环前面提过1.7的头插法在扩容时多线程操作会导致环形链表。生产环境的黄金法则需要线程安全时用ConcurrentHashMap单线程里请把HashMap设置为final成员变量同时在整个生命周期里谨慎对待rehash带来的性能抖动——初始化时如果已知数据量最好指定合适的初始化容量减少扩容次数。计算公式capacity (int) (expectedSize / loadFactor) 1。九、从面试回答看你对HashMap的理解深度我想强调一个观点面试官不是在背诵重述机他是在通过HashMap这个“经典题目”来看你是不是一个会深入思考的工程师。如果你能讲清楚哈希函数的位运算设计动机能辨析1.7和1.8树化、插入次序、扩容迁移的具体差异能理解泊松分布与树化阈值8的关系还能扛得住关于并发场景下的挖坑问题——那这场面试已经稳了大半。最后送上一段源码里最值得你反复阅读的注释我把它的内在含义翻译成一句话HashMap是一个极致追求性能、同时保有优雅设计、又处处透露着妥协的艺术品。读懂它你不仅懂了一个容器更懂了程序设计中时间、空间与复杂性的三角博弈。把这篇文字消化掉下一场面试碰到HashMap你不只是能答你还能成为主导对话的人。
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
