深入研究HashMap

一. HashMap的结构和底层原理

HashMap是我们非常常用的数据结构,由数组和链表组合构成的数据结构。大概如下,数组里面每个地方都存了Key-Value这样的实例,在Java7叫Entry在Java8中叫Node。

深入研究HashMap

深入研究HashMap

因为他本身所有的位置都为null,在put插入的时候会根据key的hash去计算一个index值。就比如我put(”帅丙“,520),我插入了为”帅丙“的元素,这个时候我们会通过哈希函数计算出插入的位置,计算出来index是2那结果如下。

hash(“帅丙”)= 2
深入研究HashMap

深入研究HashMap

我们都知道数组长度是有限的,在有限的长度里面我们使用哈希,哈希本身就存在概率性,就是”帅丙“和”丙帅“我们都去hash有一定的概率会一样,就像上面的情况我再次哈希”丙帅“极端情况也会hash到一个值上,那就形成了链表。

深入研究HashMap

深入研究HashMap

每一个节点都会保存自身的hash、key、value、以及下个节点,我们看看Node的源码。

深入研究HashMap

深入研究HashMap

那么新的Entry节点在插入链表的时候,是怎么插入的?

java8之前是头插法,就是说新来的值会取代原有的值,原有的值就顺推到链表中去,就像上面的例子一样,因为写这个代码的作者认为后来的值被查找的可能性更大一点,提升查找的效率。

但是,在java8之后,都是所用尾部插入了。

那么为啥改为尾部插入呢?

首先我们看下HashMap的扩容机制:

之前提到过了,数组容量是有限的,数据多次插入的,到达一定的数量就会进行扩容,也就是resize。

什么时候resize呢?

有两个因素:

  • Capacity:HashMap当前长度。

  • LoadFactor:负载因子,默认值0.75f。

怎么理解呢,就比如当前的容量大小为100,当你存进第76个的时候,判断发现需要进行resize了,那就进行扩容,但是HashMap的扩容也不是简单的扩大点容量这么简单的。

它是怎么扩容的呢?

分为两步

  • 扩容:创建一个新的Entry空数组,长度是原数组的2倍。

  • ReHash:遍历原Entry数组,把所有的Entry重新Hash到新数组。

    为什么要重新Hash呢,直接复制过去不香么?

是因为长度扩大以后,Hash的规则也随之改变。

Hash的公式---> index = HashCode(Key) & (Length - 1)

原来长度(Length)是8你位运算出来的值是2 ,新的长度是16你位运算出来的值明显不一样了。

说完扩容机制我们言归正传,为啥之前用头插法,java8之后改成尾插了呢?

我先举个例子吧,我们现在往一个容量大小为2的put两个值,负载因子是0.75是不是我们在put第二个的时候就会进行resize?2*0.75 = 1 所以插入第二个就要resize了。现在我们要在容量为2的容器里面用不同线程插入A,B,C,假如我们在resize之前打个短点,那意味着数据都插入了但是还没resize那扩容前可能是这样的。我们可以看到链表的指向A->B->C,

深入研究HashMap

深入研究HashMap

因为resize的赋值方式,也就是使用了单链表的头插入方式,同一位置上新元素总会被放在链表的头部位置,在旧数组中同一条Entry链上的元素,通过重新计算索引位置后,有可能被放到了新数组的不同位置上。就可能出现下面的情况,大家发现问题没有?B的下一个指针指向了A

深入研究HashMap

深入研究HashMap

一旦几个线程都调整完成,就可能出现环形链表

深入研究HashMap

深入研究HashMap

如果这个时候去取值,悲剧就出现了——Infinite Loop。

那1.8的尾插是怎么样的呢?

因为java8之后链表有红黑树的部分,大家可以看到代码已经多了很多if else的逻辑判断了,红黑树的引入巧妙的将原本O(n)的时间复杂度降低到了O(logn)。

使用头插会改变链表的上的顺序,但是如果使用尾插,在扩容时会保持链表元素原本的顺序,就不会出现链表成环的问题了。就是说原本是A->B,在扩容后那个链表还是A->B

深入研究HashMap

深入研究HashMap

Java7在多线程操作HashMap时可能引起死循环,原因是扩容转移后前后链表顺序倒置,在转移过程中修改了原来链表中节点的引用关系。Java8在同样的前提下并不会引起死循环,原因是扩容转移后前后链表顺序不变,保持之前节点的引用关系。

那是不是意味着Java8就可以把HashMap用在多线程中呢?

我认为即使不会出现死循环,但是通过源码看到put/get方法都没有加同步锁,多线程情况最容易出现的就是:无法保证上一秒put的值,下一秒get的时候还是原值,所以线程安全还是无法保证。

HashMap的默认初始化长度是多少?

16

为什么是16

在JDK1.8的 236 行有1<<4就是16,为啥用位运算呢?直接写16不好么?

深入研究HashMap

深入研究HashMap

我们在创建HashMap的时候,阿里巴巴规范插件会提醒我们最好赋初值,而且最好是2的幂。

深入研究HashMap

深入研究HashMap

这样是为了位运算的方便,位与运算比算数计算的效率高了很多,之所以选择16,是为了服务将Key映射到index的算法。前面说了所有的key我们都会拿到他的hash,但是我们怎么尽可能的得到一个均匀分布的hash呢?当然通过Key的HashCode值去做位运算。。。。。。。此处省略详情百度hash算法。直接说结论:为了均匀分布。

为啥我们重写equals方法的时候需要重写hashCode方法呢?

因为在java中,所有的对象都是继承于Object类。Ojbect类中有两个方法equals、hashCode,这两个方法都是用来比较两个对象是否相等的。

在未重写equals方法我们是继承了object的equals方法,那里的 equals是比较两个对象的内存地址,显然我们new了2个对象内存地址肯定不一样

  • 对于值对象,==比较的是两个对象的值

  • 对于引用对象,比较的是两个对象的地址

大家是否还记得我说的HashMap是通过key的hashCode去寻找index的,那index一样就形成链表了,也就是说”帅丙“和”丙帅“的index都可能是2,在一个链表上的。我们去get的时候,他就是根据key去hash然后计算出index,找到了2,那我怎么找到具体的”帅丙“还是”丙帅“呢?

equals!是的,所以如果我们对equals方法进行了重写,建议一定要对hashCode方法重写,以保证相同的对象返回相同的hash值,不同的对象返回不同的hash值。不然一个链表的对象,你哪里知道你要找的是哪个,到时候发现hashCode都一样,这不是完犊子嘛。

二 .HashMap常见面试题

HashMap的底层数据结构?

HashMap的存取原理?

Java7和Java8的区别?

为啥会线程不安全?

有什么线程安全的类代替么?

默认初始化大小是多少?为啥是这么多?为啥大小都是2的幂?

HashMap的扩容方式?负载因子是多少?为什是这么多?

HashMap的主要参数都有哪些?

HashMap是怎么处理hash碰撞的?

hash的计算规则?

上一篇:【小工具系列】Python + OpenCV 图片序列转换成视频


下一篇:php-保存从函数imagecopy创建的图像