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时代，大致的实现方式是下面这张图的样子。
所以如果key经过hash算法映射之后，整个HashMap的key都映射到一个格子上的话，那么这个HashMap就会退化成一个链表。性能就很差了。
这里顺便说下1.6时代，hash算法对key的hashCode进行了两次异或（假设key的hashCode值为h），那么1.6版本的hash算法是下面这样的。
|
1 2 |
h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); |
1.8下HashMap产生的变化
1.8的HashMap到底怎么了？他的性能更好了，在这个版本HashMap的存储结构发生了细微的变化，而这个变化，也直接导致了HashMap的性能比以前好了一些。
首先的一个重要的变化，那就是存储结构由以前单纯的数组+链表，变成了数组+链表/红黑树。什么意思呢，就是这个数组上跟着的可能是一个链表，也可能是个红黑树。当冲突节点（也就是链表上的节点）个数达到7个或者7个以上的时候，将会把链表转换为红黑树，然后继续进行存储。这里需要说明一点，就是HashMap中就可能存在有个数组节点后面是链表，有的是红黑树的情况。
有个什么好处呢，在最坏的情况下，冲突节点个数假设为N，那么1.6版本的时间复杂度为O(N)，但是在1.8版本中时间复杂度会是O(logN)，性能有了提升。
下面看一下1.8版本的HashMap存储结构图（偷个懒省略null了）。
当冲突比较明显的时候，红黑树是要比链表好点。接下来再看看1.8的hash算法是什么样的，同样设h为key的hashCode。
|
1 |
return h >>> 16; |
比1.6的简单了好多啊，由于HashMap的key进行hash如果冲突之后，使用红黑树比链表性能更好，所以作者觉得就算冲突了也还好，所以简化了hash算法，只是把高16位异或下来了而已。
再聊下加载因子Load Factor
HashMap中用到了一个扩容因子，他的作用很简单，就是为了防止数组都有元素的时候才扩容，默认扩容因子为0.75，也就是说，默认16个长度的数组，在有13分元素占满数组的时候，就会开始扩容了。如果没有扩容因子，那么到16个数字格子都占满了才扩容，那肯定这时候肯定很多数组元素里面后面有很长的冲突了（链表很长或者红黑树很高）。而且HashMap的扩容，其实要比ArrayList扩容复杂的多，性能也差很多。
假设声明一个HashMap，大概知道数组可能的长度，或者要copy一个HashMap，不能简单的像下面这样写。
|
1 |
HashMap map = new HashMap(n); // n为知道的可能长度 |
因为加载因子的作用，在填充内容的时候很容易还是需要一次扩容的。HashMap里面有一个可以把一个HashMap复制过来的方法，是putAll方法，接收一个Map参数，看下里面的实现，其实他会初始化一个长度，((float)s / loadFactor) + 1.0F，然后转换为int类型，其中s为原Map的size。
最后拓展个IntObjectHashMap
先写个测试代码。
|
1 2 3 4 5 6 7 8 9 10 11 |
IntObjectHashMap<String> map = new IntObjectHashMap<String>(); map.put(1, "c"); map.put(2, "b"); map.put(3, "a"); MutableIntSet mutableIntSet = map.keySet(); for (IntIterator iter = mutableIntSet.intIterator(); iter.hasNext();) { int key = iter.next(); System.out.println(map.get(key)); } System.out.println(map.getFirst()); // c System.out.println(map.max()); // c |
很多时候我们想要用key类型为int的Map，但是常规情况HashMap的key只能是Integer，虽说空间浪费了一点我们也不是很在意，但是这个IntObjectHashMap确实有更多厉害的地方。
通过上面示例代码我们可以看到他可以取第一个元素，可以拿到最大值的元素。其实他的Set也可以获取min()和max()，还可以转换为数组和有序数组。
最后有个内容差点忘了，IntObjectHashMap并不是JDK自带的，但是如果你的项目比较大的话，很容易就已经引用到了这个模块，pom文件看下面，版本号并不重要。
|
1 2 3 4 5 |
<dependency> <groupId>com.goldmansachs</groupId> <artifactId>gs-collections</artifactId> <version>7.0.0</version> </dependency> |
两个内容混起来写总觉得不太好，我又懒了。
©原创文章，转载请注明来源： 赵伊凡's Blog
©本文链接地址: 好好用Java的HashMap及1.8的变化