本文最后更新于 <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.75threshold表示所能容纳的键值对的临界值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
文章默认使用 CC BY-NC-SA 4.0 协议进行许可，使用时请注意遵守协议。