如何解决hash冲突

1)冲突是如何产生的？

　　上文中谈到，哈希函数是指如何对关键字进行编址的规则，这里的关键字的范围很广，可视为无限集，如何保证无限集的原数据在编址的时候不会出现重复呢？规则本身无法实现这个目的。举一个例子，仍然用班级同学做比喻，现有如下同学数据
张三，李四，王五，赵刚，吴露.....
假如我们编址规则为取姓氏中姓的开头字母在字母表的相对位置作为地址，则会产生如下的哈希表

位置 字母 姓名
0 a
1 b
2 c

...

10    L     李四

...

22 W 王五，吴露

..

25  Z  张三，赵刚

我们注意到，灰色背景标示的两行里面，关键字王五，吴露被编到了同一个位置，关键字张三，赵刚也被编到了同一个位置。老师再拿号来找张三，座位上有两个人，"你们俩谁是张三？"

2)如何解决冲突问题

既然不能避免冲突，那么如何解决冲突呢，显然需要附加的步骤。通过这些步骤，以制定更多的规则来管理关键字集合，通常的办法有:

a)开放地址法

开放地执法有一个公式: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取值可能为伪随机数列。称伪随机探测再散列。仍然以学生排号作为例子，
现有两名同学，李四，吴用。李四与吴用事先已排好序，现新来一名同学，名字叫王五，对它进行编制

10.. .... 22 .. .. 25
李四.. .... 吴用 .. .. 25

　　赵刚未来之前

10.. .. 22 23 25
李四.. 吴用 王五

　　(a)线性探测再散列对赵刚进行编址，且di=1

10... 20 22 .. 25
李四.. 王五 吴用

　　(b)二次探测再散列，且di=-2

1... 10... 22 .. 25
王五.. 李四.. 吴用

　　(c)伪随机探测再散列,伪随机序列为:5,3,2

b)再哈希法

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

c)链地址法

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

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

d)建立一个公共溢出区

假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。
经过以上方法，基本可以解决掉hash算法冲突的问题。

注:之所以会简单得介绍了hash，是为了更好的学习lzw算法，学习lzw算法是为了更好的研究gif文件结构，最后，我将详细的阐述一下gif文件是如何构成的，如何高效操作此种类型文件。

以上就是本文的全部内容，希望能给大家一个参考，也希望大家多多支持我们。

赞 (0)

相关推荐

  • PHP利用hash冲突漏洞进行DDoS攻击的方法分析

    本文实例分析了PHP利用hash冲突漏洞进行DDoS攻击的方法.分享给大家供大家参考.具体分析如下: 首先声明:本文内容只用于研究学习使用,请勿用于非法行为! 前面提到过最近爆出的hash表碰撞漏洞,包括java.python.php等在内的很多常用语言均未幸免,今晚咱就来实际看看它的威力. 攻击原理: 通过向目标服务器post一组精心拼凑的数组参数,到达服务端后语言底层处理接收到的数组参数时,由于该漏洞的存在造成CPU的大量消耗,最终导致服务器资源耗尽. 不用什么花哨的手法,就用PHP简单实现

  • java开放地址法和链地址法解决hash冲突的方法示例

    hashMap对各位小伙们来说,没有不知道的了,使用过的人想必或多或少的都了解一点hashMap的底层实现原理,总结来说就是,数组+链表,至于源码的实现,大家可参看源码,今天想说的是hashMap是怎么解决hash冲突的呢? 首先看一张图, 从这张图也大概可以看出来,hashMap维护的是一个数组,数组里面的每个单元又是一个个链表,那么为什么会产生hash冲突呢?这也就是接下来要探讨的问题. 既是数组,必然会有长度,当我们在往数组中插入数据的时候,不管是什么类型的数据,对于数组来说,就是占据了某

  • 如何解决hash冲突

    如何解决hash冲突

    1)冲突是如何产生的? 上文中谈到,哈希函数是指如何对关键字进行编址的规则,这里的关键字的范围很广,可视为无限集,如何保证无限集的原数据在编址的时候不会出现重复呢?规则本身无法实现这个目的.举一个例子,仍然用班级同学做比喻,现有如下同学数据 张三,李四,王五,赵刚,吴露..... 假如我们编址规则为取姓氏中姓的开头字母在字母表的相对位置作为地址,则会产生如下的哈希表 位置 字母 姓名 0 a 1 b 2 c ... 10    L     李四 ... 22 W 王五,吴露 .. 25  Z 

  • 快速解决Hash碰撞冲突的方法小结

    Hash碰撞冲突 我们知道,对象Hash的前提是实现equals()和hashCode()两个方法,那么HashCode()的作用就是保证对象返回唯一hash值,但当两个对象计算值一样时,这就发生了碰撞冲突.如下将介绍如何处理冲突,当然其前提是一致性hash. 1.开放地址法 开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,-,k(k<=m-1) 其中,m为哈希表的表长.di 是产生冲突的时候的增量序列.如果di值可能为1,2,3,-m-1,称线性探测再散列. 如果d

  • 详解Eclipse提交项目到GitHub以及解决代码冲突

    前言:来这家公司上班后,开始使用Git作为项目版本控制系统,由于以前用的是SVN,所以对Git也就简单学习了一下.但是,实践出真知,当开始使用Git后,发现遇到了不少问题,也遇到过血的教训,于是决定记录一下,方便以后查看. 一.Eclipse安装Git插件 如果是比较新的Eclipse版本,默认就已经安装了Git插件. 菜单栏 --> Help --> About Eclipse ,如下图: 如果有这个图标,表示Eclipse已经安装了Git插件,如果没有这个图标,就到Eclipse插件市场下

  • maven解决包冲突方法详解

    maven解决包冲突方法详解

    Maven根据最近胜利策略(nearest wins strategy)的原则工作,同时解决依赖冲突,这意味着它在依赖树中找到更接近的版本,它将采用该版本并忽略其他版本.实际上Maven有点懒,所以每当它开始寻找依赖时,它就会从根目录开始遍历树,无论它先前找到哪个版本,它都会选择它并从它们返回而不进一步.如果它进一步寻找依赖版本,可能会有机找到一些更新的版本,但它从第一个发现的版本那里返回,并采用旧版本并用它来解决依赖关系. 可以用下面的命令显示依赖树: mvn dependency:tree

  • 基于django2.2连oracle11g解决版本冲突的问题

    上次用django2.2和oracle11g,在migrate的时候发生了版本冲突,最终将Oracle升级到了12c才解决问题 那么到底能不能用别的方法来解决这个冲突呢?想了个解决思路,实践一下: 用django2.2连Oracle12c环境下做migrate,创建基础表 将基础表导出,再导入到Oracle11g数据库中 用django2.2连Oracle11g 实施步骤 1.用django2.2连Oracle12c环境下做migrate,创建基础表 在前文中已经完成,连接到数据库,可以看到有1

  • Android ViewPager自定义轮播图并解决播放冲突

    本文实例为大家分享了Android ViewPager自定义轮播图,并解决播放冲突,供大家参考 首先介绍一下这篇小代码: 注释全面,简单易学,适用初学者,图片自拟!!! 一定要将ArrayList集合&Handler机制传到适配器,否则无法完成展示,也解决不了滑动冲突,代码有点多,但是它通俗易懂啊 layout布局内写法: <?xml version="1.0" encoding="utf-8"?> <LinearLayout xmlns:

  • 如何在IDEA中快速解决Jar冲突详解

    如何在IDEA中快速解决Jar冲突详解

    目录 一.为什么会产生Jar包冲突? 1.1 直接与传递依赖 1.2 Maven 的传递依赖 1.3 Maven 如何解决版本冲突? 1.4 覆盖传递依赖版本 1.5 使用直接依赖覆盖传递依赖版本 二.通过IDEA快捷解决依赖冲突 2.1 查找冲突 2.2 发现冲突 2.3 解决冲突 一.为什么会产生Jar包冲突? 作为 Java 开发人员,我们可能会使用 Maven 维护许多应用程序以进行依赖项管理.这些应用程序需要不时升级以保持最新状态并添加新功能或安全更新. 由于某些依赖项之间的冲突,这个

  • PowerShell中运行CMD命令的技巧总结（解决名称冲突和特殊字符等问题）

    引言 我从老旧的 CMD.EXE 命令行换到优秀的 POWSERSHELL.EXE 已经有一段时间啦.您可能知道新的 Windows PowerShell 可以运行任何旧命令.不过有些旧命令的名称或语法可能会产生问题.但这都不是事儿. 麻烦 1:名称冲突 PowerShell 的 cmdlet 别名和旧命令的名称有冲突是个常见的问题.比如说您喜欢的服务控制命令 SC.EXE.SC.EXE 非常灵活!我能理解您为什么喜欢它(不要为用 NET.EXE 管理服务找借口).如果您想查看 SMB Serv

随机推荐