关于散列冲突和开放寻找法

今天被问到有个问题,是关于HashMap冲突时解决思路的。如果hash code设计不好,散列碰撞严重,所有的元素挤在了相同散列的桶中,而桶是链表结构,会导致HashMap O(1)的获取效率向O(n)退化。

一种解决思路是,桶大小为1,如果发现散列冲突,则可以通过线性探查,二次探查或双散列等方式,继续查找空槽直到找到满足条件的空槽存放对象。就是常说的“开放寻址法”。

仔细想想,线性查找是将原先槽对应的桶链表在槽中展开。如果槽是X维度,桶链表是Y维度,线性查找实际做了一次Y -> X的映射——存储结构降维了。这样的操作其实存在很大的潜在风险,因为X原先已经有元素,而且之后可能不断添加。随着元素增加,其实并没有减少冲突,反而在加剧冲突。而且维度的混乱让散列越发难以管理,比如做删除,原先只要察觉槽中有桶就能检测,现在要遍历,遍历收敛的条件也很难判断,搞得不巧一次删除就是一次O(n)的操作。实在让人不喜。二次探查和双散列还好一些,本质都是都是利用附加属性对桶中相似对象进行进一步区分。但实际上也增加了算法复杂度,让程序难以维护。

个人感觉解决散列冲突的根源不在于冲突后的应对算法,还是在于避免冲突,回到问题的本源。散列算法基本是从大的定义域向小的值域映射的函数,本身具有可以重复且不可逆两个特征。不可逆意味着映射过程中信息是有减损的。可重复意味着,相同的特征集合,得到的函数结果是相同的。如果目标为了提高效率,避免散列冲突,则最好的解决方案,还是减小散列函数定义域和值域的差距,使得即使散列后虽然信息损减,但是依然保持可以互相区分。就像二次探查和双散列,其实就在利用附加属性增大散列函数的值域,加大区分,减小冲突可能性。

那么,在实际落地实施的时候,还是不要吝啬参与hash code运算的对象特性值。特征值本质是甄别对象间异同的要素集合,从业务设计上,就应该将有实际意义的特征加入散列值计算中,使得对象的hash code从原理上获得高区分度。

当然,这么说可能有重业务轻技术的嫌疑。不过原则上所有的技术都应该在原理和设计规划上合理。而且我个人一直主张不要企图用技术手段来掩盖或解决设计问题。记得某公司积累了100T的Oracle单库一直没拆分。直到某天实在抗不住了,花大价钱轻高人来了次惊心动魄的线上拆库。这类现象就是典型的利用下游技术手段掩盖消灭设计问题。10T不拆,50T不拆,应用都靠数据库抗着,直到实在扛不住了才拆。如果不是高手们胆大心细,万一拆不出来或拆坏了怎么办?回到Hash code的问题,还是务必在设计建模时,确认对象的哪些要素时可以用来区分彼此的,建立在数理模型上可靠性一般都会比利用算法获得的可靠性高,这也体现了一条重要的编程原则——软件中数据结构的重要性高于算法。

只有面对实际问题甄别出对象特征,才可能在数理空间获得高区分度。而只有在数理空间获取高区分度,才可能在散列降维后保持高区分度。目前这是我能够想到的散列防冲突的因果链条。