java 对java8中HashMap的简单分析

最近在看HashMap的实现。发现JDK1.7和JDK1.8下的HashMap区别很大,所以参考一篇写得非常好的文章,说一下我个人浅显的理解。

本文只是简单的分析,以后还要写一篇文章进行详细解读。

参考:http://www.importnew.com/20386.html

 

 

一、为什么使用HashMap

一提起为什么要用某种“新东西”,我们首先应该想到:肯定是某种“旧东西”不够好,不足以解决问题,所以必须要用新的解决方案。

HashMap可以用来做数据的存储。但是,我们不是已经有ArrayList和LinkedList两种集合了吗?是不是这两种集合有什么缺陷?

缺陷就在两种集合的实现原理上,分别为数组和链表:

(1)数组

ArrayList依靠数组实现。数组存储区间是连续的,占用内存严重,空间复杂度很大。但是数组的二分查找时间复杂度小,为O(1)。数组的特点是:寻址容易,插入和删除困难。

(2)链表

LinkedList依靠双向链表实现。链表存储区间离散,占用内存比较宽松,空间复杂度很小,但时间复杂度很大,达O(N)。链表的特点是:寻址困难,插入和删除容易。

既然两种方法各有优缺点,那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?

答案是肯定的,这种数据结构就是哈希表。哈希表适合查找数据,同时不占用太多的内容空间。

HashMap的实现原理就是哈希表,它综合了ArrayList和LinkedList两者的优点。

二、简单分析

(1)HashMap的结构

哈希表有两种实现方式,一种开放地址方式,另一种是冲突链表方式(也称为拉链法)。Java中的HashMap采用的是冲突链表方式。

查看HashMap源码,可以发现这样一个table数组:

这个table数组就是上文所说的HashMap中数组结构的实现。数组中存放的是键值对Node<K,V>:

这里的next变量指向下一个键值对。通过多个Node键值对环环相接,就形成了链表,也就是上文所说的HashMap中链表结构的实现。

综上所述,可以画出HashMap的结构示意图:

5

(2)如何储存元素

1.寻址

元素要储存在table中的什么位置?

查看put方法源码:

可以发现通过hash方法对key做了处理,并且在putVal方法中进行最后一步计算寻址:

整个寻址的计算过程为:

6

假设一个键值对为Node<1,”xie”>,通过以上的方法计算得到位置为5,那么这个Node就会储存在table数组中下标为5的位置(即bucket的位置):

6

在这里,最难理解的是这个步骤:

为什么要把hash值右移16位,再与自身进行“^”(异或)操作?

参考:https://www.zhihu.com/question/20733617

这种做法被称为“扰乱”。右位移16位,正好是32bit的一半,自己的高半区和低半区做异或操作,就是为了混合hash码的高位和低位,从而加大低位的随机性。而且混合后的低位掺杂了高位的部分特征,这样高位的信息也被变相地保留了下来。

“扰乱”的结果,就是计算出更多不同的bucket位置,让元素的位置更加离散,让HashMap的效率更高。

在jdk 1.8中的“扰乱”已经是优化后的结果。我们可以看看Jdk 1.7中的“扰乱函数”的源码:

为了让元素更离散,可谓是大费周章。

2.key为null的情况

我们总是拿HashMap和HashTable相比:HashMap可以使用null作为key,HashTable不行。那么问题来了:如果key为null,那就无法计算其hash,HashMap怎么确定bucket的位置?

不用担心这个问题,看看hash方法:

如果key为null,不会进行hash计算,直接确定bucket位于数组下标为0的位置。

HashTable的hash方法不够机智,所以不能使用null作为key。

3.如果hash相同并且当前位置已经存在元素,则需要延长链表

如果需要储存一个key为100的Node<100,”pjl”>,通过hash方法计算得到位置为5,那么这个Node<100,”pjl”>要如何进行储存?

因为key相同,所以计算得出的hash也相同。因为hash相同,所以计算的(n – 1) & hash得出的数组中的位置也相同(此位置一般称之为bucket,意为hash桶)。所以Node<100,”pjl”>在插入时会和Node<1,”xie”>发生碰撞,形成链表结构。

看JDK1.7的HashMap源码,插入时采用的是“头插法”:

但是在JDK1.8中,发生了显著变化:

很明显,新的方法会把新元素插入到当前链表的尾部,所以已经不是“头插法”了,而是“尾插法”。

在这里,Node<1,”xie”>的指针next会指向新的键值对Node<100,”pjl”>,从而形成链表结构:

6

4.相同key的覆盖

如果需要储存一个元素Node<1,”xie4ever”>,但是之前已经存在一个Node<1,”xie”>了,如何进行储存?

查看put方法源码:

首先,因为key同为1,所以计算的hash值肯定和Node<1,”xie”>相同。因为hash相同,所以两个元素通过(n – 1) & hash计算得出的bucket也相同,肯定能找到Node<1,”xie”>所在的链表的位置。之后遍历链表,如果找到hash相同并且key也相同的元素,就直接更换value,并且返回原value的值。

这里存在一个问题:我们需要通过(n – 1) & hash计算bucket的位置,而n是当前数组的大小。那么问题来了,如果数组容量不足,HashMap会进行resize,数组的大小会改变,n的值会改变。即使hash的值一致,只要n改变了,计算出bucket的位置肯定不一样了,那岂不是起不到覆盖的效果?

事实上,完全不用担心会存在这样的问题。resize不像ArrayList中的grow(ArrayList中的扩容只是创建一个更大的数组,然后复制原内容),不仅是数组的大小改变了,原来所有元素都会重新改变位置,保证(n – 1) & hash计算的位置相同,确保相同key值的元素可以覆盖。

验证一下:

结果为xie,与预测的结果相符。

5.分析put方法的源码

上面的分析比较简单,真正的put方法非常复杂:

HashMap同时使用了数组和链表,这就意味着:ArrayList和LinkedList会遇到的问题,HashMap也一样会遇到。因此,put方法必须做更多的优化处理,才会显得很复杂。

既然用到了链表,我们可以想到:如果数据量很大,hash相同的键值对就可能很多,就会导致链表边长,降低查询的效率,遇到同LinkedList一样的问题。

所以在第五步,如果遍历链表超过一定次数(即链表超长),则使用红黑树进行处理。这里涉及红黑树的概念,不再深入研究。

既然用到了数组,我们可以想到:HashMap中table是一个数组,数组有其默认长度。如果数据量很大,那么数组的容量就可能不够,要随时准备扩容。

所以在第六步,可以通过resize方法进行数组的扩容。这个方法实现得非常巧妙,可以参考:

java 对HashMap扩容的简单分析

(3)如何获取元素

1.分析get方法的源码

感觉获取比储存要简单很多。查看源码:

get方法调用了getNode方法。如果不存在节点,直接返回null。

如果在链表的第一个节点没有找到想要的键值对,就要遍历这个链表。

2.更快地找到元素(查询的优化)

从之前的经验来看,数组查询明显比链表查询要快,所以在一般情况下,方案1要优于方案2:

6

为了优化get方法的速度,有两种方法:

第一种方法在上文已经介绍了。如果链表超长,就转为红黑树结构,从而避免链表过长影响查询效率。

第二种方法更强调优化HashMap的结构。如果HashMap里面的数据能够尽量分布均匀,使得数组的每个位置上的键值对数量只有一个。当我们用hash得到bucket的位置时,马上就可以得知对应位置的键值对是否我们想要的,不再需要遍历链表,起到优化的效果。

如果想用第二种方法优化查询,就会遇到这样的问题:如果table数组很大,即使使用较差的hash算法也会导致元素比较分散。如果数组很小,即使使用再好的hash算法也会导致较多碰撞(链表变长)。数组的大小非常影响优化的效果。

所以,我们应该具体情况具体分析,通过优秀的hash算法和扩容算法配合,保证数据均匀分布,尽量减少hash碰撞。

说起来倒是挺简单的,Java 8中的实现非常巧妙,值得我们深入研究。

三、总结

对比了一下JDK1.7和1.8的源码,不得不感叹HashMap的变化之大。HashMap竟然能做这么多优化,是我始料未及的。由此看来,应该学好数据结构,方能在底层原理学习中更进一步。

发表评论

电子邮件地址不会被公开。 必填项已用*标注