解决hashmap冲突的四个方法

朱雀 2021-11-02 07:34 422阅读 0赞

Hash函数

非哈希表的特点：关键字在表中的位置和它之间不存在一个确定的关系，查找的过程为给定值一次和各个关键字进行比较，查找的效率取决于和给定值进行比较的次数。

哈希表的特点：关键字在表中位置和它之间存在一种确定的关系。

哈希函数：一般情况下，需要在关键字与它在表中的存储位置之间建立一个函数关系，以f(key)作为关键字为key的记录在表中的位置，通常称这个函数f(key)为哈希函数。

hash : 翻译为“散列”，就是把任意长度的输入，通过散列算法，变成固定长度的输出，该输出就是散列值。

这种转换是一种压缩映射，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。
    
           简单的说就是一种将任意长度的消息压缩到莫伊固定长度的消息摘要的函数。

hash冲突：就是根据key即经过一个函数f(key)得到的结果的作为地址去存放当前的key value键值对(这个是hashmap的存值方式)，但是却发现算出来的地址上已经有人先来了。就是说这个地方被抢了啦。这就是所谓的hash冲突啦。

哈希函数处理冲突的方法

**1.开放定址法：**

其中 m 为表的长度

对增量di有三种取法：

线性探测再散列 di = 1 , 2 , 3 , … , m-1

平方探测再散列 di = 1 2 , -2 , 4 , -4 , 8 , -8 , … , k的平方 , -k平方

随机探测再散列 di 是一组伪随机数列

**2.链地址法**

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

**3.再哈希**

这种方法是同时构造多个不同的哈希函数：

Hi=RH1（key） i=1，2，…，k

当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

**4.建立公共溢出区**

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

HashMap的Hash冲突处理办法

hashmap出现了Hash冲突的时候采用第二种办法：链地址法。

发表评论取消回复

表情：

评论列表（有 0 条评论，422人围观）

还没有评论，来说两句吧...

相关阅读

相关哈希冲突及四种解决方法

哈希冲突的产生原因哈希是通过对数据进行再压缩，提高效率的一种解决方法。但由于通过哈希函数产生的哈希值是有限的，而数据可能比较多，导致经过哈希函数处理后仍然有不同的数据对

悠悠/ 2022年12月19日 00:54/ 0 赞/ 150 阅读

相关 HashMap 如何解决 Hash 冲突

通过引入单向链表来解决 Hash 冲突。当出现 Hash 冲突时，比较新老 key 值是否相等，如果相等，新值覆盖旧值。如果不相等，新值会存入新的 Node 结点，指向老

系统管理员/ 2022年09月16日 12:22/ 0 赞/ 312 阅读

相关 TortosieGit解决冲突的方法

项目开发中，发生冲突很影响开发效率，发生冲突时，我们必须能正确识别哪些是我们自己的代码，哪些是别人开发的代码。 git发生冲突后，产生了3个文件或者更多文件，比如我在t.p

ゝ一世哀愁。/ 2022年06月11日 03:54/ 0 赞/ 287 阅读

相关 java基础--HashMap解决hash冲突的方法

写的不错，记录下转载了，面试必问的。原文地址： [http://xiaolu123456.iteye.com/blog/1485349][http_xiaolu123456.i

古城微笑少年丶/ 2022年05月30日 07:25/ 0 赞/ 243 阅读

相关解决hash冲突的三个方法

原文地址：https://www.cnblogs.com/wuchaodzxx/p/7396599.html 目录 1、开放定址法 1.1 线性探测再散

た入场券/ 2022年05月21日 11:50/ 0 赞/ 295 阅读

相关 Git冲突的解决方法

说明：前段时间有点忙，没有继续写一些工作中积累总结的东西，最近时间相对比较充裕了，继续分享点东西；前面的篇章已经说过，Git是我们公司的代码管理工具，我以前没用过，在学习使用

迈不过友情╰/ 2022年05月18日 03:44/ 0 赞/ 293 阅读

相关 HashMap原理及冲突解决办法

class HashMap<K,V> extends AbstractMap<K,V> HashMap put() HashMap get() 1.put(

Love The Way You Lie/ 2022年05月09日 15:20/ 0 赞/ 250 阅读

相关【Java-集合】HashMap-Hash冲突解决

【Java-集合】HashMap-Hash冲突解决 2017年10月22日 20:49:58 [binke\_mxb][binke_mxb] 阅读数：5371 版权声

た入场券/ 2022年02月28日 07:10/ 0 赞/ 276 阅读

相关解决hashmap冲突的四个方法

Hash函数非哈希表的特点：关键字在表中的位置和它之间不存在一个确定的关系，查找的过程为给定值一次和各个关键字进行比较，查找的效率取决于和给定值进行比较的次数。

朱雀/ 2021年11月02日 07:34/ 0 赞/ 423 阅读

相关 Hash算法解决冲突的方法

Hash算法解决冲突的方法一般有以下几种常用的解决方法 1，开放定址法：所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散

小鱼儿/ 2021年08月19日 17:56/ 0 赞/ 445 阅读