文档章节

Hash冲突解决

fengsehng
 fengsehng
发布于 2016/11/09 09:12
字数 850
阅读 4
收藏 0
点赞 0
评论 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
朝阳
程序员
hash查找和hashmap

search by hashing 解决顺序查找一一对比的问题,对存入数据的key取hashcode并存入array,查找数据时以key的hashcode作为索引返回数据。 hash collision 没有一种hash算法可以避免hash冲突,...

gangzz ⋅ 2014/08/25 ⋅ 0

Hash-冲突的解决

为提高hash表查找性能,除了考虑选择合适的hash表表长和完美的hash函数外,还必须考虑hash表处理冲突的能力。当hash函数对两个不同的数据项产生了相同的hash值时,冲突就产生了。对于冲突的处...

DYOS ⋅ 2014/11/10 ⋅ 1

开放地址法散列

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

月见樽 ⋅ 01/23 ⋅ 0

JAVA基础-自问自答学hashCode和equals

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

liangzzz ⋅ 2017/09/08 ⋅ 0

JAVA基础-自问自答学hashCode和equals

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

liangzzz ⋅ 2017/09/08 ⋅ 0

PHP中HASH函数的优化技巧

Hash数据结构是一种非常常见的数据结构,作为一个程序员,你可能每天都在和它接触, 尽管很多时候你可能没有意识到。Hash在PHP内核中扮演了非常重要的角色,数组、变量作用域、函数参数列表等...

ChefXu ⋅ 2015/12/04 ⋅ 4

PHP 实现HASH表

Hash 表又称散列表,通过关键字Key 映射到数组中一个位置来访问记录 Hash 函数的作用是把任意长度的输入,通过HASH算法变换成固定长度的输出,该输出就是HASH值 HASH表的时间复杂度为O(1) ...

eatnothing ⋅ 2015/11/04 ⋅ 0

Java中hashMap的源码初探

最近一段时间准备沉下心来,认真学习底层的东西。今天从HashMap开始吧。看源码,我个人觉得应该带着问题去看,去学习大师们怎么做的。 {:toc} HashMap 底层是用什么数据结构实现的? HashMa...

lifer ⋅ 2016/10/10 ⋅ 0

网络攻击技术(三)——Denial Of Service

1.1.1 摘要 最近网络安全成了一个焦点,除了国内明文密码的安全事件,还有一件事是影响比较大的——Hash Collision DoS(通过Hash碰撞进行的拒绝式服务攻击),有恶意的人会通过这个安全漏洞...

长平狐 ⋅ 2012/06/11 ⋅ 0

源码分析HashMap的几个问题(JDK1.7)

如何存储数据 (put、get) put数据 get数据 默认容量为什么是16 我们先看一下源码如何获取index的值 index的值是通过key的hash值与数组长度-1进行位运算来的。举个例子, 计算book的hashcod...

宇你同在 ⋅ 06/10 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

如何使用serverchan微信推送告警

之前实现推送告警信息到微信的方法有如下几种: 1、通过企业公众号实现----收费: 2、通过QQ邮箱,在微信平台上开启收到邮件进行提醒; 3、第三方告警平台API,一般也是收费的; 不过最近看文...

问题终结者 ⋅ 6分钟前 ⋅ 0

TCP的RPC

RPC就是远程方法调用(Remote Process Call ),包含了客户端和服务端,涉及了对象的序列化传输。 1.服务端启动,注册远程调用的类2.客户端发送请求信息包含类、方法、参数的一些信息、序列化传...

Cobbage ⋅ 27分钟前 ⋅ 0

IOS-UI UI初步代码布局添加事件

ISO开发界面,UI是必须学习的一部分,其实很早之前想学来了,一直没有沉下心来学习。看到IOS的代码风格和布局就别扭的不行,跟java代码和android布局比较显得不是那么方便,所以一直到现在。...

京一 ⋅ 37分钟前 ⋅ 0

浅谈OpenDaylight的二次开发

OpenDaylight作为一款开源SDN网络控制器,依托于强大的社区支持以及功能特性,成为了目前主流的SDN网络控制器开发平台。在比较稳定的OpenDaylight Helium版本中,已经为开发者提供了大量的网...

wangxuwei ⋅ 46分钟前 ⋅ 0

API 开发中可选择传递 token 接口遇到的一个坑

在做 API 开发时,不可避免会涉及到登录验证,我使用的是jwt-auth 在登录中会经常遇到一个token过期的问题,在config/jwt.php默认设置中,这个过期时间是一个小时,不过为了安全也可以设置更...

等月人 ⋅ 47分钟前 ⋅ 0

Java NIO之文件处理

程序要操作本地操作系统的一个文件,可以分为以下三个部分: 对文件位置的操作 对文件的操作 对文件内容的操作 其中,对文件内容的操作在 Java NIO之Channel 中已经有了介绍,通过FileChann...

士别三日 ⋅ 52分钟前 ⋅ 0

Maven的pom.xml配置文件详解

<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.......

小海bug ⋅ 今天 ⋅ 0

解决httpclient超时设置不生效的问题

最近公司有项目需要通过http调用第三方服务,且第三方服务偶有超时,故需要设置一定的超时时间防止不响应的情况出现。 初始设置如下: [java] view plain copy //超时设置 RequestConfig re...

Mr_Tea伯奕 ⋅ 今天 ⋅ 0

过滤器Filter和拦截器HandlerInterceptor

过滤器 依赖于servlet容器。在实现上基于函数回调,可以对几乎所有请求进行过滤,但是缺点是一个过滤器实例只能在容器初始化时调用一次。使用过滤器的目的是用来做一些过滤操作,获取我们想要...

hutaishi ⋅ 今天 ⋅ 0

Redis入门详解(转)

Redis入门详解 Redis简介 Redis安装 Redis配置 Redis数据类型 Redis功能 持久化 主从复制 事务支持 发布订阅 管道 虚拟内存 Redis性能 Redis部署 Redis应用场景 Redis总结 Redis简介: Redi...

xiaoyaoyoufang ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部