小强整了整衬衫领子屏幕上的面试官表情像刚吃了一碗没放盐的面条。“先简单介绍下你自己。”小强挺直腰板“三年Java开发主力业务系统常用集合框架很熟HashMap源码也看过。”面试官眼皮都没抬“那说说HashMap底层数据结构。”小强心里一乐。这题他背过。“数组加链表JDK 8还引入了红黑树。哈希冲突的时候用链表挂着链表太长就转成红黑树提升查询效率。”“还行。”面试官顿了顿“什么时候链表转红黑树”“链表长度超过8同时数组长度大于等于64。只超8但数组小优先扩容。”“为什么阈值是8”小强一愣。他背过这个数字但没想过为什么。“呃……应该是经过测试平衡空间和时间的折中值”“你这个理解停留在表面。”面试官推了下眼镜“还有吗”小强手心开始冒汗。他快速回忆博客内容什么也捞不出来。“没……没有了。”“那换个角度。HashMap怎么计算key存在哪个位置”这个他又熟了语气轻快起来“key的hashCode高16位和低16位做异或然后和数组长度减一做与运算。”“为什么高16位要参与异或”“为了……让哈希更散列”“散列什么高16位参与的目的是什么不这样做会有什么问题”小强脑子嗡了一下。他看过这段源码final int hash那个方法注释里写了但他没细看。“减少哈希碰撞……”“太笼统了。还有吗”小强沉默了十秒摇了摇头。“那就问个简单的。”面试官端起茶杯抿了一口“HashMap扩容机制说说看。”“扩容就是把数组扩大两倍然后把旧数据重新哈希过去。”“这个过程是线程安全的吗”“不是HashMap本身线程不安全。”“如果在并发场景下用HashMap会怎样”“可能会数据覆盖……还有死循环。”小强回答得有些犹豫。“死循环是怎么产生的”“在JDK 7里扩容的时候链表会反转多线程同时扩容可能导致环形链表。”小强总算想起一篇面经里的答案。“JDK 8解决了吗”“JDK 8不会出现死循环了但依然有数据覆盖问题。”“为什么JDK 7会有死循环”这个问题像块砖头砸在脸上。“扩容的时候用头插法……”小强支支吾吾“转移链表元素的时候指针乱掉了。”“具体怎么乱掉的描述一下过程。”小强张了张嘴。脑子里的知识调不出来只剩下满屏的报错画面。他把面经所有能抖的都抖完了面试官还在问。“有没有想过为什么JDK 8改成尾插法就不死循环了但对于丢失数据还是无能为力”“这个……没有细想过。”“HashMap的负载因子默认多少”“0.75。”“为什么是0.75不是0.5或者1”房间里安静得能听见CPU风扇转。“不知道……”面试官放下笔抬头看着小强没有任何表情。“行情况我了解了。你先回去等通知吧。”视频挂断。屏幕上倒映出小强呆滞的脸。他愣在那儿半晌没动。三年代码经验HashMap用过上万次被问到怀疑人生。电脑合上他抓起烟盒下了楼。园区长椅上老汪正叼着烟看手机。花白头发被风吹得乱糟糟的保温杯搁在扶手上冒着热气。“怎么了跟丢了魂似的。”小强一屁股坐下把刚才的面试倒了个干净。老汪听完拧开保温杯喝了口茶慢悠悠开口“HashMap这玩意儿说白了就是个大型食堂的取餐窗口。”“食堂”“你想想。”他把烟掐灭从兜里掏出支笔在烟盒背面画起来。“食堂有16个取餐窗口每个窗口排一队人。你拿到餐号怎么知道去哪个窗口”“餐号对窗口数取模……Hash。”“对。但餐号是连续的数字实际key的hashCode可不连续。”老汪画了个方框“如果hashCode的低位规律很明显比如都是偶数那你下标永远落在偶数窗口奇数窗口全空着。”他抬眼“高16位参与异或是让高位特征混进低位。不然数组长度小的时候高位特征根本参与不了运算浪费了。说白了就是把一粒盐撒进水里搅匀别让盐全沉在一个角落。”小强猛点头“那链表过长转红黑树呢”“16个窗口某个窗口排了十几个人。你是一路找过去还是挨个问”老汪在纸上写上TREEIFY_THRESHOLD 8“超过8个人不排队了你站中间比前面的人编号大往右走小就往左走——红黑树。至于为什么是8跟概率有关。”他在纸上写泊松分布λ0.5。“正常哈希分布下链表长度达到8的概率是0.00000006。再长就不是运气问题了是你的哈希算法本身有问题或者有人故意造哈希碰撞攻击你。所以树化是个保险机制不是常规路径。”小强掏出手机记笔记手指都在抖。“面试官追着我问死循环是怎么产生的我答不上来。”老汪啧了一声在纸上画了两个小人。“JDK 7扩容用头插法。线程A和线程B同时扩容线程A拿到指针A→B→null刚把A搬到新数组CPU时间片用完了。线程B完整执行完链表变成B→A→null。线程A回来继续它手里还拿着旧的A→B的引用。”笔尖停在纸上。“A插入新数组然后遍历下一个元素B。但B的next已经被线程B改成指向A了。A再把B用头插法放进去B的next指向A。A再找B的next——又指向A。死循环了。”他在纸上画了个圈A→B→A→B。“CPU直接飙到100%。当年我们生产环境排查了一整夜最后jstack一把线程全卡在HashMap.transfer这个方法上。我到现在还记得那个凌晨四点的机房。”“JDK 8怎么就没事了”“JDK 8用尾插法转移链表的时候顺序不变。但它只能保证不会死循环保证不了数据正确性。”老汪在圈上打了个叉“两个线程同时put完全可能A的值被B覆盖。所以面试官才问你对数据丢失的理解——他知道你看过源码但要看你是不是真思考过。”小强低声说“我以为HashMap底层已经挺熟了。”“会用和会修是两码事。”老汪合上笔帽“面试官问HashMap前半段考基础知识到了追问阶段他在拆四个层次——数据结构选型为什么这样设计哈希函数为什么要扰动扩容为什么是两倍并发场景下到底哪里不安全。他不是问你背的API他想看你的排错能力和设计思维。”老汪敲了敲烟盒“回去做三件事。第一源码里HashMap开头的注释有一大段设计决策的说明逐行读三遍。第二用两个线程模拟扩容跑一次jstack抓线程栈下来看。第三翻开《Java并发编程实战》第五章读完写篇博客手画内存图别复制粘贴网上的。”小强捏着写了笔记的手机沉默了一会儿。“汪哥我觉得我三年白干了。”“不叫白干。”老汪拧开保温杯热气腾起来“摔一跤才知道坑有多深。知道坑有多深填坑的时候才知道铲子往哪挖。”长椅旁边梧桐树的影子斜过来老汪站起来拍拍裤子。“走了。我那还有一堆慢SQL要收拾。”小强望着老汪拎着保温杯走远的背影低头看了眼烟盒上画的圆圈和箭头。A→B→A→B。他好像突然看得懂了。