哈希表中元素是由哈希函数确定的。将数据元素的关键字K作为自变量,通过一定的函数关系(称为哈希函数),计算出的值,即为该元素的存储地址。表示为:
Addr = H(key)
为此在建立一个哈希表之前需要解决两个主要问题:
⑴构造一个合适的哈希函数
均匀性 H(key)的值均匀分布在哈希表中;
简单 以提高地址计算的速度
⑵冲突的处理
冲突:在哈希表中,不同的关键字值对应到同一个存储位置的现象。即关键字K1≠K2,但H(K1)= H(K2)。均匀的哈希函数可以减少冲突,但不能避免冲突。发生冲突后,必须解决;也即必须寻找下一个可用地址。
解决冲突的方法: [1]
⑴链接法(拉链法)。将具有同一散列地址的记录存储在一条线性链表中。例,除留余数法中,设关键字为 (18,14,01,68,27,55,79),除数为13。散列地址为 (5,1,1,3,1,3,1)。
⑵开放定址法。
其中,h(k)为哈希函数,TSize为哈希表长,p(i)为探查函数。在 h(k)+p(i-1))%TSize的基础上,若发现冲突,则使用增量 p(i) 进行新的探测,直至无冲突出现为止。其中,根据探查函数p(i)的不同,开放定址法又分为线性探查法(p(i) = i : 1,2,3,…),二次探查法(p(i)=(-1)^(i-1)*((i+1)/2)^2,探查序列依次为:1, -1,4, -4, 9 …),随机探查法(p(i): 随机数),双散列函数法(双散列函数h(key) ,hp (key)若h(key)出现冲突,则再使用hp (key)求取散列地址。探查序列为:h(k),h(k)+ hp(k),…,h(k)+ i*hp(k))。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。