常见的5种方法:
1.开放定址法
开放定址法就是一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入。
常见的开放寻址技术有线性探测、二次探测和双重散列。
这种方法的缺点是可能导致“聚集”问题,降低哈希表的性能。
2.链地址法
最常用的解决哈希冲突的方法之一每个哈希桶(bucket)指向一个链表。当发生冲突时,新的元素将被添加到这个链表的末尾。在Java中,HashMap就是通过这种方式来解决哈希冲突的。Java8之前,HashMap使用链表来实现;从Java 8开始,当链表长度超过一定阈值时,链表会转换为红黑树,以提高搜索效率。
3.再哈希法
当哈希地址发生冲突用其他的函数计算另一个哈希函数地址,直到冲突不再产生为止。
这种方法需要额外的计算,但可以有效降低冲突率。
4.建立公共溢出区
将哈希表分为基本表和溢出表两部分,发生冲冲突的元素都放入溢出表中。
5.致性hash
主要用于分布式系统中,如分布式缓存。它通过将数据均分布到多个节点上来减少冲突。