HashMap源码分析（主要基于JDK1.8）
什么是HashMap
HashMap是一个用于存储Key-Value键值对的集合，也是Java中使用频率最高的用于映射(键值对)处理的数据类型。
众所周知，HashMap访问速度快，遍历顺序不确定，线程不安全。这些特点都是由底层实现决定的，将在本文中进行分析。
在JDK1.8中，对HashMap的底层实现进行了优化，接下来本文将结合JDK1.7及JDK1.8的区别，对HashMap的底层实现原理做简单的分析（主要基于JDK1.8）。
JDK1.7、JDK1.8中，HashMap的区别简述
JDK1.7
1、hash计算，4次扰动
2、实现方式：链表 + 数组
3、链表：头插法（并发扩容时容易出现环形链表）
4、扩容时重新计算桶下标
JDK1.8
1、hash计算，1次扰动
2、实现方式：链表 + 数组 / 红黑树
3、链表：尾插法
4、扩容时只计算hash值新增的bit
存储结构
都知道JDK1.7中，HashMap的实现方式是：数组 + 链表，在JDK1.8中，引入了红黑树做优化。那么，数组 + 链表 / 红黑树，这个存储结构，是怎么实现的呢？让我们把目光放到源码中，
/* ---------------- Fields -------------- */
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;
字段定义的一开始，就是一个Node<K,V>类型的table数组。那么再看看Node<K,V>的定义：
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
......
}
Node<K,V>是HashMap的一个内部类，它实现了Map.Entry接口，本质上就是一个映射（键值对）。Node<K,V>中，除了key和value字段之外，还定义了hash和next字段。next字段也是Node<K,V>类型的，这意味着，Node<K,V>这个类有能力组成链表。事实也正是如此，下图中，我画出了HashMap的实现图示，包含了链表和红黑树，红黑树的定义TreeNode<K,V>同样也是HashMap中的一个内部类。
存储结构图示
左侧的是table数组，每一个圆点都代表一个Node / TreeNode。
有个小的细节，在这里提及一下。当链表达到树化阀值（TREEIFY_THRESHOLD = 8）的时候，并不会直接树化这条链表，而是先判断table数组有没有达到最小的树化容量（MIN_TREEIFY_CAPACITY = 64），如果没达到的话，此时HashMap会选择扩容，而非树化。因此，实际使用过程中，要出现图示的结构，table数组的长度至少要有64。
HashMap初始化
简单的了解下初始化方法。在实际使用过程当中，最常用的就是不带参数的默认构造函数，和指定容量的构造函数。例：
Map<String, String> map1 = new HashMap<>();
Map<String, String> map2 = new HashMap<>(20);
Map<String, String> map3 = new HashMap<>(65);
不带参数的默认构造函数，实际上只做了一件事情，就是设置负载因子loadFactor的值。在此不赘述。
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
带指定容量的构造函数，通过代码，可以看到实际上是调用了这个方法：
/* ---------------- Public operations -------------- */
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
可以看出，除了设置负载因子loadFactor的值外，还调用了tableSizeFor方法，将其返回值赋给threshold字段。
tableSizeFor这个方法，可以重点了解下。方法入参是容量的期望值，返回则是大于等于期望值的，距离这个值最近的2的次方值。
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
通过不断的与自身无符号右移的结果做按位或，得到一个低位全部都是1的数据。然后再加1，就可以得到2的次方值。
以期望容量65为例，经过一系列无符号右移及按位或操作后，得到了实际容量128。
（这个值是容量，也是table的长度。初始化的时候暂时把这个值赋值给了threshold，一般threshold的计算方式其实是capacity * load factor，由此可以得知，当table == null时，threshold的值可能为0，也可能为当前实际容量）
tableSizeFor方法计算图示
按位或( | )：按位运算，有一个是1，结果为1，否则为0；
无符号右移( >>> )：向右移动N位，高位用0补齐；
HashMap的put方法解析
要再深入一点了解HashMap的原理，那么可以先从put方法入手，put方法大致可以分为三步：
· 检查是否需要resize()
· 确定哈希桶数组索引位置
· 存放键值至对应链表/红黑树中
先来一个整体流程图：
put方法流程图
可以看到，流程的第一步是判断是否需要扩容，这一步的目的很明确。就是保证后边的存放步骤可以存放到一个正确的数组当中。像刚才我们提到的初始化方法，就肯定要进行扩容，因为构造函数中，并没有对table字段进行赋值，这样显然是无法使用的。这个时候扩容，就会将table默认初始化成一个长度为16的Node数组，当然，如果填了初始化容量，那么table就会被初始化成长度为tableSizeFor返回值的Node数组。
计算哈希桶数组索引
此时我们已经拥有了一个长度合适的table数组，那么接下来将要计算Key在哈希桶数组中的索引，那索引的计算公式是什么呢，看源码：
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 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) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
......
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
......
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
关键代码在putVal方法的第5行，p = tab[i = (n - 1) & hash] 这里。JDK1.8中并没有将哈希桶数组的索引抽成方法来计算。但从代码中我们还是可以提取出，其计算公式为：
(n - 1) & hash
话不多说，上图：
key = "hello world"
key.hashCode() = 1794106052
（1794106052的二进制表示：0110 1010 1110 1111 1110 0010 1100 0100）
哈希桶数组索引计算图示
按位与( & )：按位运算，都是1，结果为1，否则为0；
位异或( ^ )：按位运算，相反为1，相同为0；
图示中是JDK1.8中，哈希桶数组索引的计算步骤拆解。其中h ^ (h >>> 16)这一步，是为了让hashCode的高位也参与到运算中来，增加hash值的随机性。JDK1.7和JDK1.8中，hash值的计算方式是不同的，因此，在JDK1.7和JDK1.8中，同样的数据所对应的桶下标是可能不一致的。（并没有什么关系，因为除了你我，别人可能都不太关心HashMap中的数据到底是怎么存放的😑）
从图示中可以看到，key在哈希桶数组的位置，取决与它自己的hash值和当前HashMap的实际容量，也就是table的数组长度。（图示中HashMap的当前容量是16，key的桶索引其实就是其hash值的低4位）
存放逻辑
哈希桶数组索引已经有了，那么接下来就是将键值对存放到对应的数组 / 红黑树中。从流程图中可以看到，接下来就是判断是否有产生了hash冲突。本文开头提及过，HashMap的访问速度非常快。在Hash算法合理的前提下，最理想的情况是所有的键值对都均匀的散落到table数组中，在不发生哈希冲突的情况下，只要能定位到哈希桶索引，就能定位到想获取的数据。所以这里判断了两次，第一次，判断tab[i]是否为null，如果为null，那么直接存放即可；如果不是，则进行第二次判断，判断tab[i]中已存放的key是否就是我们将要处理的key，如果是的话，说明也没有发生哈希冲突，此时直接覆盖即可。如果也不是，说明发生了哈希冲突，这时候，就要区分：
链表：遍历链表，查找是否已经存在该key，已存在则覆盖原有值；若不存在，则将key、value插入链表末尾（JDK1.8：尾插法）；如果插入该数据将使得链表长度达到树化阀值8，则进行树化；
红黑树：遍历树节点，若该key已存在则覆盖原有值，若不存在则插入树节点；（红黑树这块后边单独开个文章细讲）
扩容逻辑
将数据按逻辑存放好后，在putVal方法的末尾，进行了一次检查（++size > threshold），如果判断数据已经达到了threshold，则做一次扩容resize()。
已经了解到HashMap的核心字段table之后，扩容这个操作就很好理解了。在Java中，数组是不可以自动扩容的。因此，扩容的思路就是用一个容量大的数组，替代原先容量小的数组，并将数据迁移到新数组当中。
实际上HashMap也是这么做的，用一个新的数组替代原先容量小的数组，但是在数据迁移的过程中，并不是直接一个个数据重新计算hash值及桶下标，而是只计算了hash值新增的bit。设计得非常巧妙。
还记得上边说到的哈希桶数组索引的计算方式吗？
(n - 1) & hash
还是以key = "hello world"为例，请看：
!
扩容机制-1
同一个key，它的hash值是不变的，那么变量在哪里呢？自然就是n了，n是数组的长度。图中HashMap的容量从16扩容到32，唯一变化的就是(n - 1)，从低4位都是1，变成了低5位都是1。
而变化的这一位，很关键的，就等于原有的容量。
扩容机制-2
由上可以得知，扩容前后，数据所在的桶下标只有2种情况：
1、新增bit为0，桶下标不变；
2、新增bit为1，桶下标 = 原有桶下标 + 原容量；
这样，就可以将原先某个哈希桶中冲突的节点，分散到2个哈希桶中了。
同时，新增bit为0 / 1，这件事情可以认为是随机的，因此扩容过程，可以把原先hash冲突的节点均匀的分散到新的桶中。
至此，HashMap的put方法就简单的解析完了。源码写得很赞，可以学到挺多的。
非线程安全
HashMap并非线程安全类，在刚才的源码解析中，可以发现在put操作中，并没有加锁，也就是说任一时刻可以多个线程同时写HashMap。那么就会有一定的几率会出现数据丢失的情况。先简单的列举以下几个场景，如：
1、两个线程同时判断完 tab[i] == null, 准备newNode赋值给 tab[i] 时；
2、两个线程同时判断到链表末尾，(e = p.next) == null，准备newNode赋值给 p.next 时；
3、一个线程扩容中，已经将新的Node数组赋值给table，但未迁移完数据。此时另一个线程执行了put / remove操作，则 put / remove 操作可能无效；
……
还有其他非线程安全的可能，这里没有全部列举出来，只是提供思路供参考。
/**
* 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) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
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;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
当2个线程同时已经判断完了if ((p = tab[i = (n - 1) & hash]) == null)，准备执行写入数据时，先写入的数据将被后写入的数据覆盖。同理，如果2个线程同时已经判断到了链表的末尾 if ((e = p.next) == null)，准备执行 p.next = newNode(hash, key, value, null)写入数据时，后写入的数据将覆盖先写入的数据。（大前提都是，同时写入的数据，桶下标刚好相同，也就是产生了Hash冲突）
除此之外，当线程1正在扩容，已经将新数组赋值给table（已执行到table = newTab），但还未执行下边的数据迁移操作，此时线程2写入（或删除）数据，线程1再执行完对应的数据迁移操作，都会导致线程2写入的数据被覆盖（删除数据将不生效）
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
......
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
......
}
return newTab;
}
为了加深印象，这里准备了2个例子，供参考。
下边是我本地复现线程不安全的代码，感兴趣的话可以试试。这是基于JDK1.8的。
示例1
import java.util.HashMap;
public class HashMapDemoResize1 {
private static HashMap<String, String> map = new HashMap<String, String>();
public static void main(String[] args) {
map.put("5", "C");
new Thread("Thread1") {
public void run() {
map.put("16", "B");
System.out.println("put record. key: 16, value: B. result: " + map);
};
}.start();
new Thread("Thread2") {
public void run() {
map.put("27", "A");
System.out.println("put record. key: 27, value: A. result: " + map);
};
}.start();
System.out.println("HashMapDemoResize1");
}
}
本地我是先让两个线程都同时跑到if ((e = p.next) == null)，然后让Thread2先把key = "27"的数据put到链表末尾，再执行Thread1的代码。可以看到，打印出来的结果中，key = "27"的数据被覆盖了。
HashMapDemoResize1
示例2
import java.util.HashMap;
public class HashMapDemoResize2 {
private static HashMap<String, String> map = new HashMap<String, String>(4);
public static void main(String[] args) {
map.put("12", "A");
map.put("23", "B");
map.put("34", "C");
System.out.println("");
new Thread("Thread1") {
public void run() {
map.put("45", "D");
System.out.println("put record. key: 36, value: D. result: " + map);
};
}.start();
new Thread("Thread2") {
public void run() {
map.put("56", "E");
System.out.println("put record. key: 48, value: E. result: " + map);
};
}.start();
System.out.println("HashMapDemoResize2");
}
}
这里初始容量设置为4的目的是，threshold = capacity * load factor，threshold为3，也就是当put到第4个数据的时候，需要扩容resize()。
我本地让Thread1先跑到resize()方法中table = newTab这一步，然后让Thread2将key = "56"的键值对put进去，再让Thread1执行数据迁移操作。
从结果中可以看到，key = "56"的键值对被覆盖了。
HashMapDemoResize2
看到这里，相信你已经知道为什么说HashMap是线程不安全的了吧。如果要求线程安全的话，建议使用ConcurrentHashMap；如果不要求线程安全，直接使用HashMap即可。
如果这篇文章对你有帮助，不妨点个赞再走吧~ _
