141

问答题 141 /290

请你说一下解决hash冲突的方法

参考答案

参考回答:

当哈希表关键字集合很大时,关键字值不同的元素可能会映象到哈希表的同一地址上,这样的现象称为哈希冲突。目前常用的解决哈希冲突的方法如下:

开放定址法: 当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。

再哈希法:当发生哈希冲突时使用另一个哈希函数计算地址值,直到冲突不再发生。这种方法不易产生聚集,但是增加计算时间,同时需要准备许多哈希函数。

链地址法:将所有哈希值相同的Key通过链表存储。key按顺序插入到链表中

建立公共溢出区:采用一个溢出表存储产生冲突的关键字。如果公共溢出区还产生冲突,再采用处理冲突方法处理。