前言
HashMap是是Java Collections Framework的成员，位于java.util包，在JDK1.2引入。其数据存储形式是基于K-V键值对形式进行存储，HashMap中的key不能重复，允许且只能存在一个null值。如果多次put同一个key会进行值覆盖，对于value则没有限制。
public class TestHashMap {
public static void main(String[] args) {
HashMap<String, String> map = new HashMap<>();
map.put("hello", "world");
map.put("java", "Map");
map.put(null, null);
map.put(null, "value");
System.out.println(map);
}
}
输出结果：
{null=value, java=Map, hello=world}
对HashMap有了一个基本的认知，HashMap在JDK1.2一直到JDK7中HashMap的实现都没有过多改变，在JDK8中HashMap做了较大调整，接下来会从基本理论以及源码等方面来分析HashMap的实现。
源码分析
这一部分内容会引入一些基本的概念，并且会从HashMap的一些实现细节进行分析，主要包含以下几个方面：
-
哈希冲突
-
数据结构特性，如数组、链表、红黑树、哈希表
-
扰动函数，如下计算索引
-
扩容机制
-
put方法的流程
-
线程安全
关于HashMap的分析如没有特殊说明以JDK8为准。
什么是哈希冲突
HashMap之所以被称为Hash Map，主要是在存储元素时用到了哈希算法，又被称为散列算法。哈希算法根据设定的哈希函数和处理冲突方法将一组关键字映象到一个有限的地址区间上，由于哈希算法被计算的数据是无限的，而计算后的结果范围有限，因此总会存在不同的数据经过计算后得到的值相同，这就是哈希冲突。
说明：HashMap中的key并没有特别要求，既可以是对象也可以是字符串等，在没有重写hashcode时，Java中对象的引用被修改也会随之影响hashcode，对象并不是那么适合作为Map的key。如果想要一个稳定的key，这要求对象是不可变的，Java中String就符合这一特点，事实也如此，往往被用作Map的Key。
HashMap中计算散列值的时候对先调用对象自身的hashCode方法，查看String类的hashCode方法：
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
关于这个方法的公式可以推导为：s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1]，其中n为字符串总长度，s[i]为第几个字符串。但是使用这个方法就会很容易造成哈希冲突，更多参考。
例如计算ABCDEa123abc和ABCDFB123abc的hashcode结果是一致的。
ABCDEa123abc --> 1001110110110110101011101110
ABCDFB123abc --> 1001110110110110101011101110
当遇到这种情况时，就是哈希冲突，而且哈希冲突一定会存在，在HashMap中，如果想提高效率，就需要尽可能少的发生哈希冲突，或者使散列结果尽可能均匀，接下来会详细说明HashMap是如何解决哈希冲突。
构造方法
HashMap提供了多个构造方法，其中比较重要的一个构造方法需要了解：指定了初始化容量和加载因子。
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);
}
HashMap传入的initialCapacity参数，并没有用来记录其容量的大小，而是用来计算阈值，因为在达到阈值时就会进行扩容操作，关于阈值的计算有如下计算方法：
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;
}
该方法的作用是返回一个与传入参数cap最接近的2^n的一个结果，即满足2^n >= cap例如：
2 --> 2
4 --> 4
10 --> 16
17 --> 32
**说明：**在构造方法中
this.threshold = tableSizeFor(initialCapacity);这一行代码，将计算的结果赋值给阈值，在使用指定初始化容量的构造方法时，首次扩容会把这个计算结果赋值给HashMap的容量。
数据结构
HashMap中用的数据结构是哈希表，并不是具体单一的某种结构，而是复合了单一类型的数据结构，因此想要理解其实现原理，就需要先知道一些基本概念。
常见数据结构
数组
数组是一种最基本的数据结构，是按照一定顺序存储在连续的内存空间中，由于数据是存储在连续空间内的，所以每个数据的内存地址(在内存上的位置)都可以通过数组下标算出，也就可以借此直接访问目标数据，也就是随机访问。如下图所示：
数组的这种结构，在进行数据访问时的效率足够快，需要的时间复杂度为O(1)，但是再在插入和删除数据时，由于内存连续的要求，需要将操作索引处后的元素进行移动，需要的时间复杂度为O(n-index)，如果在数组头部操作，那需要将现有所有元素进行移动，修改到指定下标位置。这里所说的下标其实表示的并不是元素的顺序，而是地址的偏移量，由于首个元素偏移为0，因此数组的下标从0开始。
.png)
数组由于其根据偏移量操作和快速查询的特性，被用作HashMap中的基本存储单元，作为bucket(一个下标对应一个bucket)存在，通过哈希算法确定元素被存储与哪个bucket中，也可以根据下标快速定位到对应的bucket。
链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。如下图所示：
.png)
链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，链表允许插入和移除表上任意位置上的节点，但是不允许随机存取，链表由于增加了结点的指针域，空间开销比较大。链表有很多种不同的类型：单向链表，双向链表(可以实现双向遍历)以及循环链表，如下图的线性链表示意图：
.png)
由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
链表在HashMap中用于数组bucket中元素hashcode发生哈希冲突时，进行元素的链式存储，在JDK8中，到达对应的阈值后链表会进行树化。
红黑树
红黑树(Red-Black Tree)它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红或黑。红黑树可以用来存储有序的数据，查找的时间复杂度为O(logN)。红黑树满足以下特性：
-
节点是红色或黑色。
-
根节点是黑色。
-
所有叶子节点都是黑色的空节点。(叶子节点是NIL节点或NULL节点)
-
每个红色节点的两个子节点都是黑色节点。(从每个叶子节点到根的所有路径上不能有两个连续的红色节点)
-
从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。
这里只简单介绍红黑树的特性，不再对红黑树做过多解析。
关于红黑树操作可以参考：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
HashMap存储结构
前面介绍了常见数据结构的特点，接下来对HashMap的使用的数据结构进行分析。
哈希表
HashMap在JDK1.8中的底层数据结构使用的是哈希表，即数组+链表或者数组+红黑树，是一个复合结构，可以充分利用数组、链表、红黑树的特点。每个数组下标位置存储不止一个元素，会存储多个元素，因此每个下标空间可以被称为一个bucket(桶)，哈希表结构示意如图所示：
.png)
由上图可知，哈希表中的节点根据数量的多少，存在两种形态，一种是链表节点，一种是红黑树节点，红黑树的节点实现也更为复杂，其本身占用的空间也更大，关于两种节点结构类型，如下所示：
链表节点
// HashMap普通链表节点，单向链表
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
红黑树节点
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
// HashMap红黑树节点，继承自普通Node节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
哈希表中同时复合了数组、链表、红黑树三种数据结构，因此在HashMap中查询数据时的时间复杂度也不是固定的，处于O(1) ~ O(logN) ~ O(n)几种场景。最理想的是没有发生哈希冲突，数据直接存储在数组位置，时间复杂度为O(1)。具体情况如下：
- 数组：哈希表中每一个数组的位置不止存储一个元素，可以看作一个bucket(桶)，在数组位置进行元素查找时间复杂度为O(1)。
- 链表：查找的时间复杂度为O(n)，这种情况下HashMap的综合时间复杂度为O(1)+O(n)=O(n)。
- 红黑树：查找的时间复杂度为O(logN)，该情况下HashMap的时间复杂度为O(1)+O(logN)=O(logN)。
HashMap中会采用数组+链表还是数组+红黑树的结构，取决于存储元素的多少和一些基本初始参数定义，在源码中初始化了如下重要的成员变量：
// HashMap中存储散列链表的数组，长度必须是2的幂
transient Node<K,V>[] table;
//默认初始容量 - 必须是 2 的幂。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量，如果一个更高的值由任何一个带参数的构造函数隐式指定时使用。必须是 2 <= 1<<30 的幂。
static final int MAXIMUM_CAPACITY = 1 << 30;
//构造函数中未指定时使用的负载因子。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表树化阙值： 默认值为 8 。
//表示在一个node(Table)节点下的值的个数大于8时候，会将链表转换成为红黑树。
static final int TREEIFY_THRESHOLD = 8;
//红黑树链化阙值： 默认值为 6 。
//表示在进行扩容期间，单个Node节点下的红黑树节点的个数小于6时候，会将红黑树转化成为链表。
static final int UNTREEIFY_THRESHOLD = 6;
//最小树化阈值，tab.length超过才会进行树化(为了防止前期阶段频繁扩容和树化过程冲突)。
static final int MIN_TREEIFY_CAPACITY = 64;
HashMap中哈希表数组默认的长度为16，加载因子为0.75，阈值为threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR，在HashMap中的元素个数达到threshold时会进行扩容，当数组的长度小于64时并不会直将链表转化为红黑树。当数组的长度大于等于MIN_TREEIFY_CAPACITY=64并且链表的长度超过TREEIFY_THRESHOLD=8时会将链表转化为红黑树，红黑树在查询数据时比较稳定，但是在元素增删操作时要经过旋转变色，比较消耗性能，因此在树元素小于UNTREEIFY_THRESHOLD=6时会退化为链表。
为什么在MIN_TREEIFY_CAPACITY=64并且链表长度超过8时会将链表转化为红黑树，在大量实验中，发生哈希碰撞的模型符合泊松分布，此时在同一个数组索引处发生哈希冲突的概率已经达到百万分之一。
泊松分布
Poisson分布，是一种统计与概率学里常见到的离散概率分布，由法国数学家西莫恩·德尼·泊松(Siméon-Denis Poisson)在1838年时发表。关于泊松分布，在源码中有如下解释：
Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are
(exp(-0.5) * pow(0.5, k) / factorial(k)).
The first values are:
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million
因为 TreeNode 的大小大约是常规节点的两倍，所以仅在数组的bucket包含足够的节点以保证使用时才使用它们红黑树节点，限制于TREEIFY_THRESHOLD参数。 当由于删除或调整大小变得太小时被转换普通链表节点。 在具有良好分布的用户哈希码的使用中，很少使用红黑树。 理想情况下，在随机哈希码下，bucket中节点的频率遵循泊松分布 (http://en.wikipedia.org/wiki/Poisson_distribution))，默认调整大小阈值为 0.75，参数平均约为 0.5。列表大小 k 的预期出现是(exp(-0.5) * pow(0.5, k) / k!)。结论：默认调整大小阈值为 0.75是根据大量实验得出的经验数据，是空间和时间均衡采取的一个结果，即保障了不会因为加载因子过小而频繁扩容，也不至于因为红黑树的多次操作导致HashMap的性能下降。
如何计算数组下标
HashMap中如何在put时确定一个key的存储位置，并且可以在get时快速找到这个key？这决定了HashMap的性能。HashMap通过key的hashcode与Map的数组长度进行位运算来确定某个key存储bucket索引的位置。
HashMap在JDK1.7中关于下标如何计算有如下代码：
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
虽然在JDK1.8中已经找不到该方法，但是在用到下标的地方原理是一样的使用了行内代码，例如putVal方法的片段：
// n为tab的length
tab[i = (n - 1) & hash]
为什么使用hashcode进行&运算时要使用length - 1？HashMap的初始容量16，扩容时为2倍扩容，即2^n，首先作为数组下标，其长度肯定不能超2^n-1，而hashcode的值往往比较大，也不可能初始化容量如此大的数组。此外2^n-1的二进制位还有如下特性：
15 --> 0000 1111
31 --> 0001 1111
63 --> 0011 1111
这个特性使得其非常适合作为掩码计算，无论hashcode的值是多大，只用关心决定数组长度的低位，使得计算后的下标一定落在[0,2^n-1]这个区间内。如下代码所示：
public static void testHashIndex() {
// 0000 1111 --> 15
// hello --> 101111010010001100011010010 & 1111 = 0010 --> 2
// redis --> 110011101011110010101111011 & 1111 = 1011 --> 11
// hashmap --> 101001100100111010000110001110 & 1111 = 1110 -> 14
List<String> strings = Arrays.asList("hello", "redis", "hashmap");
for (String string : strings) {
System.out.println(string.hashCode() + " --> " +
Integer.toBinaryString(string.hashCode()) + " & " +
Integer.toBinaryString(15) + " = " +
(string.hashCode() & 15));
}
}
输出结果：
99162322 --> 101111010010001100011010010 & 1111 = 2
108389755 --> 110011101011110010101111011 & 1111 = 11
697541006 --> 101001100100111010000110001110 & 1111 = 14
使用%也可以得到下标，但是&的效率要远高于%，此外，int范围-2^31 ~ 2^31 - 1进行%运算生成的hashcode有可能为负数，数组的下标不可能为负数，使用&运算避免了索引为负数可能。
扰动函数
为什么HashMap要重新生成hashcode，不使用key对象本身的hashcode？源码注释中给了明确的解释，查看源码中重新计算hashcode的方法：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
源码中有如下注释：
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.
HashMap中的关于索引计算是调用最为频繁的方法了，如果频繁出现哈希冲突，那么对于其性能也会有很大的影响，而通常用于作为key的String类型本身就有机率发生哈希冲突，再结合HashMap中索引计算的方法使得高位无法参与计算，(h = key.hashCode()) ^ (h >>> 16)这行代码是为了对hashCode进行扰动计算，防止不同hashCode的高位不同但低位相同导致的哈希冲突。
简单来说就是，即使得到的两个hashcode初始值高位部分差距较大，但是计算结果基本只受到数组长度二进制位的低位影响，为了把高位的特征和低位的特征组合起来，降低哈希冲突的概率，尽量做到任何一位的变化都能对最终得到的结果产生影响。
使用扰动函数产生的hashcode和对象本身hashcode计算出来的bucket位置时有所差别的，如下测试代码所示：
public static void compareDisturbanceIndex() {
String key = "星光不问赶路人，时光不负有心人";
int threshold = 16;
System.out.println("[NoDisturbance] \r\n hashcode --> " + Integer.toBinaryString(key.hashCode())
+ "\r\n index --> " + (15 & key.hashCode()));
System.out.println("[Disturbance] \r\n hashcode --> " + Integer.toBinaryString(key.hashCode())
+ "\r\n >>> --> " + Integer.toBinaryString(key.hashCode() >>> 16)
+ "\r\n ^ --> " + Integer.toBinaryString((key.hashCode() ^ (key.hashCode() >>> 16)))
+ "\r\n index --> " + (15 & (key.hashCode() ^ (key.hashCode() >>> 16))));
}
输出结果：
[NoDisturbance]
hashcode --> 111110110101000001001000100101
index --> 5
[Disturbance]
hashcode --> 111110110101000001001000100101
>>> 16 --> 11111011010100
^ --> 111110110101000010110011110001
index --> 1
从输出结果可以看到在进行扰动后，key对应的下标进行了变化，这也说明了扰动函数主要就是为了干预下标计算。
说明：需要注意的是对于扰动函数的计算结果，影响因素有数组本身的长度length和key的扰动hashcode，如果只是从数组的长度来说，进行扰动不扰动似乎结果也没有那么重要，计算结果都是分布在[0,2^n-1]中，影响结果的也总是hashcode低位，但是扰动函数的目的就是使得高位也尽可能的参与到运算，从这个角度来说只有通过大量测试才能观测到扰动结果。
下面对于HashMap中扰动函数的作用进行简单验证，实验代码如下：
package com.starsray.test.hashmap;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
public class TestHashMapDisturbance {
public static int disturbanceIndex(String key, int size) {
return (size - 1) & (key.hashCode() ^ (key.hashCode() >>> 16));
}
public static int index(String key, int size) {
return (size - 1) & key.hashCode();
}
public static void testIndex(int times) {
int threshold = 256;
Map<Integer, Integer> map = new HashMap<>();
Map<Integer, Integer> disMap = new HashMap<>();
for (int i = 0; i < times; i++) {
String randomKey = getRandomKey();
int index = index(randomKey, threshold);
if (map.containsKey(index)) {
Integer count = map.get(index);
map.put(index, ++count);
} else {
map.put(index, 1);
}
int disIndex = disturbanceIndex(randomKey, threshold);
if (disMap.containsKey(disIndex)) {
Integer count = disMap.get(disIndex);
disMap.put(disIndex, ++count);
} else {
disMap.put(disIndex, 1);
}
}
System.out.println("map index:");
map.forEach((k, v) -> System.out.println(k + "," + v));
System.out.println("map disturbance index:");
disMap.forEach((k, v) -> System.out.println(k + "," + v));
}
public static String getRandomKey() {
String str = "AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZzAaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZzAaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz";
int len = (int) (Math.random() * 20 + 5);
Random random = new Random();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < len; i++) {
sb.append(str.charAt(random.nextInt(str.length())));
}
return sb.toString();
}
public static void main(String[] args) {
testIndex(100_000);
}
}
put方法的流程
HashMap的put方法是实现最为复杂的，查看HashMap的put方法源码，其内部调用了一个私有的putVal方法：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
说明以下入参：
- hash(key)：经过扰动函数计算后的key的hash值，尽可能让key自身hashcode高位参与元算，提高散列效果
- key：存放的key值
- value：存放的value值
- onlyIfAbsent：是否覆盖现有的值，默认为false，即相同key后put的值会替换先put的值
- evict：是否驱逐，在HashMap中并没有实际用处，在继承自HashMap的LinkedHashMap中被重写afterNodeInsertion方法来移除早期插入的节点
查看putVal方法的源码：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 首次添加元素，哈希表的容量即HashMap未进行初始化，容量为null
if ((tab = table) == null || (n = tab.length) == 0)
// 对哈希表进行扩容，并且将哈希表扩容后的长度赋值给n，此处的n为2的幂次数
n = (tab = resize()).length;
// 根据当前key扰动后的哈希值进行下标位置计算，如果对应下标处的节点为空
// 当前put的元素会创建为一个K-V结构，并存储在tab[i]位置处
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 这里说明已经发生了哈希碰撞，哈希表中存储的元素要开始进行链化或者树化
else {
Node<K,V> e; K k;
// 这里的p指向当前key在哈希表中i索引处的节点，也就是发生碰撞的节点
// 如果p的哈希值和传入的哈希值相等或则p.key等于传入的key，或者key不为null的场景下
// 内容也一直，说明冲突的是同一个key,当前索引的节点p用e临时保存。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果当前的节点p是红黑树节点，说明整个哈希表已经树化，后面的节点也将使用红黑树处理
else if (p instanceof TreeNode)
// this为当前HashMap对象实例，tab为当前HashMap对象中的哈希表
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 使用临时节点e，从当前节点p开始进行链表的遍历
// 直到循环链表的尾节点，停止循环
for (int binCount = 0; ; ++binCount) {
// 如果当前节点的next指向为null，直接新建节点使用尾插法追加
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 从0到7，如果循环次数达到阈值，会进一步判断进行扩容还是使用红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 在treeifyBin方法中当table的长度小于64时会进行扩容
// 当table的长度超过64，并且每个下标处的元素超过8才会进行树化操作
treeifyBin(tab, hash);
break;
}
// 遍历过程中如果链表某个节点的key和当前操作key一致时，停止遍历
// 取出当前节点，并且此时临时节点e指向传入key所对应的节点，用于
// 下一步返回节点的旧值和新值的赋值
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 每次遍历后p指向新节点，驱动链表移动
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 如果覆盖或者当前oldValue为null，使用新值覆盖旧值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// LinkedHashMap回调使用
afterNodeAccess(e);
// 返回节点的旧值
return oldValue;
}
}
// 记录HashMap被修改的次数
++modCount;
// 如果当前size大于阈值，进行扩容
if (++size > threshold)
resize();
// LinkedHashMap回调使用
afterNodeInsertion(evict);
// 首次put元素时返回的旧值为null
return null;
}
- HashMap在初始化时并不会初始化容量，在调用
put方法时才会去初始化容量，在put时先使用扰动函数对key的hashcode进行二次计算，再根据数组的length - 1进行运算确定元素的下标位置，根据当前下标处是否有元素，可分为发生哈希冲突和未冲突场景：- 未发生哈希冲突：
- 首次：先调用
resize()方法进行扩容，初始化table的容量，确定bucket的位置，存放元素。 - 非首次：这种场景同首次添加类似，只不过少了初始化容量的步骤，直接计算元素
bucket的位置进行存放。
- 首次：先调用
- 发生哈希冲突：发现新添加的元素指向的bucket位置不为空，使用临时节点e指向该位置的首个Node
- 红黑树：如果当前Node是红黑树节点(TreeNode)使用红黑树的
putTreeVal方法进行元素添加。 - 链表：对链表进行遍历，使用尾插法进行元素添加，如果新添加的key与链表中的key一致，则取出旧值返回，使用新值替换掉旧值。在链表遍历时会判断链表元素长度，如果大于8个元素，会在
treeifyBin方法中进行判断，如果table长度小于64会进行扩容，超过链表会进行红黑树转变。
- 红黑树：如果当前Node是红黑树节点(TreeNode)使用红黑树的
- 未发生哈希冲突：
总结：在put的过程中会有可能触发resize，这个过程是比较消耗性能的，主要有下面几种场景：
- 首次进行元素添加，即table == null || table.length ==0，调用resize方法初始化容量。
- 发生哈希冲突，当链表满足TREEIFY_THRESHOLD = 8 && table.length < MIN_TREEIFY_CAPACITY会触发resize进行扩容。
- 当put元素后的容量，size > threshold会触发扩容
扩容机制
HashMap在存储元素数量达到阈值时会对数组的长度进行扩容，扩容的实现主要在resize()方法中，源码实现中可以将代码看作两部分，查看源码：
final Node<K,V>[] resize() {
// 第一部分：计算哈希表table的阈值和新的要扩容的容量
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
......省略代码
// 第二部分：根据第一部分计算的新容量newCap扩容，并对元素进行迁移
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
......省略代码
return newTab;
}
前面提到在put方法中共有3种情况可能会触发HashMap的扩容机制，在进行扩容时，首先会进行容量和阈值的计算，然后进行元素位置的调整，这就涉及到了链表或者红黑树的操作，消耗性能。如果可以预知元素个数，合理指定初始化容量，可以减少HashMap的扩容次数，提高性能。
以下代码简单验证HashMap指定初始化容量的差别：
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;
public class TestResize {
public static void main(String[] args) {
int cap = 2000_00;
int cycle = (int) (cap * 0.75) - 1;
String[] arr = createArr(cycle);
System.out.println(arr.length);
HashSet<String> set = new HashSet<>(Arrays.asList(arr));
System.out.println(set.size());
HashMap<String, Object> initMap = new HashMap<>(cap);
HashMap<String, Object> map = new HashMap<>();
work(cycle, arr, initMap);
work(cycle, arr, map);
}
private static void work(int cycle, String[] arr, HashMap<String, Object> map) {
long start = System.currentTimeMillis();
for (int i = 0; i < cycle; i++) {
map.put(arr[i], getRandomKey());
}
long end = System.currentTimeMillis();
System.out.println(end - start);
}
static String[] createArr(int cycle) {
String[] arr = new String[cycle];
for (int i = 0; i < cycle; i++) {
arr[i] = getRandomKey();
}
return arr;
}
public static String getRandomKey() {
String str = "AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZzAaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZzAaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz";
int len = (int) (Math.random() * 25 + 5);
Random random = new Random();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < len; i++) {
sb.append(str.charAt(random.nextInt(str.length())));
}
return sb.toString();
}
}
计算容量和阈值
HashMap在元素达到阈值时会进行扩容，其中前半段部分代码主要是计算如何扩容，如下所示：
final Node<K,V>[] resize() {
// 声明临时变量oldTable指向原来的数组，oldThr为原来的阈值，oldCap为原来数组长度或0
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
// 声明新的容量和阈值进行扩容
int newCap, newThr = 0;
if (oldCap > 0)
// 如果oldCap>=MAXIMUM_CAPACITY=2^30，直接定义阈值threshold为2^31-1，并且返回
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 当新的容量newCap小于MAXIMUM_CAPACITY，并且
// 旧的容量oldCap大于默认容量16时，进行扩容时阈值newThr也加倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// 需要注意这里的注释，JDK中一般添加注释的地方都需要特别关注
// 前面提到构造方法时，在指定构造方法时，把计算table的size赋值给了threshold，
// 在首次扩容并进行put时，会把tableSizeFor方法的计算结果通过oldThr赋值给newCap
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 首次进行put，使用默认的参数给newCap=16，newThr=16*0.75=12进行赋值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 在指定初始化容量时，进行扩容时会进行阈值的计算
if (newThr == 0) {
// 计算阈值
float ft = (float)newCap * loadFactor;
// 判断是否达到最大值进行阈值取值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 经过计算，最终确定HashMap中threshold的值
threshold = newThr;
...
}
HashMap在进行resize时会根据不同场景进行分别判断，根据是否已经进行初始化，未进行初始化时采用默认参数进行阈值和容量的计算，在指定初始化参数时或者已经有元素时会判断扩容后的容量是否达到最大阈值。
在进行扩容的时候，对于一些临界场景的判断需要结合源码注释进行上下文代码的结合，直接解读resize的源码是会有一些难以理解的地方。
元素迁移
在resize方法的前半部分，确定了新的阈值newThr和容量newCap。接下来需要对元素校验是否需要进行迁移。
final Node<K,V>[] resize() {
...省略部分
// 利用前面已经计算好的容量newCap创建一个新的数组newTable
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 将成员变量table指向新的数组引用，进行替换
table = newTab;
// 如果旧的数组不为null，说明已经进行过扩容，非首次，可能进行元素迁移，如果是首次进入
// 直接返回初始化的newTab
if (oldTab != null) {
// 外层对数组进行循环遍历，遍历的边界为扩容前的数组容量，覆盖到数组内的所有元素
for (int j = 0; j < oldCap; ++j) {
// 声明临时变量e
Node<K,V> e;
// 对原数组的每个下标处的元素进行遍历，如果数组对应下标处元素不为空进一步处理
if ((e = oldTab[j]) != null) {
// 把数组对应下标为j且不为空处的元素置为null
oldTab[j] = null;
// 如果e.next == null，说明e所处的下标j位置只有单个元素
if (e.next == null)
// 在新数据中对e重新进行下标判定
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 如果当前节点是红黑树节点进行特殊操作
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 其他情况说明该位置处为链表，需要对链表进行操作
// 声明了五个临时变量
// loHead、loTail对应低位处的链表头尾
// hiHead、hiTail对应高位处的链表头尾
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 生成链表
do {
next = e.next;
// 这里使用e.hash与扩容前的容量进行与运算，如果与运算的最终结果为0
// 说明扩容后的元素不需要进行迁移，否则元素需要进行迁移。
// 这里是一个巧妙的设计，i=h & (len - 1)，即i= h & 2^n - 1
// 扩容后是否迁移由2^n-1的高位决定，而2^n-1的高位与2^n的高位一致
// 因此通过h & oldCap可以判断元素在扩容后是否需要进行迁移
// 0 1 0000 --> 16 0 0 1111 --> 15
// 1 0 0000 --> 32 0 1 1111 --> 31
// 无论元素是否需要迁移，接下来都需要重新构建链表
// 元素bucket位置不迁移，组成新的链表
if ((e.hash & oldCap) == 0) {
// 如果链表的尾为null，说明头节点为null，临时节点e
// 作为链表的第一个元素，loHead指向e
if (loTail == null)
loHead = e;
else
// 尾节点不为空，当前临时节点e为原来尾节点的下一个节点
loTail.next = e;
// 第一次遍历首、尾节点都指向e，非首次遍历loTail指向新的尾节点
// 驱动链表追加元素
loTail = e;
}
// 元素bucket位置需要迁移，组成新的链表
else {
// 同上，高位需要迁移位置的链表遍历追加，尾插法
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null); // 直到遍历到链表的尾部
// 判断链表存放的位置，将头节点存放在bucket位置
if (loTail != null) {
loTail.next = null;
// 低位元素不迁移，完成重组链表的整体组建
newTab[j] = loHead;
}
if (hiTail != null) {
// 高位元素迁移至索引+旧容量位置，重组链表整体迁移至新的位置
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
JDK8中进行扩容时，没有rehash操作，数组扩容的大小为原来的2倍，恒为2的幂，扩容后元素是否迁移根据高低位进行判断。对于链表结构的bucket位置是否进行元素迁移，根据链表中元素key的hashcode与旧的容量进行位运算，由于容量为2^n，因此计算后的元素位置要么不迁移，要么迁移为当前下标+旧容量位置处，如：15–>31。
查看如下代码，1、31、63刚好满足2^n-1，也就是HashMap每次扩容后的长度参与下标计算的length - 1
public static void main(String[] args) {
System.out.printf("%032d%n",Integer.parseInt(Integer.toBinaryString(15)));
System.out.printf("%032d%n",Integer.parseInt(Integer.toBinaryString(31)));
System.out.printf("%032d%n",Integer.parseInt(Integer.toBinaryString(63)));
}
每次扩容后的2^n-1都高位都是1，如下输出结果所示：
00000000000000000000000000001111
00000000000000000000000000011111
00000000000000000000000000111111
在JDK8中key的hashcode是固定，在下标 i = hashcode & (length - 1)计算中，参与计算的hashcode要么是0要么是1。
例如：某个key的hashcode为52，在扩容前后进行与运算，扩容前后的下标分别为4、20，刚好为旧数组的容量，还有一种情况就是扩容后不需要位移的场景。
00000000000000000000000000001111 --> 15
00000000000000000000000000011111 --> 31
00000000000000000000000000110100 --> 52
00000000000000000000000000000100 --> 15 & 52 --> i = 4
00000000000000000000000000010100 --> 31 & 52 --> i = 20
JDK7和JDK8实现的区别
JDK8相比于JDK7，HashMap主要做了如下优化：
- 数据结构：由数组+链表改成了数组+链表/红黑树，查找的时间复杂度为O(1) ~ O(logN) ~ O(n)。
- 插入方式：1.7采用头插法，头插法会使链表发生反转，多线程环境下会产生环，并且会产生死循环、数据丢失、数据覆盖的问题，1.8采用尾插法会产生数据覆盖问题。
- 扩容方式：1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1.8 采用更简单的判断逻辑，位置不变或索引+旧容量大小。
- 扩容时机：1.7 先判断是否需要扩容，再插入，JDK1.8 先进行插入，插入完成再判断是否需要扩容。
头插法和尾插法的区别
JDK7进行添加元素时调用put方法，查看源码：
public V put(K key, V value) {
// 如果table未进行初始化，先进行初始化
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 如果key为null，添加一个null-value的entry
if (key == null)
return putForNullKey(value);
// 扰动函数计算key的hashcode
int hash = hash(key);
// 计算key在table中的索引位置
int i = indexFor(hash, table.length);
// 对链表进行遍历，使用临时节点e记录table[i]，使用e=e.next进行链表驱动，从头部开始遍历
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 如果链表中的key与put的key相等，用新的value替换oldValue，并返回oldValue
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 如果链表中不包含当前key，添加当前key-value组成的entry
addEntry(hash, key, value, i);
return null;
}
头插法看起来的优势就是插入节点的性能高，速度较快，但是也有其劣势，在多线程插入触发HashMap扩容时，有可能会引起链表反转，出现环形链表，出现死循环，使得CPU负载飙升。
头插法其实会改变链表的顺序，触发链表环化，JDK8中使用尾插法，不会对链表的顺序进行改变。
扩容实现的差别
JDK7中的扩容是在添加元素前进行扩容，扩容大小为原数组长度的2倍。
void addEntry(int hash, K key, V value, int bucketIndex) {
// 当size>阈值，并且table索引处的元素不为空会触发扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
// 扩容的大小为原来table的2倍
resize(2 * table.length);
// 扩容后对key的hashcode重新计算
hash = (null != key) ? hash(key) : 0;
// 重新确定key在table中的索引位置
bucketIndex = indexFor(hash, table.length);
}
// 创建新的节点
createEntry(hash, key, value, bucketIndex);
}
// 扩容实现
void resize(int newCapacity) {
// 声明临时变量oldTable指向当前table
Entry[] oldTable = table;
// 声明临时变量oldCapacity记录当前table的长度
int oldCapacity = oldTable.length;
// 如果当前的容量达到了最大值MAXIMUM_CAPACITY，阈值为Integer.MAX_VALUE，不再扩容
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 创建一个指定长度为newCapacity的数组
Entry[] newTable = new Entry[newCapacity];
// 进行元素迁移，执行initHashSeedAsNeeded方法判断是否需要rehash
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 将成员变量table指向扩容后的newTable
table = newTable;
// 计算新的阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
// 添加元素节点
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
// 采用头插法，使得当前的链表头节点变成新插入节点的后继节点
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
迁移元素的代码实现，查看transfer方法的源码：
void transfer(Entry[] newTable, boolean rehash) {
// 声明newCapacity记录新的容量值
int newCapacity = newTable.length;
// 外层对table中Entry进行遍历，即数组遍历
for (Entry<K,V> e : table) {
// 内层对table对应位置的链表进行遍历，直到遍历到链表的尾部
while(null != e) {
// 声明next记录e的下一个节点用于接下来的遍历
Entry<K,V> next = e.next;
// 判断是否需要对key重新进行扰动函数hashcode计算
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 根据hashcode计算下标位置
int i = indexFor(e.hash, newCapacity);
// 对链表进行操作，e的next指向扩容后newTable[i]的位置
// 如果i位置没有元素，e.next=null
e.next = newTable[i];
// newTable在i处的节点指向e，元素e被头插入新的下标位置，完成迁移
newTable[i] = e;
// 继续驱动链表遍历
e = next;
}
}
}
通过与JDK8扩容对比可以发现，JDK7的实现在扩容时会对元素进行hashcode重新计算，并确定下标位置，而且JDK7中都hash扰动函数会进行多次位运算，本身效率也不如JDK8中的扰动函数效率。JDK8中对于元素的迁移处理则比较巧妙。
查看JDK7中hash扰动函数的计算方式，进行了四次位运算，在数据量较大时会影响HashMap的效率。
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
多线程扩容为什么不安全
在多线程操作中如果刚好达到临界点，在JDK7中最严重时会触发链表的环化，形成死循环。
如图所示：图中简单演示了如何出现链表循环的场景，当线程1在执行时，此时e指向A，next指向B，然后线程时间片不够被挂起，线程2在执行时进行了扩容，扩容后进行rehash，元素下标位置进行变化，此时线程1又被唤醒执行，由于线程1原来指向A且在下标0处，使用头插法，又重新将节点插入，形成循环。
在JDK1.8中使用了尾插法，避免了多线程操作链表反转的情况，但是多线程并发执行时，线程1在执行到替换元素值或者存放元素时被挂起，线程2操作了同样的key，并且值被设置，等待线程1被唤醒，会将线程2的值覆盖。
因此在多线程操作下除去JDK7中头插法出现的死循环外，HashMap本身也是线程不安全的，如果需要使用线程安全的Map，可以使用锁或者ConcurrentHashMap。
什么是rehash
rehash主要针对JDK7中的key的hashcode计算规则，在HashMap进行扩容时，元素迁移主要依赖transfer方法实现。
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
// 这里有一个rehash的判断，在扩容后是否需要对key进行二次hash
// 如果触发了hash函数，由于hashSeed的变化，因此对同一个key的hashcode不一致
// 因此扩容前后key的hashcode也可能变化，根据公式i = hash & (lenght - 1)
// 对于下标的计算同时会受到hashcode和长度的影响
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
transfer传入的参数rehash是initHashSeedAsNeeded方法的返回结果，其入参为扩容后的容量。
final boolean initHashSeedAsNeeded(int capacity) {
// 首次扩容时currentAltHashing = false
boolean currentAltHashing = hashSeed != 0;
// VM.isBooted()VM是否启动，结果为true
// Holder.ALTERNATIVE_HASHING_THRESHOLD在类加载时候进行赋值，默认为Integer.MAX_VALUE
// 因此useAltHashing的结果一般为false
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
// switching由异或计算得到结果
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
// 重新对hashSeed进行赋值，默认为0
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
如果觉得HashMap自身的散列效果达不到预期效果，Holder.ALTERNATIVE_HASHING_THRESHOLD的值在虚拟机启动时可以通过参数进行指定jdk.map.althashing.threshold。其实默认情况下很少会出现符合rehash的场景。
说明：也有很多地方把
hascode & (length - 1)解释为rehash，重新散列，至于rehash是特指JDK7中指定初始化散列阈值触发对元素的hashcode重新计算，还是指在哈希表中下标的重新计算，言之有理即可。
总结
- HashMap是Java集合框架中重要的一员，在JDK7前后有着重大的改变。在JDK8其底层的数据结构实现为数组+链表或者数组+红黑树。频繁的进行扩容会触发元素迁移以及红黑树和链表的操作，会降低HashMap的性能，选择合适的初始化容量可以在一定程度上提升效率。
- HashMap是线程不安全的，如果需要保证线程安全可以使用Collections.synchronizedMap()进行包装，或者使用ConcurrentHashMap。ConcurrentHashMap的粒度是基于分段锁的，其并发性能更好。
- HashMap是基于散列算法的，使用扰动函数可以使其元素分布的更加均匀，查找元素时最理想的时间复杂度是O(1)，在引入红黑树或链表的情况下，查找元素的时间复杂度介于O(1)O(logN)O(N)之间。
参考文档：
- JDK7 & JDK8 HashMap源码
- https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
- https://blog.csdn.net/qq_34719188/article/details/83927460
- https://zhuanlan.zhihu.com/p/449337470
- https://zhuanlan.zhihu.com/p/342561761
- https://blog.csdn.net/weixin_33977645/article/details/113076222
- https://blog.csdn.net/qq_34719188/article/details/83927460
- https://cloud.tencent.com/developer/article/1794165