欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HashMap原理分析

程序员文章站 2022-05-25 21:16:22
...

注:文末有福利!

一、HashMap的原理

众所周知,HashMap是用来存储Key-Value键值对的一种集合,这个键值对也叫做Entry,而每个Entry都是存储在数组当中,因此这个数组就是HashMap的主干。
HashMap数组中的每一个元素的初始值都是NULL

HashMap原理分析

1.Put方法的实现原理

HaspMap的一种重要的方法是put()方法,当我们调用put()方法时,比如hashMap.put(“Java”,0),此时要插入一个Key值为“Java”的元素,这时首先需要一个Hash函数来确定这个Entry的插入位置,设为index,即 index = hash(“Java”),假设求出的index值为2,那么这个Entry就会插入到数组索引为2的位置。

HashMap原理分析
但是HaspMap的长度肯定是有限的,当插入的Entry越来越多时,不同的Key值通过哈希函数算出来的index值肯定会有冲突,此时就可以利用链表来解决。
其实HaspMap数组的每一个元素不止是一个Entry对象,也是一个链表的头节点,每一个Entry对象通过Next指针指向下一个Entry对象,这样,当新的Entry的hash值与之前的存在冲突时,只需要插入到对应点链表即可。
HashMap原理分析
需要注意的是,新来的Entry节点采用的是“头插法”,而不是直接插入在链表的尾部,这是因为HashMap的发明者认为,新插入的节点被查找的可能性更大。

2.Get方法的实现原理

get()方法用来根据Key值来查找对应点Value,当调用get()方法时,比如hashMap.get(“apple”),这时同样要对Key值做一次Hash映射,算出其对应的index值,即index = hash(“apple”)。
前面说到的可能存在Hash冲突,同一个位置可能存在多个Entry,这时就要从对应链表的头节点开始,一个个向下查找,直到找到对应的
Key值,这样就获得到了所要查找的键值对。
例如假设我们要找的Key值是”apple”:

HashMap原理分析

第一步,算出Key值“apple”的hash值,假设为2。
第二步,在数组中查找索引为2的位置,此时找到头节点为Entry6,Entry6的Key值是banana,不是我们要找的值。
第三步,查找Entry6的Next节点,这里为Entry1,它的Key值为apple,是我们要查找的值,这样就找到了对应的键值对,结束。

二、HashMap的深入思考

上面所说的就是HashMap的基本原理,可以总结出HashMap的3个要素为:hash函数、数组、链表,如下图:
HashMap原理分析

接下来对于HaspMap还有很多深入的问题,比如:
1.HashMap默认的初始长度是多少?为什么这么规定?
2.高并发情况下,HashMap会出现死锁吗?
3.Java8中,HashMap有怎样的优化?
下面开始说明这几个问题:

1.HashMap的长度

1.HaspMap的默认初始长度是16,并且每次扩展长度或者手动初始化时,长度必须是2的次幂。之所以是16,是为了服务于从Key值映射到index的hash算法。前面说到了,从Key值映射到数组中所对应的位置需要用到一个hash函数:index = hash(“Java”);

那么为了实现一个尽量分布均匀的hash函数,利用的是Key值的HashCode来做某种运算。因此问题来了,如何进行计算,才能让这个hash函数尽量分布均匀呢?

一种简单的方法是将Key值的HashCode值与HashMap的长度进行取模运算,即 index = HashCode(Key) % hashMap.length,但是,但是!这种取模方式运算固然简单,然而它的效率是很低的, 而且,如果使用了取模%, 那么HashMap在容量变为2倍时, 需要再次rehash确定每个链表元素的位置,浪费了性能。
因此为了实现高效的hash函数算法,HashMap的发明者采用了位运算的方式。那么如何进行位运算呢?可以按照下面的公式:

index = HashCode(Key) & (hashMap.length - 1);

接下来我们以Key值为“apple”的例子来演示这个过程:

  1. 计算“apple”的hashcode,结果为十进制的3029737,二进制的101110001110101110 1001。

  2. HashMap默认初始长度是16,计算hashMap.Length-1的结果为十进制的15,二进制的1111。

  3. 把以上两个结果做 与运算,101110001110101110 1001 & 1111 = 1001,十进制是9,所以 index=9。

可以看出来,hash算法得到的index值完全取决与Key的HashCode的最后几位。这样做不但效果上等同于取模运算,而且大大提高了效率。

那么回到最初的问题,初始长度为什么是16或者2的次幂?如果不是会怎么样?

我们假设HaspMap的初始长度为10,重复前面的运算步骤:
HashMap原理分析


单独看这个结果,表面上并没有问题。我们再来尝试一个新的HashCode 101110001110101110 1011 :
HashMap原理分析


然后我们再换一个HashCode 101110001110101110 1111 试试 :
HashMap原理分析

这样我们可以看到,虽然HashCode的倒数第二第三位从0变成了1,但是运算的结果都是1001。也就是说,当HashMap长度为10的时候,有些index结果的出现几率会更大,而有些index结果永远不会出现(比如0111)!

所以这样显然不符合Hash算法均匀分布的原则。

而长度是16或者其他2的次幂,Length - 1的值的所有二进制位全为1(如15的二进制是1111,31的二进制为11111),这种情况下,index的结果就等同于HashCode后几位的值。只要输入的HashCode本身分布均匀,Hash算法的结果就是均匀的。这也是HashMap设计的玄妙之处。

2.HashMap的死锁

我们知道HashMap是非线程安全的,那么原因是什么呢?

由于HashMap的容量是有限的,如果HashMap中的数组的容量很小,假如只有2个,那么如果要放进10个keys的话,碰撞就会非常频繁,此时一个O(1)的查找算法,就变成了链表遍历,性能变成了O(n),这是Hash表的缺陷。

为了解决这个问题,HashMap设计了一个阈值,其值为容量的0.75,当HashMap所用容量超过了阈值后,就会自动扩充其容量。

在多线程的情况下,当重新调整HashMap大小的时候,就会存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历。如果条件竞争发生了,那么就会产生死循环了。

具体发生死锁的过程可以参考这篇文章:疫苗:JAVA HASHMAP的死循环

3.HashMap的优化

关于Java8中对于HashMap的优化,可以参考下面两篇文章:
Java 8系列之重新认识HashMap

HashMap源码分析(JDK1.8)

最后,给大家推荐一个良心公众号【IT资源社】:

本公众号致力于免费分享全网最优秀的视频资源,学习资料,面试经验等,前端,PHP,JAVA,算法,Python,大数据等等,你想要的这都有

IT资源社-QQ交流群:601357554

微信搜索公众号:ITziyuanshe 或者扫描下方二维码直接关注,

HashMap原理分析

里面基本什么资料都有,基础到进阶到项目实战,如果觉得不够还可以加群跟群主要,最重要的是全部免费!


原文链接: https://blog.csdn.net/VampireKalus/article/details/79798372
相关标签: HashMap原理