哈希表解决冲突的4种方法

yPhantom 2019年10月15日 31次浏览

hash算法解决冲突的一般解决办法:

1.开放地址法

所谓的开放定址法就是一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入。

缺点:容易产生堆聚现象,即存入哈希表的记录在表中连成一片。

2.拉链法(链地址法)

每个哈希表节点有一个next指针,同一hash值的节点可以用next指针构成一个单向链表。

3.再哈希法

又叫双哈希法,即存在多个不同的hash函数,当发生冲突时,使用第二个,第三个,...。计算地址,直到无冲突。虽然不易发生堆聚,但是增加了计算时间。

4.建立公共溢出区

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