456lives.com - 舒适慢生活

专享优惠券-淘宝天猫最热门优惠券清单 阿里旅行-前往世界的尽头 【聚名品】奢品潮流风向标 省钱优惠圈 精品女装 靓丽全场
文字广告45元/月 聚划算专享优惠 文字广告45元/月 文字广告45元/月 文字广告45元/月
京东居家生活 日用精品 抽免单+抽红包,福利抽不停 天猫超市-今日疯抢 多款好货任你抢 全球精选-享品质生活 广告合作客服QQ:253482037

Java面试必问之HashMap原理分析

时间:2018-04-08 08:33:36 | 作者:本站编辑 | 来源:网络 | 查看:595 | 评论:0

摘要: HashMap是用来存储Key-Value键值对的一种集合,这个键值对也叫做Entry,而每个Entry都是存储在数组当中,因此这个数组就是HashMap的主干。而HashMap也经常出现在各大面试题中,今天我们就来分析一下HashMap的原理。

众所周知,HashMap是用来存储Key-Value键值对的一种集合,这个键值对也叫做Entry,而每个Entry都是存储在数组当中,因此这个数组就是HashMap的主干。在Java面试题中,HashMap也是必问的一道考题,今天慢生活的小编就和在家一起分析分析HashMap的原理。


HashMap的原理


HashMap数组中的每一个元素的初始值都是NULL,如图:

2.png


1.Put方法的实现原理


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

3.png


但是HaspMap的长度肯定是有限的,当插入的Entry越来越多时,不同的Key值通过哈希函数算出来的index值肯定会有冲突,此时就可以利用链表来解决。


其实HaspMap数组的每一个元素不止是一个Entry对象,也是一个链表的头节点,每一个Entry对象通过Next指针指向下一个Entry对象,这样,当新的Entry的hash值与之前的存在冲突时,只需要插入到对应点链表即可。

4.png


需要注意的是,新来的Entry节点采用的是“头插法”,而不是直接插入在链表的尾部,这是因为HashMap的发明者认为,新插入的节点被查找的可能性更大。


2.Get方法的实现原理


get()方法用来根据Key值来查找对应点Value,当调用get()方法时,比如hashMap.get("apple"),这时同样要对Key值做一次Hash映射,算出其对应的index值,即index = hash("apple")。


前面说到的可能存在Hash冲突,同一个位置可能存在多个Entry,这时就要从对应链表的头节点开始,一个个向下查找,直到找到对应的Key值,这样就获得到了所要查找的键值对。例如假设我们要找的Key值是"apple":

5.png


第一步,算出Key值“apple”的hash值,假设为2。

第二步,在数组中查找索引为2的位置,此时找到头节点为Entry6,Entry6的Key值是banana,不是我们要找的值。

第三步,查找Entry6的Next节点,这里为Entry1,它的Key值为apple,是我们要查找的值,这样就找到了对应的键值对,结束。


HashMap的深入思考


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

6.png


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


1.HashMap的长度


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”的例子来演示这个过程:


计算“apple”的hashcode,结果为十进制的3029737,二进制的101110001110101110 1001。HashMap默认初始长度是16,计算hashMap.Length-1的结果为十进制的15,二进制的1111。


把以上两个结果做 与运算,101110001110101110 1001 & 1111 = 1001,十进制是9,所以 index=9。可以看出来,hash算法得到的index值完全取决与Key的HashCode的最后几位。这样做不但效果上等同于取模运算,而且大大提高了效率。那么回到最初的问题,初始长度为什么是16或者2的次幂?如果不是会怎么样?我们假设HaspMap的初始长度为10,重复前面的运算步骤:

7.png


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

8.png


然后我们再换一个HashCode 101110001110101110 1111 试试 :

9.png


这样我们可以看到,虽然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并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历。如果条件竞争发生了,那么就会产生死循环了。

  • 0
    惊讶
  • 0
    欠揍
  • 0
    支持
  • 0
    很棒
  • 0
    愤怒
  • 0
    搞笑
  • 0
    恶心
  • 0
    不解
此篇文章已有0人参与评论

请发表评论

热门评论

精选资讯


免责申明:本站部份内容来源自互联网,如果侵害了您的合法权益,请您及时与我们联系,我们会在第一时间给予改正和删除。

Powered by 舒适慢生活 Copyright © 2013-2023, All Rights Reserved京ICP备13024987号-1京公网安备11010602030047号京公网安备11010602030047号

工作时间:7x24小时联系QQ:253482037服务热线:188****4459活动洽谈:188****4459联系邮箱:253482037@qq.com