文档章节

Hash冲突解决

fengsehng
 fengsehng
发布于 2016/11/09 09:12
字数 850
阅读 4
收藏 0

hash的冲突不可避免的

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,2,-2,4,-4,9,-9,16,-16,…k*k,-k*k(k<=m/2)
称二次探测再散列。如果di取值可能为伪随机数列。称伪随机探测再散列。

2.再哈希法

当发生冲突时,使用第二个、第三个、哈希函数计算地址,直到无冲突时。缺点:计算时间增加。
比如上面第一次按照姓首字母进行哈希,如果产生冲突可以按照姓字母首字母第二位进行哈希,再冲突,第三位,直到不冲突为止

3。链地址法

将所有关键字为同义词的记录存储在同一线性链表中。如下:

因此这种方法,可以近似的认为是筒子里面套筒子

4.建立一个公共溢出区

假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表,另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。

拉链法的优缺点:

优点:

①拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;
②由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;
③开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;
④在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表,删除结点不能简单地将被删结 点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。

拉链法的缺点

 拉链法的缺点是:指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。

参考:
http://yiluohuanghun.blog.51cto.com/3407300/1305172
http://yiluohuanghun.blog.51cto.com/3407300/1305172

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧

微信订阅号二维码如下:

这里写图片描述

© 著作权归作者所有

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
Memcached Hash算法

本文来自网易云社区 作者:吕宗胜 Hash算法 1. Memcached Hash介绍 我们在前面的文章中已经介绍过了Memcached的内存管理方式,LRU的策略。由于Memcached的数据存储方式基本上是基于双向链表来...

网易云
09/11
0
0
NSDictionary实现原理

NSDictionary是基于key - value 方式,把key映射到一个hash表中实现的 key 需要支持NSCopying协议,实际上不支持也可以作为key,但在swift中就必须要支持,支持NSCopying的原因在于,NSDicit...

庄msia
08/16
0
0
开放地址法散列

开放地址法 开放地址法是另一种(相对于分离链接法)解决散列冲突的方法。适用于装填因子(散列表中元素个数和散列表长度比)较小(小于0.5)的散列表。 开放地址法中索引的计算方法为$$h_{...

月见樽
01/23
0
0
JAVA基础-自问自答学hashCode和equals

前言 和常常在面试中会被问到,在工作中我们也有可能遇到要重写对象方法的情况,而且方法的设计思想值得我们学习,所以我们有必要去深入学习一下这两个方法。 下面我就以面试问答的形式学习我...

liangzzz
2017/09/08
0
0
JAVA基础-自问自答学hashCode和equals

前言 和常常在面试中会被问到,在工作中我们也有可能遇到要重写对象方法的情况,而且方法的设计思想值得我们学习,所以我们有必要去深入学习一下这两个方法。 下面我就以面试问答的形式学习我...

liangzzz
2017/09/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

DES/3DES(TripleDES)加密、解密测试数据

以下结果经 PHP+openssl及VB.NET验证,ECB模式。 PHP 7.0.10 (cli) (built: Aug 18 2016 09:48:53) ( ZTS ) OpenSSL Library Version: OpenSSL 1.0.1t 3 May 2016 VB.net 2003 ****** DES(S......

SamXIAO
40分钟前
1
3
Java11的新特性

Java语言特性系列 Java5的新特性 Java6的新特性 Java7的新特性 Java8的新特性 Java9的新特性 Java10的新特性 Java11的新特性 Java12的新特性 序 本文主要讲述一下Java11的新特性 版本号 java...

go4it
41分钟前
3
0
Maven常用命令及相关笔记

Maven常用命令 dos指令 4. 编译源代码: mvn compile 6. 运行测试: mvn test 8. 打包: mvn package 9. 在本地Repository中安装jar: mvn install 10. 清除产生的项目: mvn clean 4. 运行项...

颖伙虫
48分钟前
1
0
swagger2.2.2 与 spring cloud feign冲突 导致服务请求报空

swagger2.2.2 与 spring cloud feign冲突 Java代码 Caused by: org.springframework.beans.factory.BeanCreationException: Error creating bean with name 'com.choosefine.web.console.ar......

泉天下
51分钟前
1
0
设计模式之 明确责任 观察者模式 状态模式 责任链模式

观察者模式是任务分发的一种模式。 如果认为我们设计的系统的各个模块(或子系统)的最终目的是完成共同任务,那么这个任务如何分配到多个模块的就是我们遇到的第一个问题。简单设计场合我们...

backbye
55分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部