JDK8中HashMap的工作原理剖析

在Java语言里,HashMap无疑是使用频率非常高的一个类,了解它的内部实现将有助于更好的使用它。

在jdk8中的HashMap是由三种数据结构组成:数组 + ( 链表 or 红黑树 )

图示如下:

而在jdk8之前还只是数组+链表两种数据结构,在这里简单提下数组和链表的区别:

数组

优点:物理地址连续+按下标随机访问效率高O(1)

缺点:插入,删除效率低,

链表

优点:存储地址不连续,可灵活的扩展自己的长度,插入,删除效率高

缺点:访问效率低O(n)

而哈希表(Hash类数据结构)正是结合了两者的优点,而衍生出来的的一种高效的数据存储结构,本质上是采用空间换时间的方式,提高了读写的效率。

HashMap的继承结构如下:

这里我们能发现HashMap中K,V都是泛型的,所以可以支持任何类型作为key或者value,但实际开发中用的最多的都是以String类型的字符串作为key。

在这里泛型Key的hashCode和equals方法非常重要,因为它们会影响HashMap存储的数据分布和读写是否正确

上面说过HashMap可以看成是一个大的数组,然后每个数组元素的类型是Node类型,源码里定义如下:

注意Node类还有两个子类:TreeNode和Entry

上图中的链表就是Node类,而红黑树正是TreeNode类

接着我们来看下HashMap的一些成员变量:

成员变量主要两部分组成,一部分是处理化时候的常量,一部分是变量会在运行时改变,这里还需要注意的是HashMap本身不是线程安全的,所以尽量避免在多线程环境下使用,如果非要使用,就用线程安全的Map,如下:

此外,HashMap还有几个构造方法:

(1)第一个是默认的构造方法,我们看到只对影响扩容负载因子做了初始化,默认是0.75

(2)第二个和第四个其实是一个方法逻辑,可以传入指定的table数组的大小,负载因子用默认的。

(3)第三个可以传入一个Map集合直接赋值给该map,里面用了putMapEntries方法,这个方法可以理解为迭代传入的Map然后将数据赋值给new的Map

(4)第四个是同时指定初始化table数组的大小和负载因子,中间有一些逻辑判断,这里需要提下tableSizeFor这个方法:

源码如下:

这个方法,保证指定的设置的table数组的长度必须是2的n次方,比如你初始化传入的是5,但是实际运行后你会发现table数组的长度是8,这是因为2的n次方,对于数组的扩容和重新赋值有比较大的好处,所以如果你传入的不是2的n次方,那么经过这个方法出来的值一般都是大于你传入的参数最接近的2的n次方。

下面我们看下HashMap是如何存数据的?

源码中的put方法如下:

这里我们看到put方法里面调用了hash方法,来得到该key的hashCode,那么我们来看下其内部是如何实现的:

这里能看到hash方法并不是直接取的hashCode值,而是用hashCode()的高16位异或低16位实现的,这么做可以保证高低bit位都能参与到Hash的计算中,一句话就是为了减少hash冲突的几率。

然后在putVal方法中,实现数据的插入操作,注意数组的下标的计算方式是:

等价于使用转化后hash值对数组长度取模

但是位运算比模运算效率更高

在putVal插入数据的方法中,第一次会调用扩容方法,此外插入时还会判断该节点是链表还是红黑树,他们分别对应不同的赋值方法,并且如果单个bucket的节点数量大于8,还会将链表转化为红黑树,在插入完成后还会继续判断下一次是否需要扩容。

这里重点介绍下扩容方法:

注意,扩容后的table数组的长度,一定是2的n次方。

最后我们来看下get方法:

可以看到get方法也同样调用了hash方法获取hashCode,接着调用了getNode方法:

HashMap读取的效率:

(1)如果在第一个节点命中,那就是O(1)

(2)如果在红黑树中查询,那就是O(logn)

(3)如果是在链表中查询,那就是O(n)

在这里,我们就会发现红黑树的结构的引入,其实是为了提升检索效率。

注意上面查询过程中还有一个小细节,就是判断key是否null,因为在HashMap中其key和value 都可以允许为null值,有时候你get一个null值出来,可能会有两种情况,那么value就是null, 要么是因为你的key传入的是null,而刚好这个null这个key,对应的value也是null。

演示的代码如下:

总结:

本文对JDK8中的HashMap的工作原理做了一个剖析,并介绍了一些核心的方法和注意事项,通过了解它的内部运行机制,以帮助我们更加合理的在实际开发中使用。

参考文章:

https://www.jianshu.com/p/aa017a3ddc40

https://www.geeksforgeeks.org/internal-working-of-hashmap-java/

https://www.cdn.geeksforgeeks.org/java-util-hashmap-in-java/

https://www.javacodegeeks.com/2017/11/java-hashmap-detail-explanation.html

http://lingmeng.github.io/archives/

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20180129B1CRJ800?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券