题目标题

hash 冲突及解决办法?

难度:初级

数据分析
参考解析

关键字值不同的元素可能会映象到哈希表的同一地址上就会发生哈希冲突。解
决办法:
1)开放定址法:当冲突发生时,使用某种探查(亦称探测)技术在散列表中形成
一个探查(测)序列。沿此序列逐个单元地查找,直到找到给定 的关键字,或者
碰到一个开放的地址(即该地址单元为空)为止(若要插入,在探查到开放的地
址,则可将待插入的新结点存人该地址单元)。查找时探查到开放的 地址则表
明表中无待查的关键字,即查找失败。
2) 再哈希法:同时构造多个不同的哈希函数。
3)链地址法:将所有哈希地址为 i 的元素构成一个称为同义词链的单链表,并
将单链表的头指针存在哈希表的第 i 个单元中,因而查找、插入和删除主要在
同义词链中进行。链地址法适用于经常进行插入和删除的情况。
4)建立公共溢出区:将哈希表分为基本表和溢出表两部分,凡是和基本表发
生冲突的元素,一律填入溢出表