一般情况下，建立散列表时难以避免出现散列冲突，常用处理散列冲

[问答题]

一般情况下，建立散列表时难以避免出现散列冲突，常用处理散列冲突的方法之一是开放定址法，该方法的基本思想是什么？

对象不存在的怨念同学

PS: 我看的书上好像写的是线性探测法，不过意思没太大差别

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

H_i= (H(key) + d_i) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)为散列函数，m为散列表长，d_i为增量序列。d_i可有下列三种取法：

（1）d_i=1,2,3,…, m-1，称为线性探测再散列；

（2）d_i=1^2, -(1^2), 2^2, -(2^2), 3^2, …, ±(k^2),(k<=m/2)，称二为次探测再散列；

（3）d_i=伪随机数序列，称为伪随机探测再散列。

所谓伪随机数，用同样的随机种子，将得到相同的数列。

发表于 2017-12-03 22:54:12 回复(0)

牛客4414733号

把可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放

发表于 2017-12-03 20:37:58 回复(0)

提交观点

问题信息

哈希

上传者：城市里的养猫者

难度：

2条回答 3收藏 2131浏览

扫一扫，把题目装进口袋