0


HashMap常用方法及底层原理

HashMap

HashMap介绍

数据结构是一门组织联系数据的学科,其中一种数据结构就是 HashMap,它是一种以键值对的形式存储数据的数据结构,时间复杂度可以达到 O(1)


HashMap常用方法

HashMap 的方法有很多,这里介绍几个常用的:

以下代码均使用该实例:

Map<T, T> map =newHashMap<>();
  1. put()方法 用于将键值对存入 map 中
map.put("zhangsan",20);
map.put("lisi",22);

注意: (1)map 中不允许存在相同的 K 值,所以当使用 put 函数放入键值对时,如果此时 map 中已经有了当前 K 值,则会将原有 K 所对应的 V 值覆盖。
(2)HashMap 中的 put()方法允许使用 null 作为 K

  1. get()方法 用于获取 map 中已存放的键值对中指定 K 值对应的 V 值。
map.get("zhangsan");
map.get("zhangsan2");

此时的输出结果分别对应 20,null

  1. remove()方法 用于删除 map 中存放的键值对
map.remove("zhangsan");

此时 map 中只剩下 <“lisi”, 20> 这组键值对

  1. keySet()方法 用于获取 map 中所有不重复 K 值集合,返回一个 Set
Set set = map.keySet();

set 中的所有元素的是不重复的。

  1. EntrySet()方法 用于获取 map 中所有键值对的映射关系
Set<Map.Entry<String, Integer>> setEntry = map.EntrySet();

其 setEntry 中存放的就是若干个 Map.Entry<String, Integer> 类型的键值对


哈希表

HashMap 的底层实现就是一张哈希表,或者叫哈希桶(HashBuck)

哈希表的存取都通过哈希函数来进行映射,得到相应的映射关系,找到对应的哈希地址来进行存储,从而其时间复杂度达到O(1)

哈希表的存取

举个栗子来描述哈希表的存取

假设 K 值为 Integer 类型的

哈希函数:K % array.length
那么对应的存取将都由这个哈希函数进行映射

比如以下有 4 个数据:0, 4, 18, 22
以及一个 array 数组(大小为 10)

哈希表
将这四个数据分别代入哈希函数求得哈希地址为:0,4,8,2

将其对应存放进 array 数组里

哈希表
如果要取元素,也同样通过哈希函数进行映射拿到对应哈希地址取出元素。

但是这样的存取,就必然会存在一个问题,那就是 “哈希冲突”

哈希冲突

当哈希函数确定之后,如果存入大量的数据,都通过这个哈希函数进行映射,那必然会出现哈希地址重复的情况,这就是哈希冲突。
如果一味的不管哈希冲突,就会导致新的数据将旧的数据覆盖,为了解决这个问题,可以采用增加数组长度的方式,但是因为数据个数一定是远远大于数组长度的,也就导致哈希冲突是无法避免的,
所以哈希表采用的方法是开链法

所谓开链法,就是将所有的数据通过数组 + 链表的形式进行组织

每一个链表节点必须有 3 个域,分别是 next 域,K 域,V 域
而数组中存放的每个元素是引用类型,存放链表第一个节点的地址。

如下图,将 4 个键值对存入哈希表

<0, “a”> <4, “c”> <18, “d”> <22, “b”>

哈希表

使用开链法的方式进行存储将是以上形式,这样可以有效的避免哈希冲突带来的麻烦。

比如现在又要插入几个键值对:<10,“e”>,<28,“f”>

结果如下:

注:哈希表中的链表采用的是头插法,我这里为了方便画图采用了尾插法,请见谅~
哈希表
以上就是哈希桶进行存取数据的方式,但是现在又有了新的问题,哈希表的存取需要让时间复杂度达到 O(1),如果链表的长度过长,那么就会导致存取的时间复杂度达不到 O(1)。

这里就提出了一个概念,叫做负载因子

负载因子

在哈希表中,数据的个数是无法确定已经更改的,为了避免链表的长度过长而降低时间复杂度,只能通过增加数组长度的方式来解决。

而负载因子 = 数据的个数 / 数组的长度

我们知道,数据的个数是不可控的,而当我们增加数组的长度,就可以降低负载因子,从而负载因子就可以作为我们评判数组是否扩容的标准。

在源码中,默认的负载因子大小为 0.75,也就意味着,当存入的数据太多,导致负载因子超过 0.75 时,数组就会进行扩容。

通过负载因子的控制,链表的长度就不会很长,可以控制在常数范围内


扩容机制

在哈希表中,除了给定了默认的负载因子大小为 0.75,还给定了一个 1 << 30 作为哈希表的最大默认容量,每一次存储数据之后会计算对应的负载因子是否超过了 0.75,如果超过了 0.75,将会判断当前容量的两倍有没有超过 1 << 30,如果没有超过,则进行二倍扩容,如果超过了,则将 1 << 30 作为新的容量大小。

在每一次数组进行扩容之后,原来存放的数据必须进行重新哈希,因为此时的数组长度已经发生了变化,这样就能够达到我们想要缩短链表长度的目的,如下:

哈希表
这样即可降低哈希表中链表的长度,达到提高效率的目的。


其他机制

由上文已经了解到了几个简单的机制,譬如默认负载因子大小为 0.75,最大容量为1 << 30,超过默认负载因子将出发扩容机制等等。。

接下来还有几个比较重要的机制。

哈希表容量问题

首先,如果在实例化时不指定哈希表的容量,则哈希表的默认容量为 16,但并非是构造出 map 对象的那一时刻就给定容量,在 JDK 8 中,实例化 map 之后其实他的容量依然是为 0 的,如果我们不指定 map 大小,那么将在第一次 put()元素时为其开辟大小为 16 的容量。
如果指定了哈希表的容量,如:

Map<String, Integer> map =newHashMap<>(20);

则同理,在实例化之后,并不分配容量,而是在第一次 put()元素时为其分配大小,但值得一说的是,这里给它分配的容量大小并不是 20,而是 32,具体原因看完第二点便可知道。

哈希函数问题
哈希表的容量大小必须是 2 的次幂,其原因是为了提高哈希表的效率,降低哈希冲突。
在源码中,计算并不是使用 hash(K)% array.length 来进行计算的,取而代之的是 hash(K)&(array.length - 1)。
因为按位与运算比取模运算的效率要高很多,而 & 运算存在一个问题,hash(K)的值可能为 1 也可能为 0,而如果(array.length - 1)的值也可奇可偶的话,那么运算出来是偶数的概率则会特别大,为了解决这个问题,就采用了让 array.length - 1,并且保证数组长度是偶数的方法来确保 array.length - 1 是奇数,这样计算的结果奇偶概率分散,即可大大降低哈希冲突的概率。

树化问题

就算哈希表有了负载因子,有了开链法,有了扩容机制,但还是架不住数据量的庞大,这就导致链表长度随时会过长,为了不让这种现象影响哈希表的性能,在哈希桶中会在每一次 put()元素之后进行判断,如果当前链表长度超过 8 则会将链表转换成一种查找效率极高的数据结构 - - 红黑树(这里不介绍),以此来保证其时间复杂度达到O(1)。

当变成红黑树之后,如果哈希表中使用 remove()方法删除元素,导致链表长度小于 6,则又会将红黑树进行链化,变成原来的链表。

hashcode 问题

上文讲的例子中,K 的值是 Integer 类型的,但我们在使用 HashMap 的时候极有可能用到的 K 值是 String 类型或者其他类型的数据,那该如何进行计算呢?

答案就是重写 hashcode()方法,使用 hashcode()方法可以将不是整型的数据转化为一个合法的整型数据,从而方便进行哈希映射。

那么,就又引出了一个新的问题,举一个栗子,如果要存放用户对应的身份证信息,那就需要不管是几个实例的 map,只要存放的 K 值相同,查找到的身份证信息就应该相同,但是 hashcode()方法就出问题了:

classPerson{public String name;publicPerson(String name){this.name = name;}@OverridepublicinthashCode(){return Object.hash(name);}}
Map<String, Integer> map =newHashMap<>();
map.put("zhangsan",123);

Person person1 =newPerson("zhangsan");
Person person2 =newPerson("zhangsan");

person1.hashcode();
person2.hashcode();

此时的 person1 和 person2 的 hash 值将会不相等,因为这是针对两个不同对象的 hashcode,所以对应的值会不相等,但他们的 name 都是 “zhangsan”,所以我们希望他们拿到的哈希值是一样的。

这就需要 “hashcode and equals” 来解决这个问题了。

我们只需要在 Person 类中同时重写 hashcode()方法和 equals()方法。

classPerson{public String name;publicPerson(String name){this.name = name;}@Overridepublicbooleanequals(Object o){if(this== o)returntrue;if(o == null ||getClass()!= o.getClass())returnfalse;
        Person person =(Person) o;return Object.equals(name, person.name);}@OverridepublicinthashCode(){return Object.hash(name);}@Overridepublic String toString(){return"Person{"+"name='"+ name +'\''+'}'";}}

Person person1 =newPerson("123");
Person person2 =newPerson("123");
        
System.out.println(person1.hashcode());
System.out.println(person2.hashcode());

此时拿到的哈希值就会是相等的了,重写的 equals()方法会帮助我们判断对象是否相等,如果相等,就会返回 TRUE,在 hashcode()时返回一个相同的值。

相当于如果我们在查字典,要查 “二” 这个字
equals()方法就帮我们找到了 E 所对应的位置
而hashcode()方法则帮我们找到 “er”

所以,在使用哈希表存放自定义类型数据类型的时候,一定要重写 hashcode()方法和 equals()方法。

总结

以上就是本文的全部内容,首先是 hashmap 的常用方法:put,get,keySet等等。
然后是哈希表的底层是一个哈希桶,使用链表 + 数组的形式进行组织。

接下来是哈希表中的一些机制,比如何时开辟内存,超过负载因子进行二倍扩容并重新哈希,链表长度超过阈值树化,哈希桶容量必须是 2 的幂次等等。

希望本文可以给大家带来帮助~ 感谢~~


本文转载自: https://blog.csdn.net/Aaron_skr/article/details/126292216
版权归原作者 万羽西 所有, 如有侵权,请联系我们删除。

“HashMap常用方法及底层原理”的评论:

还没有评论