哈希碰撞及解决方式

一、先搞懂什么是哈希冲突咱们先抛开复杂的概念举个生活化的例子假设你有一个书架书架有16个格子对应HashMap的数组每个格子用来放一本书对应HashMap的元素。你给每本书定了一个“摆放规则”对应哈希函数根据书名的拼音首字母计算出它应该放在哪个格子里。结果发现《红楼梦》和《水浒传》经过计算后都应该放在第5个格子里——两个不同的“书”key抢同一个“格子”数组下标这就是哈希冲突。专业定义当两个及以上不同的key经过哈希函数计算后得到相同的数组下标桶位置这种现象就称为哈希冲突哈希碰撞。这里要注意一个关键点哈希冲突是无法完全避免的。因为哈希函数的作用是把无限多的输入任意key映射到有限的输出数组下标就像用16个格子装无数本书必然会有多本书挤一个格子的情况我们能做的只是“减少冲突”和“妥善解决冲突”。二、HashMap 解决哈希冲突的3大核心方案重中之重HashMap作为Java中最常用的集合类之一针对哈希冲突做了非常完善的优化核心就是3种方式拉链法主方案 扰动函数减少冲突 扩容机制分散冲突三者配合让HashMap的性能达到最优。1. 拉链法数组 链表 / 红黑树这是HashMap默认且最主要的解决哈希冲突的方式核心思路很简单既然一个数组下标桶放不下多个冲突的元素那就给这个桶“挂个尾巴”——让冲突的元素按顺序挂载在这个桶的后面形成一个链表当链表太长时再转为红黑树提升查询效率。具体实现JDK1.8版本重点优化HashMap的底层结构是「数组 链表 红黑树」数组是核心骨架每个元素都是一个“桶”当发生哈希冲突时新的元素不会覆盖原来的元素而是被添加到该桶对应的链表末尾当链表的长度≥8时会自动转为红黑树红黑树的查询时间复杂度是O(logn)而链表是O(n)差距很大当红黑树的节点数≤6时会退化为链表为什么不是7因为7是中间值防止链表和红黑树频繁转换避免性能损耗。优点也很明显实现简单就算冲突再多也能正常存储元素而且通过红黑树的优化查询和插入效率都能得到保障。2. 扰动函数减少哈希冲突的“小技巧”如果哈希函数计算出来的哈希值分布不均匀就会导致大量key集中在少数几个桶里冲突加剧。所以HashMap会对key的hashCode做一次“二次扰动”让哈希值分布更均匀从而减少冲突的概率。JDK1.8中的扰动函数代码hash key.hashCode() ^ (key.hashCode() 16);核心作用把key的hashCode的高16位和低16位进行异或运算让高16位的特征也参与到哈希值的计算中避免因为哈希值的低位重复导致大量冲突。这里要注意扰动函数是“减少冲突”而不是“解决冲突”——它只能降低冲突的概率不能完全避免冲突。3. 扩容机制自动分散冲突优化性能当HashMap中的元素越来越多数组的负载因子元素个数/数组长度超过默认的0.75时就会触发自动扩容——数组长度翻倍必须是2的幂这是HashMap的核心设计之一然后重新计算所有元素的哈希值和下标把原来冲突的元素分散到新的桶中从而减少冲突。这里补充一个和之前相关的知识点——扩容时的红黑树拆分也就是之前聊到的low树和high树当扩容时原来桶中的红黑树或链表会被拆分成两个子树low树用「元素hash 旧数组长度」判断结果为0的元素留在原来的下标位置high树判断结果不为0的元素放到「原下标 旧数组长度」的新位置。这样拆分的目的是让原来冲突的元素自动分散到新的不同桶中进一步减少冲突保证HashMap的性能。三、除了拉链法还有哪些解决哈希冲突的方式除了HashMap用的拉链法还有3种常见方式1. 开放地址法ThreadLocalMap在用核心思路当发生冲突时不挂链表而是在数组中往后找一个空的位置把元素放进去。常见的有3种探测方式线性探测依次往后找、二次探测往后找平方距离的位置、伪随机探测随机找空位置。缺点容易出现“聚集效应”多个冲突元素挤在一起影响查询效率。2. 再哈希法核心思路当一个哈希函数计算出冲突的下标时换一个哈希函数重新计算直到找到不冲突的下标。缺点增加了哈希计算的次数性能有损耗。3. 建立公共溢出区核心思路单独开辟一个“溢出数组”所有发生冲突的元素不管原来的下标是什么都统一放到这个溢出数组中原数组只存没有冲突的元素。缺点当冲突元素较多时溢出数组的查询效率会很低。