解决哈希冲突的常用方法有哪些?

开放定址法

基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈 希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不 冲突的哈希地址pi ,将相应元素存入其中。

再哈希法

这种方法是同时构造多个不同的哈希函数:Hi=RH1(key) i=1,2,…,k 当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。

链地址法

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

拉链法的优点:

拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短; 由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况; 在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

拉链法的缺点:

指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。

看图就可以知道Java中的hashMap使用了拉链法处理冲突。 HashMap有一个初始容量大小,默认是16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 为了减少冲突的概率,当hashMap的数组长度到了一个临界值就会触发扩容,把所有元素rehash再放到扩容后的容器中,这是一个非常耗时的操作。

而这个临界值由【加载因子】和当前容器的容量大小来确定:DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR ,即默认情况下是16x0.75=12时,就会触发扩容操作。

所以使用hash容器时尽量预估自己的数据量来设置初始值。具体代码实现自行去研究HashMap的源码。

基础知识补充完毕,回到正题,为什么加载因子要默认是0.75?

使用随机哈希码,节点出现的频率在hash桶中遵循泊松分布,同时给出了桶中元素个数和概率的对照表。从上面的表中可以看到当桶中元素到达8个的时候,概率已经变得非常小,也就是说用0.75作为加载因子,每个碰撞位置的链表长度超过8个是几乎不可能的。

建立公共溢出区

这种方法的基本思想是:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券