好好用Java的HashMap及1.8的变化

HashMap有什么好说的?从最开始接触java语言,可能就开始使用了。对于一个稍微钻研过的Java开发来说,心里都非常的明白HashMap内部的实现结构。他就是数组+链表实现的。

最近越来越多的团队都把Java升级到1.8了,但是绝大多数人对Java的理解还都停留在1.6版本。而对于1.7、1.8的理解,也仅仅只是局限于语法这个层面。

本篇我们就来聊聊HashMap在1.6到1.8到底发生了什么变化(1.6和1.7大致相近),以及怎么样更高效的使用HashMap。

先说下1.6时代HashMap的实现

可能很多人如果没有对Java源码深究过的话,不会太知道HashMap到底内部是怎么实现的。或者看过数据结构的书的话,可能也知道HashMap会有哪些种实现方式。这里安利一下我写的算法书——轻松学算法(东强那边好像没货了,去这里看看),里面有介绍到这一数据结构,但是没有介绍1.8中的变化,最近打算面试的可以买来参考下。

在1.6时代,HashMap是由数组+链表的形式存储的,通过key进行hash算法得到一个值,映射到数组中,如果数组上已经有值,那么会建立一个链表来存储。如果链表已经存在,那么会在链表的首位插入这个新增的元素(想想为什么要在首位?)。

所以HashMap在1.6时代,大致的实现方式是下面这张图的样子。

HashMap1.6版本结构
HashMap1.6版本结构

所以如果key经过hash算法映射之后,整个HashMap的key都映射到一个格子上的话,那么这个HashMap就会退化成一个链表。性能就很差了。

这里顺便说下1.6时代,hash算法对key的hashCode进行了两次异或(假设key的hashCode值为h),那么1.6版本的hash算法是下面这样的。

1.8下HashMap产生的变化

1.8的HashMap到底怎么了?他的性能更好了,在这个版本HashMap的存储结构发生了细微的变化,而这个变化,也直接导致了HashMap的性能比以前好了一些。

首先的一个重要的变化,那就是存储结构由以前单纯的数组+链表,变成了数组+链表/红黑树。什么意思呢,就是这个数组上跟着的可能是一个链表,也可能是个红黑树。当冲突节点(也就是链表上的节点)个数达到7个或者7个以上的时候,将会把链表转换为红黑树,然后继续进行存储。这里需要说明一点,就是HashMap中就可能存在有个数组节点后面是链表,有的是红黑树的情况。

有个什么好处呢,在最坏的情况下,冲突节点个数假设为N,那么1.6版本的时间复杂度为O(N),但是在1.8版本中时间复杂度会是O(logN),性能有了提升。

下面看一下1.8版本的HashMap存储结构图(偷个懒省略null了)。

hashmap1.8版本结构
hashmap1.8版本结构

当冲突比较明显的时候,红黑树是要比链表好点。接下来再看看1.8的hash算法是什么样的,同样设h为key的hashCode。

比1.6的简单了好多啊,由于HashMap的key进行hash如果冲突之后,使用红黑树比链表性能更好,所以作者觉得就算冲突了也还好,所以简化了hash算法,只是把高16位异或下来了而已。

再聊下加载因子Load Factor

HashMap中用到了一个扩容因子,他的作用很简单,就是为了防止数组都有元素的时候才扩容,默认扩容因子为0.75,也就是说,默认16个长度的数组,在有13分元素占满数组的时候,就会开始扩容了。如果没有扩容因子,那么到16个数字格子都占满了才扩容,那肯定这时候肯定很多数组元素里面后面有很长的冲突了(链表很长或者红黑树很高)。而且HashMap的扩容,其实要比ArrayList扩容复杂的多,性能也差很多。

假设声明一个HashMap,大概知道数组可能的长度,或者要copy一个HashMap,不能简单的像下面这样写。

因为加载因子的作用,在填充内容的时候很容易还是需要一次扩容的。HashMap里面有一个可以把一个HashMap复制过来的方法,是putAll方法,接收一个Map参数,看下里面的实现,其实他会初始化一个长度,((float)s / loadFactor) + 1.0F,然后转换为int类型,其中s为原Map的size。

最后拓展个IntObjectHashMap

先写个测试代码。

很多时候我们想要用key类型为int的Map,但是常规情况HashMap的key只能是Integer,虽说空间浪费了一点我们也不是很在意,但是这个IntObjectHashMap确实有更多厉害的地方。

通过上面示例代码我们可以看到他可以取第一个元素,可以拿到最大值的元素。其实他的Set也可以获取min()和max(),还可以转换为数组和有序数组。

最后有个内容差点忘了,IntObjectHashMap并不是JDK自带的,但是如果你的项目比较大的话,很容易就已经引用到了这个模块,pom文件看下面,版本号并不重要。

两个内容混起来写总觉得不太好,我又懒了。

本文原创于赵伊凡BLOG转载请注明出处。

©原创文章,转载请注明来源: 赵伊凡's Blog
©本文链接地址: 好好用Java的HashMap及1.8的变化

“好好用Java的HashMap及1.8的变化”的3个回复

发表评论

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