说到HashMap，绝大多数Java程序员并不默认，在没有研究它之前，我们严重的HashMap多是这样的：
Map<String, String> map = new HashMap<>()
map.put(key, value);
map.get(key);
map.putAll(List<Map>)
……
然而在面试官眼里，可大不一样，它可以对数组、链表、位运算、线程安全等一系列Java基础的集合。很多时候，HashMap是Java面试绕不过去的点。以上的知识点，我们可以在学习HashMap原理和源码的过程中掌握和消化。本文试图详尽的描述作者对HashMap的理解，力求条理清晰。
- 哈希是谁
- Map为啥扯上Hash
- HashMap的创建及put方法（结合源码）
- HashMap的get方法（结合源码）
哈希是谁
哈希在这里指的是哈希函数，简单来说，哈希算法会接收任意输入对象，将其转换成定长的整型数字输出。一个好的哈希函数会有两个特点：一是同一性，也就是说由于任意输入经过fun后都是定长输出，输出是固定长度，就意味着这个函数输出的最大值是确定的，那么哈希函数需要力争让任何输入都能均匀的散落到输出区间上，以免过多的输入映射到同一个输出上；第二点是雪崩效应，它表示当输入变化一点，输出就产生很大的变化，其目的也是希望减少碰撞。本文不会涉及具体的哈希算法，我们也不需要纠结在这一点上，把握住哈希算法的含义和特点即可。
Map为啥扯上Hash
我们知道Map是一种键值对形式的数据结构，那为啥Java要把Map和Hash算法结合起来呢？
其实即便我们将Map在内存中用数组或链表的形式存储也是可以的，试想每一个存储节点的数据结构如下：
//数组node
Node<K, V> {
K key;
V value;
}
//链表node
Node<K, V> {
K key;
V value;
Node<K, V> next;
}
它当然可以存储Map要表达的数据，但是对于数组而言，我们知道它在内存中是连续的，这意味着，数组在查询时有天然的优势，因为知道初始地址和index就可以很快锁定读取位置。但正是由于连续的内存地址，导致在做删除和插入操作时，数组需要不断调整操作节点后续的位置，导致效率低下；那链表呢，链表的内存地址是不连续的，每一个节点都记录着下一节点的内存地址，所以如果做查询操作，我们需要挨个访问兴趣节点之前的所有节点，才能找到它，此时效率是低下的，对于删除和新增来讲会比数组灵活，因为只需要改动附近节点的next指针即可，其它节点不受影响。所以一个是新增删除效率低下（数组），一个是读取效率低下（链表）。人们就试图将二者结合，做到优势互补，这就是下一个话题——哈希表
哈希表在内存中的直观表现如下：
哈希表
它是数组+链表或者叫做链表数组形式组成。我们来看一下插入、读取、删除哈希表会如何操作：
- 在插入的时候，输入对象先通过特定哈希函数计算，其输出会落在左边数组的index里面（不会超过array.length），如果该数组元素没有指向任何Node，则直接将插入的值生成Node挂在对应数组元素之后，如图array[8]所示；如果该数组元素后面已经挂有链表存在，则我们将遍历这个链表，确定链表中没有相同的key后，挂在链表的最后，也就是数组 --> 原链表 --> 新Node。
- 在读取的时候，读取的时候也是先根据key值计算哈希函数结构，找对应的array index，找到后根据key遍历对应的链表。
- 删除的过程参照读取。
这样一来无论是读写还是删除都可以很快的缩小范围，降低时间复杂度。最理想的情况是所有输入的hash值都散落在数组index范围内，这样每个数据元素后面都只指向一个链表节点。当然最坏的情况是所有hash值都落在某一个array节点上，这就是所谓的哈希碰撞，或者叫做违反“同一性”原则，这样的哈希函数需要改进。
HashMap的创建及put方法（结合源码）
接下来我们需要阅读源码，看一下HashMap真实的样子，在此之前，我将需要理解的专有概念梳理出来，方便查阅。
capacity：指代哈希表中数组的容量；
load factor：它是一个(0,1)的float，作为一个系数，用来计算当前array的阈值。打个比方，capacity是8，load factory是0.75，当哈希表的数组部分落入hash值到达8*0.75=6个时，哈希表会根据一定规则进行扩容；
Threshold.png
我们就以文初那段代码为索引，看看大家眼中的HashMap实际上做了些什么。
1. 初始化：
Map<String, String> map = new HashMap<>()
HashMap对外暴露了4个构造函数，三个带参，一个无参，我们常用是无参构造函数：
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
很简单构造函数仅仅初始化了loadFactor=0.75f，在后面有一个注释：其它成员采用默认设置。那我们就来看看有哪些重要的成员。
- table
transient Node<K,V>[] table;
哈希表的数组部分，可以看到每个元素都是一个Node节点，Node是HashMap的内部类，成员包括Key，Value，hash，和下一个Node的引用：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
……
- size
transient int size;
记录key-value个数
- modCount
transient int modCount;
记录HashMap的操作数，比如每次执行put、get、remove等操作，modCount都会加1。
- threshold
int threshold;
如上面所说，代表的是阈值 threshold = capacity * loadFactor。
- loadFactor
final float loadFactor;
加载因子，上文已详细说明，不赘述。
2. 写入
map.put(key, value);
我们看到HashMap的put方法其实是对putVal方法的直接调用，没有其它多余的东西，那我们来好好研究一下putVal方法，先看一下方法的声明：
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict)
前三个参数很好理解，hash（根据key值计算出来的hash值），传入的key和value。后两个参数在put方法调用的时候直接设置成onlyIfAbsent = false，evict=true。后者暂时不用关注，onlyIfAbsent的意思是如果如果key值已经存在是否要替换传入的value，设置为false代表如果key存在则覆盖其value；true是指如果key存在则传入的value不会被写入。
所有传参都很清晰，有一点！int hash是怎么来的，当然是通过hash函数计算而来，但是我们有必要看一下这个过程。put方法在调用putVal时传参如下：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
hash(key)是什么怪物？进去看一下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
到这里我们终于看到跟哈希有实质性关系的地方了，如果key值为null，那么返回的hash值为0，这里先得出一个结论：HashMap的key可以为null，而且对于这类数据，HashMap存放在index=0的位置！要强调的是，hash值为0并不是index为0的直接原因，后面会提到，HashMap对得到的hash值做了位与操作，这个位与的结果就是index，自然任何值与0位与结果为0。对于非空key，返回值的计算方式则是先进行hashCode计算，其结果的高位和低位做了异或。其中hashCode方法是一个native方法：
public native int hashCode();
它的具体实现跟JVM有关，要注意的一点是，对于同一个对象进行hashCode，在同一个Java应用执行阶段，无论调用多少次，都会返回相同的int数。当然如果不同版本的JVM或者再一次启动某Java程序，返回的int数可能不同。那么问题来了，既然通过本地方法已经得到了一个整型值，为何不直接返回呢？我们先看一下jdk8的这段代码做了些什么
(h = key.hashCode()) ^ (h >>> 16)
因为hashCode返回是个整型，也就是说内存占用4字节，我们就以一个32位的2进制数举例：
根据key生成index的过程
第一步：执行native方法hashCode得到一个32位的2进制数
第二步：将这个数与它右移16位的数进行异或
第三步：将第二步的结果与capacity-1的值进行位与（因为默认capacity为16，所以这里采用16为例）
最后的结果则为根据key得到的index数。
第三步的代码会在后面讲到，因为这三步是一条逻辑链，这里就一并讲解。回答刚刚的问题，我们试想如果第一步执行完后，函数直接返回，（n-1）直接和这个返回值做位与会是什么情况？
不做位移的情况下求index
大家可以看到，高16位在这种情况下无论怎么变，都不会影响到最后的结果，因为n-1的高位全为0，这样就会出现前面说的哈希碰撞，也违反了雪崩效应的原则，所以HashMap先将高位移到低位做异或（这段代码也叫做扰动函数），这样会增加高位变动对最终结果的影响，从而减少碰撞的可能性。说了半天，putVal()的函数声明及各位参数都说完了，接下来我们看看具体的写入过程。因为内容比较多，为了方便阅读，我将代码分成几段讲解，如果希望查看完整代码的可以自行去查询源码。
//声明变量
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
这里声明了4个变量，然后在if语句里面给tab和n进行了赋值：
tab <=> 成员变量table
n <=> table的长度
resize()我们之后在了解，接着看：
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
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);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
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;
}
}
if中首先对p进行了赋值：
p<=>该index上的Node对象（为了方便下文称之为原Node）
根据key得到的hash值算出table中的index，如果对应这个位置为null，则实例化一个Node，并放到这个位置。如果不为空则走入else。下面对于这种碰撞的情况进行处理：
- 如果原Node的key和传入的key一致，我们将传入的value覆盖原Node的value；
- 如果原Node的key和传入的key不一致，我们看一下这个原Node是不是TreeNode类型，如果是的，我们利用传入的key、value、hash生成一个TreeNode，并挂在上面；
- 如果Key不一致且不是TreeNode我们会根据next一级级往下找，且比对每个节点的key和传入的key，如果找到了一致的，就将该节点的value换成传入的value，如果找到最后一个节点仍然不一致，则先根据key、value、hash新建一个节点，如果这个节点小于TREEIFY_THRESHOLD这个阈值，就直接接入链表尾部。如果大于TREEIFY_THRESHOLD则进行树化。
HashMap的get方法（结合源码）
如果理解了以上的put过程，那么整个get过程就是很容易的，get方法的核心代码如下：
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
- 如果当前table里面没有内容，则get时返回null；
- 根据key得到table的index上的Node，如果第一个Node的key与传入的key一致，则返回第一个Node；
- 如果第一个Node的key与传入的key不一致，则先会判断，这个index绑定的Nodes是不是树型，如果是的，则调用getTreeNode方法去获取对应的节点；
- 如果不是树型，则沿着链表比较key值，如果能找到返回对应Node，如果找不到则返回null。
讲到这里出现了tree！怎么又蹦出来新的数据结构！这个应该是在jdk8后对传统HashMap的优化。这个我们下一节再详细解释。
网友评论