深入理解HashMap的底层原理

本文最后更新于 <span id="expire-date"></span> 天前，文中部分描述可能已经过时。

基本概念

HashMap类主要用来处理具有键值对特征的数据。随着JDK版本的更新，JDK 1.8 对HashMap底层进行了优化。

HashMap是基于哈希表对Map接口的实现，HashMap具有较快的访问速度，但是遍历顺序却是不确定的。

HashMap提供所有可选的映射操作，并允许使用 null值 和 null键。

new HashMap<>().put(null, null);

Hash并非线程安全，当存在多个线程同时写入HashMap时，可能会导致数据的不一致。

必知字段

loadFactor 称为负载因子，默认值为0.75
threshold 表示所能容纳的键值对的临界值
threshold 计算公式为：数组长 * 负载因子
size 是HashMap中实际存在的键值对数量
modCount 字段用来记录HashMap内部结构发生变化的次数
HashMap的默认容量 INITIAL_CAPACITY 为16

/**
 * The initial capacity -- MUST be a power of two.
 */
private static final int INITIAL_CAPACITY = 16;

/* ---------------- 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;

/**
 * Holds cached entrySet(). Note that AbstractMap fields are used
 * for keySet() and values().
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * The number of key-value mappings contained in this map.
 */
transient int size;

/**
 * The number of times this HashMap has been structurally modified
 * Structural modifications are those that change the number of mappings in
 * the HashMap or otherwise modify its internal structure (e.g.,
 * rehash).  This field is used to make iterators on Collection-views of
 * the HashMap fail-fast.  (See ConcurrentModificationException).
 */
transient int modCount;

/**
 * The next size value at which to resize (capacity * load factor).
 *
 * @serial
 */
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;

/**
 * The load factor for the hash table.
 *
 * @serial
 */
final float loadFactor;

存储结构

在JDK 1.8 中，HashMap 采用了数组 + 链表 + 红黑树的存储结构。

HashMap数组部分称为哈希桶，当链表长度大于等于`` 8 时，链表数据将以 红黑树 的形式进行存储，当长度降到 6 时，转为链表。

链表的时间复杂度为O(n)；
红黑树的时间复杂度为O(logn)；

每个Node节点存储着用来定位数据索引位置的hash值，k键，v值以及指向链表下一个节点的 Node<K, V> next 节点组成。

Node 是 HashMap的内部类，实现了Map.Entry接口，本质是一个键值对。

 /**
 * 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;

当向 HashMap 中插入数据时，首先要确定在哈希桶中的位置，那么如何确定Node的存储位置呢？

static final int hash(Object key) {
	int h;
	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

以添加key键为字符 ‘e’ 为例：

HashMap首先调用 hashCode() 方法，获取键key的hashCode值 h(101)，然后对其进行高位运算：

将 h 右移16位以取得h的高16位，与原 h 的低16位进行异或运算（结果为 101）

最后将得到的 h值与（table.length - 1）进行与运算获得该对象的保留位以计算下标。

HashMap<Character, Integer> hashMap = new HashMap<>();
hashMap.put(K, V);

例如存放键key分别为 ‘a’, ‘b’, ‘c’, ‘d’, ‘r’, ‘t’, ‘e’, ‘a’, ‘g’, ‘i’ 对象，

通过计算知：

‘a’ 的下标为 1(0001)
‘b’ 为 2(0010),
‘d’ 为 4(0100),
‘r’ 为 2(0010),
‘t’ 为 4(0100),
‘e’ 为 5(0101)

当HashMap调用 put() 方法插入键为字符的对象时：

HashMap键的输出顺序为：a, b, r, d, t, e, g, i

当插入第二个以’a’为key的对象时，将新值赋值给’a’的值；

当插入的对象大小超过临界值时，HashMap将新建一个桶数组，并重新赋值（jdk1.7 和 jdk1.8 重新赋值方式略有不同）

HashMap键的输出顺序为：null, a, b, d, e, f, g, i, j, k, r, t, u, w

面试常问

面试官：在日常开发中，JDK 中包含的集合几乎我们每天都会用到，那么你可以简单地说一下Java的集合容器包含了哪些吗？【Java集合容器包含了哪些？】

答：主要是三个接口：List、Set、Map，以及实现了这些接口的诸多子类。

面试官：那他们三个都是对Collection接口的实现吗？

答：不是的，List、Set是实现了Collection接口，Map是单独的接口，只不过当我们在谈到这个JDK的容器的时候，经常会把这三者放在一起谈。

面试官：你能简单说说这三者在概念上的差别吗？【List、Set、Map的基本区别】

答：List是有序的，这个有序指的是插入元素的顺序，其中呢可以存放重复的值和null值；Set呢它是无序的，其中的值是各不相同的，所以呢它里面只能存放一个null值；Map呢它存放的是Entry键值对，键呢必须是唯一的，所以说在Map里面只能存放一个键为null的值，但是可以存放多个值为null的Entry。

面试官：在Map中最常用的要数HashMap，关于HashMap，你能说说你的理解吗？【HashMap的基本概念】

答：关于HashMap，正如它的名字那样，它的key是通过hashCode来进行存储的，这又要谈到它的内部结构了，HashMap内部的数据结构呢主要用到了三种，一种就是数组，然后是链表，以及在JDK8中为了提升它的查询速度呢，加入的红黑树结构。

面试官：你可以具体的讲一下吗？

答：可以看我画的这张图更加直观一些。我来介绍一下HashMap中的数据结构，首先呢HashMap维护了一个数组，数组中存储的元素类型为Entry，Entry就是键值对，当每一个Entry要被添加到Map中时，首先要使用Hash算法来计算它的hashCode【计算的是key的hashCode】，然后对hashCode进行取模操作，比如entryA取到的模是1，entryB取到的是0，entryC取到的是3，那么根据这个值来添加到对应的数组中的位置，这样呢就不难发现，添加的过程中hash算法是比较重要的，加入一个Hash算法比较优秀的话呢，它计算出来的hashCode是比较分散比较均匀的，所以每一个元素都能均匀地分布在数组中，这样的呢，就认为这个hash算法是优秀的，然后它的查找时间复杂度就是O(1)，如果这个Hash算法比较差呢，那么它可能计算出来的hashCode取模的结果都是一样的，那么整个数组就会退化成一个链表，那么它的查询速度就会变成O(n)，这样的话它们的查询效率差异将会是非常大的。JDK 1.8 中对此做了一些优化，就是说当一个数组的节点上挂载的node的数值超过8时，就将这个链表转化成红黑树，那红黑树的查询速度是O(logn)，这样呢就起到了一定的优化作用。

面试官：那为什么这个临界值设置为8呢？

答：至于这个临界值为什么是8呢，这个是和泊松分布有关的，为什么这么设计呢？这也是类库的开发者在性能和空间开销上的一个取舍。

面试官：看过具体的源码吗？说说它的实现方式吧。【HashMap中的元素Node的源码分析】

答：之前提到了HashMap的数据结构是数组 + 链表，其中数组中存储的元素叫Node，那么我们就来说一下Node吧！

Node是对Entry的一个实现，Entry是一个接口，Node是它的一个实现类，那我们接下来再看一下Node的源码！

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;
	}

	public final K getKey()        { return key; }
	public final V getValue()      { return value; }
	public final String toString() { return key + "=" + value; }

	public final int hashCode() {
		return Objects.hashCode(key) ^ Objects.hashCode(value);
	}

	public final V setValue(V newValue) {
		V oldValue = value;
		value = newValue;
		return oldValue;
	}

	public final boolean equals(Object o) {
		if (o == this)
			return true;
		if (o instanceof Map.Entry) {
			Map.Entry<?,?> e = (Map.Entry<?,?>)o;
			if (Objects.equals(key, e.getKey()) &&
				Objects.equals(value, e.getValue()))
				return true;
		}
		return false;
	}
}

那我们可以看到 Node实现了 Entry这个接口，再来看看它的属性值，一个是hash，hash就是记录它的hash值，除了key和value呢，还有一个next，next就指向这个node的下一个节点，因为它的可以被拓展成一个链表的，接下来呢我们再看看它的方法，除了getter、setter方法，我们可以看到Node重写了Object的hashCode和equals方法。

明白了Node的构成之后呢，我们再来看一下HashMap的成员属性。

/* ---------------- Fields -------------- */

    transient Node<K,V>[] table;

    transient Set<Map.Entry<K,V>> entrySet;

    transient int size;

    transient int modCount;

    int threshold;

    final float loadFactor;

从它的源码可以来看一看，除了我们之前提到的 table，它是一个node数组之外呢，还有 entrySet，size，modCount，threshold，loadFactor 这几个属性。

一一来解释下，可以看到这个Set的泛型是 Map.Entry，它是Node的一个上层接口，主要存放Map中所有的Entry，便于用来进行遍历等操作；

size 是 table 中被使用的实际元素的数量；

modCount 是一个计数器，它主要用来记录HashMap结构发生变化的次数，比如put了一个新的key，发生了扩容等等；

threshold = size * loadFactor；

loadFactor 是负载因子，在下面扩容机制的时候会详细介绍这个属性的作用。默认值它是 0.75。

面试官：不好意思，打断一下，transient 这个修饰符不是很常见，你能介绍一下它的作用吗？【笔记5：transient修饰符的作用】

答：transient 到底是干什么用的呢，是这样子的，Java中有个Serilizable 接口，就是当一个类实现了这个接口之后，它就能进行自动序列化，那么什么是自动的序列化呢？就是说Java进程之间在进行对象传输的时候，或者说对对象进行持久化等操作的时候呢，就要将这个对象序列化成二进制流，然后便于传输或者进行存储。那transient 修饰了一个属性之后呢，该属性将不会被自动序列化，比如一些敏感的字段，类库开发者是不希望它被序列化的。

private int a;
private transient int b;

比如说有一个对象它有一个private的属性int是a，然后它还有一个transient的int类型的属性b，那么它序列化之后保存到本地文件上，之后再进行序列化成对象的时候，这个属性b将会消失，因为它是不可见的。

面试官：好的，你说的没错，那么接下来我们再回归正题吧，我们知道table是一个数组，数组是在初始化指定长度的，无法动态扩展，但是呢在实际业务中我们往往无法预测它的未来长度，那么这点HashMap是如何解决的呢？【笔记6：核心重点：HashMap扩容机制】

答：接下来我就结合上述几个属性来介绍一下HashMap比较核心的扩容机制吧，首先谈谈扩容的时机，就是HashMap在什么情况下才会扩容。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;

从源码中这两行我们可以得知，HashMap默认初始化长度是16，它的默认负载因子是0.75，那么负载因子是用来干嘛的呢？

当table中的元素被使用到了75%以上的时候呢，将会进行扩容，那么threshold指的就是这样一个临界值，它等于 size * loadFactor。

当table中元素个数达到这个threshold 之后将会进行扩容，每次扩容都是成倍的，即扩容之后table大小是之前的两倍，扩容属于一个比较消耗资源的操作，它需要为数组分配更多的空间。但是呢，它的好处就是说，因为你的数组更长了，所以hash算法的结果能够更均匀，它的碰撞也会更少，那么个数与碰撞的几率是服从泊松分布的，就是发现在0.75处碰撞的几率是最小的，所以使用0.75作为默认的负载因子。当然，如果面临特殊的业务情况下，开发者是可以手动控制负载因子的，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);
}

面试官：那么你能谈一谈负载因子的默认值为什么是0.75，而它扩容的时候又是成倍增加的呢？你能去揣测一下开发者他为什么这么设计吗？【笔记7：为什么HashMap扩容，每次长度都是 * 2】

答：至于为什么table的长度一定是2的次幂，是为了在取模的时候做优化，当判断一个元素进入哪一个桶的时候，需要对key的hash值进行取模（%），但是 % 是一个比较重的操作，它比较耗性能，而当数组的长度总是2的n次方时，h & (length - 1) 运算等价于对 length 取模（下面会讲到），相较于 %，& 操作性能更好。

为什么呢？因为它是位运算操作，直接对二进制数据计算，而 % 需要将hash值转化为十进制后再计算。所以 & 在性能上有很大优势，可以看一下下面两段代码：

static final int hash(Object key) {
	int h;
	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

...
Node<K,V> e;
if ((e = oldTab[j]) != null) {
	oldTab[j] = null;
	if (e.next == null)
		newTab[e.hash & (newCap - 1)] = e;
                ...

可以看到，Node中的hash属性都是通过上面的hash函数计算出来的，那么为什么在计算key的hash值的时候，为什么要将key的hash值右移16位，然后再进行异或操作？

这其实也是HashMap设计中的一个细节，在扩容时，将旧 old table 中的元素添加到 new table 时，使用了 newTab[e.hash & (newCap - 1)] = e; 这样的操作.

面试官：上面你聊到了hash算法的源码，那么能介绍一下，为什么HashMap要在Object的hashCode的基础上，进行异或和右移的操作呢 (h = key.hashCode()) ^ (h >>> 16); ，这样有什么好处？【笔记8：在取模之前，进行右移和异或的好处】

答：将key的hash值无符号右移16位，然后再与旧值进行异或操作，主要是为了保留高位和低位的信息，这样就能够表现目标值的特征，这样能够减少碰撞。

假如A的值是 11101110，当它与 111 进行 & 运算的时候，它的高四位的信息将会全部丢失，因为 & 111 的高四位全都是0，所以得出的结果就是 110。

A 11101110  & 00000111 （111）= 00000110 （110）
^ 00001110
   11100000  & 00000111 （111）=  00000000（000）

异或（^）相同取0，不同取1
&：全1才1

System.out.println(Integer.toBinaryString(0b00001110 ^ 
0b11100000));

那么我们首先对 A 进行右移四位的操作之后呢，将会得到 00001110 这个值，然后再将旧的值和新的值进行异或操作之后呢，将会得到 11101110，再用这个值与 (length - 1) 进行& 操作之后呢，我们会发现得到了一个不一样的结果：00000000，这个结果作为A的模就更加具有代表性，因为它混合了A的高四位和低四位之间的信息。

面试官：那你能解释下为什么“当数组的length总是2的n次方时，h & (length - 1)运算等价于对length取模”呢？【笔记9：为什么 h % length == h & (length - 1)】

答：为什么length对hash值取模的结果和 hash值对(length - 1) 做 & 之后的结果是一样的呢，那首先我们需要知道一个概念，对无符号数取模和取余是一样的，设length 为 2^n，那么hash值对2^n取余，就是将x的二进制表示右移n位，结果就是商，移动的n位则是余数，当 length 为 2^n，则 2 ^(n - 1) 的二进制表示等于 n 个 1，与之做与操作，结果是一样的。

我们假设这个hash值是：1101 1101（221），10（2），可以计算得出它的取模结果是 1。

      1101 1101（221） % 10（2）= 1

>>2 0011 0111 --> 01（1）

我们将这个hash值的二进制表示右移n位，移动的其实就是最后两位 01（1），01就是余数，01的十进制表示就是1，这和我们刚才计算得出的1是一致的。

那么我们在用hash对(length - 1)进行&操作：10 - 1 其实就是十进制的 2- 1，得出的二进制结果是01，那么我们对 11011101 与 01 做 & 操作，得出的结果也是01，那么它的十进制表示也是1。

面试官：那么接下来你可以说一下，一个元素put的整个流程吗？【笔记10：put操作的流程】

public V put(K key, V value) {
	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;
	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;
}

在这张图中最重要的是我们需要知道如果table为空，或是length为0，那么HashTable将会扩容，其他的情况实在插入之后再进行扩容。

面试官：那么关于HashMap的最后一个重点，可以介绍一下它的线程安全情况吗？【笔记11：HashMap线程不安全】

答：首先先说结论：HashMap不是线程安全的，因为我们看它的源码可以知道，它的很多操作都不是使用 synchronized 来进行同步的。

void resize(int newCapacity) {
	Entry<K,V>[] oldTable = getTable();
	int oldCapacity = oldTable.length;
	if (oldCapacity == MAXIMUM_CAPACITY) {
		threshold = Integer.MAX_VALUE;
		return;
	}

	Entry<K,V>[] newTable = newTable(newCapacity);
	transfer(oldTable, newTable);
	table = newTable;

	if (size >= threshold / 2) {
		threshold = (int)(newCapacity * loadFactor);
	} else {
		expungeStaleEntries();
		transfer(newTable, oldTable);
		table = oldTable;
	}
}

首先呢我们来看它的resize这个源码，resize逻辑很简单，其实就是将旧数组中的元素通过转换之后将其填充到新数组之中，那么关键就是这个transfer这个函数方法.

/** Transfers all entries from src to dest tables */
private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
	for (int j = 0; j < src.length; ++j) {
		Entry<K,V> e = src[j];
		src[j] = null;
		while (e != null) {
			Entry<K,V> next = e.next;
			Object key = e.get();
			if (key == null) {
				e.next = null;  // Help GC
				e.value = null; //  "   "
				size--;
			} else {
				int i = indexFor(e.hash, dest.length);
				e.next = dest[i];
				dest[i] = e;
			}
			e = next;
		}
	}
}

刚才也提到了transfer函数主要是将旧数组中的元素填充到新数组中去，那么我们这边假设一个旧数组的长度是2，它扩容之后的数组长度是4。

HashMap在扩容的时候是如何产生线程安全问题的，假设我们有两个线程thread1和thread2，首先我们需要明确几个概念，newTable这些变量都是在当前线程栈中的，所以它是跟线程无关的，它是线程独立的，但是node这些节点是在堆内存中分配的，不同的线程是可以对它进行操作，那么就会存在线程同步问题。

JDK 1.7中是 头插法

本文作者：ZYang

本文链接： https://luziyangde.cn/2021/03/09/%E6%B7%B1%E5%85%A5%E7%90%86%E8%A7%A3HashMap%E7%9A%84%E5%BA%95%E5%B1%82%E5%8E%9F%E7%90%86/

文章默认使用 CC BY-NC-SA 4.0 协议进行许可，使用时请注意遵守协议。

更新于 2022-12-04 11:23

# HashMap # 源码分析