导航:首页 > 使用方法 > 开放寻址法中常用的方法

开放寻址法中常用的方法

发布时间:2024-01-04 20:57:42

‘壹’ 线性探测再散列法是什么

当di值可能为1,2,3,...m-1,称线性探测再散列。

具体如下:

开放地址法有一个公式:Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)。

其中,m为哈希表的表长。di是产生冲突的时候的增量序列。如果di值可能为1,2,3,...m-1,称线性探测再散列。

如果di取1,则每次冲突之后,向后移动1个位置。如果di取值可能为1,-1,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2),称二次探测再散列,如果di取值可能为伪随机数列。称伪随机探测再散列。

处理冲突的方法:

开放寻址法:Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1),其中H(key)为散列函数,m为散列表长,di为增量序列,可有下列三种取法:

1、di=1,2,3,…, m-1,称线性探测再散列;

2、di=1^2, -1^2, 2^2,-2^2, 3^2, …, ±(k)^2,(k<=m/2)称二次探测再散列。

3、di=伪随机数序列,称伪随机探测再散列。

再散列法:Hi=RHi(key), i=1,2,…,k. RHi均是不同的散列函数,即在同义词产生地址冲突时计算另一个散列函数地址,直到冲突不再发生,这种方法不易产生“聚集”,但增加了计算时间。

链地址法(拉链法):将所有关键字为同义词的记录存储在同一线性链表中。

用二次探测再散列法解决冲突:

1、(key+1^2)%11=(49+1)%11=6,仍然发生冲突。

2、(key-1^2)%11=(49-1)%11=4,仍然发生冲突。

3、(key+2^2)%11=(49+4)%11=9,不再发生冲突。

以上内容参考网络-哈希表

与开放寻址法中常用的方法相关的资料

热点内容
列举三种常用的xrd实现方法 浏览:507
心梗干细胞治疗方法 浏览:504
宝宝病毒肠炎治疗方法 浏览:627
硬连和软连接方法 浏览:952
如何保存卵子的方法 浏览:25
肥料酸碱检测方法 浏览:810
平车抬高架安装方法 浏览:560
低谷期的自我解决方法 浏览:308
下跪是解决问题的方法 浏览:171
果树甜蜜素的使用方法 浏览:372
制作饮料最简单的方法不用牛奶 浏览:663
实验研究方法有哪些类型 浏览:334
手机电池耗电快有什么方法解决 浏览:307
物源盆地分析方法 浏览:83
分数比的化简方法图片 浏览:782
哪些方法可以避光烘干蔬菜 浏览:595
文献的方法与技巧 浏览:593
便携式扩音器使用方法 浏览:299
中蜂春繁的问题和解决方法 浏览:620
符咒使用方法 浏览:625