快速解决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，称线性探测再散列。

如果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，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；

④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

缺点：

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

补充知识：java的hashmap如何处理hash碰撞

核心的概念

map是entry的集合，一个key、value就是一个entry

图解

Java在处理hash冲突的时候使用了链表

图中的0到10号 的方块就是entry（键值对），如果发生hashcode的冲突，就会像4号方块那样，开始向后追加，注意看4号方块的next的属性，那个属性不是null，而是指向了一个方块

以上这篇快速解决Hash碰撞冲突的方法小结就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持我们。

赞 (0)

相关推荐

  • 谈谈Hashmap的容量为什么是2的幂次问题

    做为面试常考的问题之一,每次都答的模模糊糊,有必要了解一下,首先来看一下hashmap的put方法的源码 public V put(K key, V value) { if (key == null) return putForNullKey(value); //将空key的Entry加入到table[0]中 int hash = hash(key.hashCode()); //计算key.hashcode()的hash值,hash函数由hashmap自己实现 int i = indexFor(

  • Java HashMap源码及并发环境常见问题解决

    HashMap源码简单分析: 1 一切需要从HashMap属性字段说起: /** The default initial capacity - MUST be a power of two. 初始容量 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * The maximum capacity, used if a higher value is implicitly specified * by eit

  • 浅谈HashMap、HashTable的key和value是否可为null

    结论: HashMap对象的key.value值均可为null. HahTable对象的key.value值均不可为null. 且两者的的key值均不能重复,若添加key相同的键值对,后面的value会自动覆盖前面的value,但不会报错. public class Test { public static void main(String[] args) { Map<String, String> map = new HashMap<String, String>();//Has

  • HashMap容量和负载因子使用说明

    HashMap底层数据结构是数组+链表,JDK1.8中还引入了红黑树,当链表长度超过8个时,会将链表转成红黑树,以提升其查找性能. 那么,给出一个<key, value>节点,HashMap是如何确定这个节点应该放在具体哪个位置呢?(以JDK1.8为例) final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p;

  • 快速解决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

  • IDEA中解决 git pull 冲突的方法

    0.事先准备. 1)把远程仓库的README.md内容改写为bbb(原先为aaa). 2)本地仓库的README.md内容改写为ccc(原先也为aaa). 以此来模仿代码冲突. 1.先commit 再pull pull的时候会提示有冲突,需要你进行手动merge Accept Yours 就是直接选取本地的代码,覆盖掉远程仓库的 Accept Theirs 是直接选取远程仓库的,覆盖掉自己本地的 我们选择Merge,自己手动行进选择.修改. 这里左边部分是你本地仓库的代码,右边部分是远程仓库的代

  • 使用Maven Helper解决Maven插件冲突的方法

    1.何为依赖冲突 Maven是个很好用的依赖管理工具,但是再好的东西也不是完美的.Maven的依赖机制会导致Jar包的冲突.举个例子,现在你的项目中,使用了两个Jar包,分别是A和B.现在A需要依赖另一个Jar包C,B也需要依赖C.但是A依赖的C的版本是1.0,B依赖的C的版本是2.0.这时候,Maven会将这1.0的C和2.0的C都下载到你的项目中,这样你的项目中就存在了不同版本的C,这时Maven会依据依赖路径最短优先原则,来决定使用哪个版本的Jar包,而另一个无用的Jar包则未被使用,这就

  • pycharm 快速解决python代码冲突的问题

    pycharm 快速解决python代码冲突的问题

    找到冲突的文件(项目中报红的就是冲突文件),如下 :以下是一个标准的冲突表 <<<<<<< HEAD new new new new code ======= old old old code >>>>>>> xxxxxxxxxxxxxxxxxxxxxxx 说明 * : <<<<<<< HEAD 到 =======里面的内容是自己分支commit的内容 =========到 >

  • Java 数据结构哈希算法之哈希桶方式解决哈希冲突

    一. 实现形式一(键值对只能为整数) 我们可以先实现一个比较简单的哈希表,使用java中解决哈希冲突的方法,即哈希桶(开散列)方式实现,其中注意: 可以使用内部类方式定义节点 负载因子默认为0.75 因为我们使用的是哈希桶方式解决哈希冲突,所以在我们扩容成功之后,原来桶中的数据得重新哈希计算出新的位置,不然就和原来桶中的数据的位置不一样了 相关代码如下 public class HashBucket { static class Node {//使用内部类方式定义节点 public int ke

  • js鼠标单击和双击事件冲突问题的快速解决方法

    情况一 如果在一个DOM对象上同时绑定单击(click)和双击(dblclick)事件,当在这个DOM对象上发生双击事件时,第一次点击(click)会 触发一次单击(click)事件,第二次点击(连续的)也会触发双击(dblclick)事件,还是会触发单击(click)事件(IE7与 firefox). 解决方法: <button onclick="test(1)" ondblclick="test(2)"></button> <scr

  • onclick和onblur冲突问题的快速解决方法

    onclick和onblur冲突问题的快速解决方法

    新浪首页的搜索框里面有一个使用ajax的下拉框.我们需要实现一个点击下拉框里面的一项,让搜索框里面的值变成这一项,同时下拉框消失的效果,但同时在点击其他地方的时候,这个下拉框也要消失.大致如图: 我们同时使用onblur和onclick来使下拉框隐藏,但是更大的问题出现了,这两个功能相冲突,onblur过于强悍,根本没有onclick方法实现的机会,搜索框无法获取点击项的内容.这个就是我们想要解决的onclick和onblur冲突问题. 对应这个问题,这里我们介绍两种解决办法: 1. 使用set

  • jquery中的常见问题及快速解决方法小结

    1 在开发开放聊天室的过程中,遇到使用ajax提交表单插入数据库时会插入两条数据的情况 解决办法,在ajax函数返回后,return false. $("#btn").click(function(){ $.ajax({ do something }); return false; }) 2 去除选中元素的某一个属性使用removeattr 3 javascript中与时间相关的函数有setInterval("function",millisec[,"la

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

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

  • python3.8与pyinstaller冲突问题的快速解决方法

    安装pyinstaller 安装的时候 进入cmd pip install pyinstaller 发现安装报错! 解决办法: # 自主下载pyinstaller包,进行手动安装 pyinstaller 的下载地址:http://www.pyinstaller.org/downloads.html 下载文件后,解压文件. cmd 进入解压的路径 输入: python setup.py install 等待一段时间,pyinstaller就会安装成功 Python项目生成可执行程序的步骤 选择一:

随机推荐