HashMap发生hash冲突怎么办

2021-01-25 17:02发布

HashMap发生hash冲突怎么办?

HashMap发生hash冲突怎么办?

10条回答
yjh
2楼 · 2021-01-26 10:30

散列表要解决的一个问题就是散列值的冲突问题,通常是两种方法:链表法和开放地址法

  • 链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位;

  • 开放地址法是通过一个探测算法,当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。

java.util.HashMap采用的链表法的方式,链表是单向链表。形成单链表的核心代码如下:

voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){Entryk,v

上面方法的代码很简单,但其中包含了一个设计:系统总是将新添加的 Entry 对象放入 table 数组的 bucketIndex 索引处——如果 bucketIndex 索引处已经有了一个 Entry 对象,那新添加的 Entry 对象指向原有的 Entry 对象(产生一个 Entry 链),如果 bucketIndex 索引处没有 Entry 对象,也就是上面程序代码的 e 变量是 null,也就是新放入的 Entry 对象指向 null,也就是没有产生 Entry 链。

HashMap里面没有出现hash冲突时,没有形成单链表时,hashmap查找元素很快,get()方法能够直接定位到元素,但是出现单链表后,单个bucket 里存储的不是一个 Entry,而是一个 Entry 链,系统只能必须按顺序遍历每个 Entry,直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端(该 Entry 是最早放入该 bucket 中),那系统必须循环到最后才能找到该元素。

当创建 HashMap 时,有一个默认的负载因子(load factor),其默认值为 0.75,这是时间和空间成本上一种折衷:增大负载因子可以减少 Hash 表(就是那个 Entry 数组)所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的的操作(HashMap 的 get() 与 put() 方法都要用到查询);减小负载因子会提高数据查询的性能,但会增加 Hash 表所占用的内存空间。


我的网名不再改
3楼 · 2021-01-26 14:06

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冲突的时候采用第二种办法:链地址法。

代码示例:

有一个”国家”(Country)类,我们将要用Country对象作为key,它的首都的名字(String类型)作为value。下面的例子有助于我们理解key-value对在HashMap中是如何存储的。

public classCountry {

String name;longpopulation;public Country(String name, longpopulation) {super();this.name =name;this.population =population;

}publicString getName() {returnname;

}public voidsetName(String name) {this.name =name;

}public longgetPopulation() {returnpopulation;

}public void setPopulation(longpopulation) {this.population =population;

}//If length of name in country object is even then return 31(any random//number) and if odd then return 95(any random number).//This is not a good practice to generate hashcode as below method but I am//doing so to give better and easy understanding of hashmap.

@Overridepublic inthashCode() {if (this.name.length() % 2 == 0)return 31;else

return 95;

}

@Overridepublic booleanequals(Object obj) {

Country other=(Country) obj;if(name.equalsIgnoreCase((other.name)))return true;return false;

}

}

public classHashMapStructure {public static voidmain(String[] args) {

Country india= new Country("India", 1000);

Country japan= new Country("Japan", 10000);

Country france= new Country("France", 2000);

Country russia= new Country("Russia", 20000);

HashMap countryCapitalMap = new HashMap();

countryCapitalMap.put(india,"Delhi");

countryCapitalMap.put(japan,"Tokyo");

countryCapitalMap.put(france,"Paris");

countryCapitalMap.put(russia,"Moscow");

Iterator countryCapitalIter =countryCapitalMap.keySet().iterator();//put debug point at this line

while(countryCapitalIter.hasNext()) {

Country countryObj=countryCapitalIter.next();

String capital=countryCapitalMap.get(countryObj);

System.out.println(countryObj.getName()+ "----" +capital);

}

}

}

在注释处加入debug,可以通过watch查看countryCapitalMap的结构:

从上图可以观察到以下几点:

有一个叫做table大小是16的Entry数组。

这个table数组存储了Entry类的对象。HashMap类有一个叫做Entry的内部类。这个Entry类包含了key-value作为实例变量。我们来看下Entry类的结构。Entry类的结构:

static class Entry implementsMap.Entry{finalK key;

V value;

Entry next;final inthash;

...//More code goes here

}

1).每当往hashmap里面存放key-value对的时候,都会为它们实例化一个Entry对象,这个Entry对象就会存储在前面提到的Entry数  组table中。现在你一定很想知道,上面创建的Entry对象将会存放在具体哪个位置(在table中的精确位置)。答案就是,根据key的     hashcode()方法计算出来的hash值(来决定)。hash值用来计算key在Entry数组的索引。

2).现在,如果你看下上图中数组的索引15,它有一个叫做HashMap$Entry的Entry对象。

3).我们往hashmap放了4个key-value对,但是看上去好像只有1个元素!!!这是因为,如果两个元素有相同的hashcode,它们会  被放在同一个索引上。问题出现了,该怎么放呢?原来它是以链表(LinkedList)的形式来存储的(逻辑上)。因此他们都在hash值为15的位置  上存着了,然后把多个Entry,用next进行链接。


Sunny
4楼 · 2021-01-26 17:52

hash值冲突是发生在put()时,从源码可以看出,hash值是通过hash(key.hashCode())来获取的,当put的元素越来越多时,难免或出现不同的key产生相同的hash值问题,也即是hash冲突,当拿到一个hash值,通过indexFor(hash, table.length)获取数组下标,先查询是否存在该hash值,若不存在,则直接以Entry的方式存放在数组中,若存在,则再对比key是否相同,若hash值和key都相同,则替换value,若hash值相同,key不相同,则形成一个单链表,将hash值相同,key不同的元素以Entry的方式存放在链表中,这样就解决了hash冲突,这种方法叫做分离链表法,与之类似的方法还有一种叫做 开放定址法,开放定址法师采用线性探测(从相同hash值开始,继续寻找下一个可用的槽位)hashMap是数组,长度虽然可以扩大,但用线性探测法去查询槽位查不到时怎么办?因此hashMap采用了分离链表法。

HashMap 采用一种所谓的“Hash 算法”来决定每个元素的存储位置。当程序执行 map.put(String,Obect)方法 时,系统将调用String的 hashCode() 方法得到其 hashCode 值——每个 Java 对象都有 hashCode() 方法,都可通过该方法获得它的 hashCode 值。得到这个对象的 hashCode 值之后,系统会根据该 hashCode 值来决定该元素的存储位置。

寂静的枫林
6楼 · 2021-01-27 13:40

hash值冲突是发生在put()时,从源码可以看出,hash值是通过hash(key.hashCode())来获取的,当put的元素越来越多时,难免或出现不同的key产生相同的hash值问题,也即是hash冲突,当拿到一个hash值,通过indexFor(hash, table.length)获取数组下标,先查询是否存在该hash值,若不存在,则直接以Entry分离链表法,与之类似的方法还有一种叫做 开放定址法,开放定址法师采用线性探测(从相同hash值开始,继续寻找下一个可用的槽位)hashMap是数组,长度虽然可以扩大,但用线性探测法去查询槽位查不到时怎么办?因此hashMap采用了分离链表法。

我是大脸猫
7楼 · 2021-01-27 16:23

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=RH1key  i=12k

  当哈希地址Hi=RH1key)发生冲突时,再计算Hi=RH2key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。

  4.建立公共溢出区

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

 HashMap的Hash冲突处理办法

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

代码示例:

  有一个”国家”(Country)类,我们将要用Country对象作为key,它的首都的名字(String类型)作为value。下面的例子有助于我们理解key-value对在HashMap中是如何存储的。

复制代码

public class Country {     String name;     long population;     public Country(String name, long population) {         super();         this.name = name;         this.population = population;     }     public String getName() {         return name;     }     public void setName(String name) {         this.name = name;     }     public long getPopulation() {         return population;     }     public void setPopulation(long population) {         this.population = population;     }     // If length of name in country object is even then return 31(any random     // number) and if odd then return 95(any random number).     // This is not a good practice to generate hashcode as below method but I am     // doing so to give better and easy understanding of hashmap.     @Override     public int hashCode() {         if (this.name.length() % 2 == 0)             return 31;         else             return 95;     }     @Override     public boolean equals(Object obj) {         Country other = (Country) obj;         if (name.equalsIgnoreCase((other.name)))             return true;         return false;     } }

复制代码复制代码

   =  Country("India", 1000=  Country("Japan", 10000=  Country("France", 2000=  Country("Russia", 20000 countryCapitalMap =  HashMap"Delhi""Tokyo""Paris""Moscow" countryCapitalIter =         ==+ "----" +

复制代码

  在注释处加入debug,可以通过watch查看countryCapitalMap的结构:

          

 

从上图可以观察到以下几点:

 

  1. 有一个叫做table大小是16的Entry数组。

  2. 这个table数组存储了Entry类的对象。HashMap类有一个叫做Entry的内部类。这个Entry类包含了key-value作为实例变量。我们来看下Entry类的结构。Entry类的结构: 

复制代码

static class Entry implements Map.Entry{         final K key;         V value;         Entry next;         final int hash;         ...//More code goes here }

复制代码

    1).每当往hashmap里面存放key-value对的时候,都会为它们实例化一个Entry对象,这个Entry对象就会存储在前面提到的Entry数  组table中。现在你一定很想知道,上面创建的Entry对象将会存放在具体哪个位置(在table中的精确位置)。答案就是,根据key的     hashcode()方法计算出来的hash值(来决定)。hash值用来计算key在Entry数组的索引。

    2).现在,如果你看下上图中数组的索引15,它有一个叫做HashMap$Entry的Entry对象。

    3).我们往hashmap放了4个key-value对,但是看上去好像只有1个元素!!!这是因为,如果两个元素有相同的hashcode,它们会  被放在同一个索引上。问题出现了,该怎么放呢?原来它是以链表(LinkedList)的形式来存储的(逻辑上)。因此他们都在hash值为15的位置  上存着了,然后把多个Entry,用next进行链接。


散列表要解决的一个问题就是散列值的冲突问题,通常是两种方法:链表法和开放地址法

  • 链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位;

  • 开放地址法是通过一个探测算法,当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。

java.util.HashMap采用的链表法的方式,链表是单向链表。形成单链表的核心代码如下:

voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){Entryk,v

上面方法的代码很简单,但其中包含了一个设计:系统总是将新添加的 Entry 对象放入 table 数组的 bucketIndex 索引处——如果 bucketIndex 索引处已经有了一个 Entry 对象,那新添加的 Entry 对象指向原有的 Entry 对象(产生一个 Entry 链),如果 bucketIndex 索引处没有 Entry 对象,也就是上面程序代码的 e 变量是 null,也就是新放入的 Entry 对象指向 null,也就是没有产生 Entry 链。

HashMap里面没有出现hash冲突时,没有形成单链表时,hashmap查找元素很快,get()方法能够直接定位到元素,但是出现单链表后,单个bucket 里存储的不是一个 Entry,而是一个 Entry 链,系统只能必须按顺序遍历每个 Entry,直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端(该 Entry 是最早放入该 bucket 中),那系统必须循环到最后才能找到该元素。

当创建 HashMap 时,有一个默认的负载因子(load factor),其默认值为 0.75,这是时间和空间成本上一种折衷:增大负载因子可以减少 Hash 表(就是那个 Entry 数组)所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的的操作(HashMap 的 get() 与 put() 方法都要用到查询);减小负载因子会提高数据查询的性能,但会增加 Hash 表所占用的内存空间。



py大白
9楼 · 2021-01-29 09:29

散列表要解决的一个问题就是散列值的冲突问题,通常是两种方法:链表法和开放地址法。

链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位;

开放地址法是通过一个探测算法,当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。

java.util.HashMap采用的链表法的方式,链表是单向链表。形成单链表的核心代码如下:

voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){Entryk,v

上面方法的代码很简单,但其中包含了一个设计:系统总是将新添加的 Entry 对象放入 table 数组的 bucketIndex 索引处——如果 bucketIndex 索引处已经有了一个 Entry 对象,那新添加的 Entry 对象指向原有的 Entry 对象(产生一个 Entry 链),如果 bucketIndex 索引处没有 Entry 对象,也就是上面程序代码的 e 变量是 null,也就是新放入的 Entry 对象指向 null,也就是没有产生 Entry 链。

HashMap里面没有出现hash冲突时,没有形成单链表时,hashmap查找元素很快,get()方法能够直接定位到元素,但是出现单链表后,单个bucket 里存储的不是一个 Entry,而是一个 Entry 链,系统只能必须按顺序遍历每个 Entry,直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端(该 Entry 是最早放入该 bucket 中),那系统必须循环到最后才能找到该元素。

当创建 HashMap 时,有一个默认的负载因子(load factor),其默认值为 0.75,这是时间和空间成本上一种折衷:增大负载因子可以减少 Hash 表(就是那个 Entry 数组)所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的的操作(HashMap 的 get() 与 put() 方法都要用到查询);减小负载因子会提高数据查询的性能,但会增加 Hash 表所占用的内存空间。


相关问题推荐

  • 回答 156

    对于每一位才开始接触JAVA的新手来说,先不要管算法和数据结构,大多数简单的程序不需要用到算法和数据结构,所以当你真正需要时再去学习。编程一段时间以后,你就会知道在哪些地方用到他们。这时知道算法的名字并了解它们的功能,然后动手去实践。当我们在去...

  • 回答 93

    2个都很好就业,更关键的是要学得到东西

  • 回答 12
    已采纳

    获取Map集合中所有的key可以通过map集合的keySet()方法获取例如:    Map map = new HashMap();    map.put(xx,xx); //存放数据    //.... 省略    Set set = map.keySet();    //可以通过迭代器进行测试    Iterator iter = set.iter...

  • 回答 56
    已采纳

    不同年龄,不同掌握程度,学历,找工作城市,面试能力这是一个多方面影响的结果,如果是平均值的话,全国平均薪资14k左右

  • 回答 38

    具体学多久,根据自己的学习力,自律性、解决问题能力来决定若系统性学习,跟着讲师的节奏走,大概半年左右,有专业的讲师把课程进行规划,尽心系统学习,有问题,讲师会帮忙解决,学习的效率很高,避免了自学中出现各种问题解决不了,而耽误很多时间,可能会...

  • BIO与NIO、AIO的区别2020-05-19 15:59
    回答 4
    已采纳

    IO的方式通常分为几种,同步阻塞的BIO、同步非阻塞的NIO、异步非阻塞的AIO。一、BIO     在JDK1.4出来之前,我们建立网络连接的时候采用BIO模式,需要先在服务端启动一个ServerSocket,然后在客户端启动Socket来对服务端进行通信,默认情况下服务端需要...

  • 回答 23
    已采纳

    (1)idea启动时会有两个快捷方式,安装完后默认生成在桌面的是32位的idea的快捷方式,如果我们使用这个快捷方式运行大项目,一般都会很卡。解决方法是找到idea的安装目录,然后进入bin文件夹,找到名称为idea64的应用程序,右键他生成桌面快捷方式。以后每次...

  • Java方法的命名规则2021-04-06 19:07
    回答 31

    ava是一种区分字母的大小写的语言,所以我们在定义变量名的时候应该注意区分大小写的使用和一些规范,接下来我们简单的来讲讲Java语言中包、类、变量等的命名规范。(一)Package(包)的命名Package的名字应该都是由一个小写单词组成,例如com、xuetang9、compan...

  • 回答 2

    public class Point {    private int x;    private int y;    public int getX() {        return x;    }    public void setX(int x) {        this.x = x;    }    public int getY() {        return y;    } ...

  • 回答 6

    经典版单例模式public class Singleton {        private static Singleton uniqueInstance;//利用一个静态常量来记录singleton类的唯一实例。     private Singleton() {     }     public static  Singleton getInstance()...

  • 回答 3

    哈希表的长度一般是定长的,在存储数据之前我们应该知道我们存储的数据规模是多大,应该尽可能地避免频繁地让哈希表扩容。但是如果设计的太大,那么就会浪费空间,因为我们跟不用不到那么大的空间来存储我们当前的数据规模;如果设计的太小,那么就会很容易发...

  • 回答 14

    1. DOM(Document Object Model)        DOM是用与平台和语言无关的方式表示XML文档的官方W3C标准。DOM是以层次结构组织的节点或信息片断的集合。这个层次结构允许开发人员在树中寻找特定信息。分析该结构通常需要加载整个文档和构造层次结构,然后才...

  • 回答 19

    1)作用不同: throw用于程序员自行产生并抛出异常; throws用于声明在该方法内抛出了异常2) 使用的位置不同: throw位于方法体内部,可以作为单独语句使用; throws必须跟在方法参数列表的后面,不能单独使用。3)内容不同: throw抛出一个异常对象,且只能是...

  • 回答 11

    基本执行过程如下:1)程序首先执行可能发生异常的try语句块。2)如果try语句没有出现异常则执行完后跳至finally语句块执行;3)如果try语句出现异常,则中断执行并根据发生的异常类型跳至相应的catch语句块执行处理。4)catch语句块可以有多个,分别捕获不同类型...

  • 回答 20

    100-199 用于指定客户端应相应的某些动作。 200-299 用于表示请求成功。 300-399 用于已经移动的文件并且常被包含在定位头信息中指定新的地址信息。 400-499 用于指出客户端的错误。 400 语义有误,当前请求无法被服务器理解。 401 当前请求需要用户验证...

  • 回答 16

    异常表示程序运行过程中可能出现的非正常状态,运行时异常表示虚拟机的通常操作中可能遇到的异常,是一种常见运行错误,只要程序设计得没有问题通常就不会发生。受检异常跟程序运行的上下文环境有关,即使程序设计无误,仍然可能因使用的问题而引发。Java编译...

没有解决我的问题,去提问