Hash冲突的线性探测开放地址法
在实际应用中,无论如何构造哈希函数,冲突是无法完全避免的。
开放地址法
这个方法的基本思想是:当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。这个过程可用下式描述:
H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… , k ( k ≤ m – 1))
其中: H ( key ) 为关键字 key 的直接哈希地址, m 为哈希表的长度, di 为每次再探测时的地址增量。
采用这种方法时,首先计算出元素的直接哈希地址 H ( key ) ,如果该存储单元已被其他元素占用,则继续查看地址为 H ( key ) + d 2 的存储单元,如此重复直至找到某个存储单元为空时,将关键字为 key 的数据元素存放到该单元。
增量 d 可以有不同的取法,并根据其取法有不同的称呼:
( 1 ) d i = 1 , 2 , 3 , …… 线性探测再散列;
( 2 ) d i = 1^2 ,- 1^2 , 2^2 ,- 2^2 , k^2, -k^2…… 二次探测再散列;
( 3 ) d i = 伪随机序列 伪随机再散列;
例1设有哈希函数 H ( key ) = key mod 7 ,哈希表的地址空间为 0 ~ 6 ,对关键字序列( 32 , 13 , 49 , 55 , 22 , 38 , 21 )按线性探测再散列和二次探测再散列的方法分别构造哈希表。
解:
( 1 )线性探测再散列:
32 % 7 = 4 ; 13 % 7 = 6 ; 49 % 7 = 0 ;
55 % 7 = 6 发生冲突,下一个存储地址( 6 + 1 )% 7 = 0 ,仍然发生冲突,再下一个存储地址:( 6 + 2 )% 7 = 1 未发生冲突,可以存入。
22 % 7 = 1 发生冲突,下一个存储地址是:( 1 + 1 )% 7 = 2 未发生冲突;
38 % 7 = 3 ;
21 % 7 = 0 发生冲突,按照上面方法继续探测直至空间 5 ,不发生冲突,所得到的哈希表对应存储位置:
下标: 0 1 2 3 4 5 6
49 55 22 38 32 21 13
( 2 )二次探测再散列:
下标: 0 1 2 3 4 5 6
49 22 21 38 32 55 13
注意:对于利用开放地址法处理冲突所产生的哈希表中删除一个元素时需要谨慎,不能直接地删除,因为这样将会截断其他具有相同哈希地址的元素的查找地址,所以,通常采用设定一个特殊的标志以示该元素已被删除(因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条件)。
例子
已知一个线性表(38,25,74,63,52,48),假定采用h(k)=k%6计算散列地址进行散列存储,若用线性探测的开放定址法处理冲突,则在该散列表上进行查找的平均查找长度为()。
A. 1.5 B. 1.7 C. 2 D. 2.3 2、
解题过程:
(1)计算h(k): 38%6 = 2 25%6 = 1 74%6 = 2 63%6 = 3 52%6 = 4 48%6 = 0
(2)定址: 把不冲突的和冲突的全部列出来即可 地址: 0 1 2 3 4 5
1、线性表第1个元素(38): 38(第1 次不冲突)
2、线性表第2个元素(25): 25(第1次不冲突)
3、线性表第3个元素(74): 74(第1 次冲突,地址 + 1)
4、线性表第3个元素(74): 74(第2 次不冲突)
5、线性表第4个元素(63): 63(第1 次冲突,地址 + 1)
6、线性表第4个元素(63): 63(第2 次不冲突)
7、线性表第5个元素(52): 52(第1 次冲突,地址 + 1)
8、线性表第5个元素(52): 52(第2 次不冲突)
9、线性表第6个元素(48): 48(第1次不冲突)
经过上述定址过程,线性表中的各个元素都有了唯一的地址。
2.3、结果 线性表中的 6 个元素,经过9次定址, 在该散列表上进行查找的平均查找长度为:9/6 = 1.5, 答案选:A
最新文章
- 我心中的MySQL DBA
- Python 绘制图表之我见 ---一个java程序员的看法
- JQuery设置时间段下拉选择 时间下拉选择
- [ActionScript 3.0] xml生成方式之二
- BZOJ 3364: [Usaco2004 Feb]Distance Queries 距离咨询
- extjs实现简单的多文件上传(不借助任何插件),以及包含处理上传大文件的错误的各种处理办法
- 服务器程序源代码分析之三:gunicorn
- webform 转 MVC 飞一般的感觉
- iOS LaunchScreen设置启动图片,启动页停留时间
- mysql导入到elasticsearch
- java zip工具类
- AKKA学习笔记
- 【分享】纯jQuery实现星巴克官网导航栏效果
- lodash中Collection部分所有方法的总结
- MySQL 中 having 和 where 的区别
- 【组合数】[NOIP2011]选择客栈[c++]
- 机器学习 - 开发环境安装pycharm + pyspark + spark集成篇
- POI依据类型设置导出格式
- PTA (Advanced Level) 1005 Spell It Right
- 2018-2019-1 20189218《Linux内核原理与分析》第六周作业