HashMap深入解读（一）
概述
HashMap是我们在日常开发中经常会用到的一种用于处理键值对映射的数据类型，jdk1.8对HashMap底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。在本篇文章中我们从HashMap、HashCode是什么开始，并结合源码的解读，对HashMap的根据key获取哈希桶数组索引位置、put方法的详细执行过程这两个具有代表性的点来进行深入探讨。
HashMap是什么
在回答这个问题之前，我们先举一个生活中最常见的例子：图书管理员在藏书的时候，会把书架进行分类，然后把对应类别的图书分别放到对应类别的书架上。而我们在借书的时候只需去对应类别的书架上去找即可。这种藏书方式大大缩短了我们借阅图书的查找时间。而如果图书存放杂乱无章，在书籍的存放数量很大的情况下，那我们在借阅查找的时候可能会一筹莫展。
绘图1.png
其实HashMap也是用到了这种思路，HashMap作为一种处理键值对映射的数据类型，我们很多时候用于常规的增删改查，但HashMap在存数据的时候(put)并不是随便乱放的，它会先做一次类似“分类”的操作再存储，一旦“分类”存储之后，下次取(get)的时候就可以大大缩短查找的时间。我们知道数组在执行查、改的效率很高，而增、删(不是尾部)的效率低，链表相反，HashMap则是把这两者结合起来，我们来看一下HashMap的数据结构：
无标题.png
从上面的结构可以看出，通常情况下HashMap是以数组、链表的组合构成，在Java8中链表长度超过8时会把长度超过8的链表转化成红黑树。结合上面借书的例子，我们简单分析下HashMap存取操作的心路历程。put存一个键值对的时候(比如上图“天王”)，先根据键值"分类"，"分类"一顿操作后告诉我们，天王应该属于2号坑，直接定位到2号坑。接下来有几种情况：
- 2号坑没人，nice，直接存值；
- 号有人，也叫天王，替换原来的值；
- 号有人，叫老王！插队到老王前面去(单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置)
get取的时候也需要传键值，根据传的键值来确定要找的是哪个"类别"，比如找天王，"分类"一顿操作后告诉我们天王属于2号坑，于是我们直接定位到2号坑开始找，码妞不是…找到天王。
小结
HashMap是由数组、链表构成的数据结构，Java8中链表长度超过8时会把长度超过8的链表转化成红黑树；存取时都会根据键值计算出"类别"(hashCode)，再根据"类别"定位到数组中的位置并执行操作。
HashCode是什么
还拿上边的例子来说，如果图书管理员在存书的时候不做处理，想放哪个书架就放哪个书架，当学生去找书的的时候，只能挨个书架找，再挨个比对书架里面书籍的名字，万一这货刚好运气不咋地，要找的书放在最后一个书架的最后一个，悲剧…所以这种情况的时间复杂度为O(N)；右边采用HashCode的方式将所有书籍分类，将对应编号的书籍放到对应的书架上，这样学生就不用挨个找了，只需要比对一个书架里的书籍即可，大大提高了效率，这种情况的时间复杂度趋于一个常数O(1)。
_20200229191529.png
例子中上图其实就是hashCode的一个实现，每本书籍都有自己的hashCode，比如《Java编程思想》的hashCode是F，《数据结构与算法》的hashCode是H(这取决于你的hash算法怎么写)，然后我们根据确定的hashCode值把书架分类，hashCode匹配则存在对应书架。在Java的Object中可以调用hashCode()方法获取对象hashCode，返回一个int值。但是，会出现两个对象的hashCode一样吗?答案是会的，就像上上个例子中天王和老王的hashCode就一样，这种情况网上有人称之为"hash碰撞"，关于"hash碰撞"会在后面的文章中深入探讨。
小结
hashCode是一个对象的标识，Java中对象的hashCode是一个int类型值。通过hashCode来指定数组的索引可以快速定位到要找的对象在数组中的位置，之后再遍历链表找到对应值，理想情况下时间复杂度为O(1)，并且不同对象可以拥有相同的hashCode。
源码解读
结合以上生活中的实例，我们对HashMap有了基本的认识，接下来我们根据源码来重点探讨一下根据key获取哈希桶数组索引位置、put方法的详细执行过程这两个具有代表性的点。
1. 确定哈希桶数组索引位置
不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。前面说过HashMap的数据结构是数组、链表以及红黑树的结合，所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，不用遍历链表，大大优化了查询的效率。HashMap定位数组索引位置，直接决定了hash方法的离散性能。我们来先看一下下面源码的实现:
方法一：
static final int hash(Object key) { //jdk1.8 & jdk1.7
int h;
// h = key.hashCode() 为第一步 取hashCode值
// h ^ (h >>> 16) 为第二步 高位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法二：
static int indexFor(int h, int length) { //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
return h & (length-1); //第三步 取模运算
}
这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。对于任意给定的对象，只要它的hashCode()返回值相同，那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，模运算的消耗还是比较大的，在HashMap中是这样做的：调用方法二来计算该对象应该保存在table数组的哪个索引处。这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。主要过程如下图。
8e8203c1b51be6446cda4026eaaccf19_1440w.png
2. 分析HashMap的put方法
啥也不说，我们还是先来看一下它的源码：
public V put(K key, V value) {
// 对key的hashCode()做hash
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 步骤①：tab为空则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步骤②：计算index，并对null做处理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 步骤③：节点key存在，直接覆盖value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 步骤④：判断该链为红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 步骤⑤：该链为链表
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key,value,null);
//链表长度大于8转换为红黑树进行处理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// key已经存在直接覆盖value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 步骤⑥：超过最大容量 就扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
结合上面源码，我们会发现其put过程分为以下几个步骤：
①. 判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
②. 根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
③. 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
④. 判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
⑤. 遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
58e67eae921e4b431782c07444af824e_1440w.png
总结
以上是对HashMap的根据key获取哈希桶数组索引位置、put方法的详细执行过程的基本解读，看到这里你一定还有很多疑问，比如为什么Java8要引入红黑树？链表的长度大于8为什么要转化为红黑树？HashMap的扩容机制又是什么呢？等等。关于这些我会在后续的文章中为大家深入解读。
