厉害了！把 HashMap 剖析的只剩渣了！

1. 装载因子决定了 HashMap 扩容的阈值，需要权衡时间与空间，一般情况下保持 0.75 不作改动；

2. HashMap 扩容机制结合了数组长度为 2 的整数次幂的特点，以一种更高的效率完成数据迁移，同时避免头插法造成链表环。

线程安全

HashMap 作为一个集合，主要功能则为 CRUD，也就是增删查改数据，那么就肯定涉及到多线程并发访问数据的情况。并发产生的问题，需要我们特别关注。

HashMap 并不是线程安全的，在多线程的情况下无法保证数据的一致性。举个例子：HashMap 下标 2 的位置为 null，线程 A 需要将节点 X 插入下标 2 的位置，在判断是否为 null 之后，线程被挂起；此时线程 B 把新的节点 Y 插入到下标 2 的位置；恢复线程 A，节点 X 会直接插入到下标 2，覆盖节点 Y，导致数据丢失，如下图：

jdk1.7 及以前扩容时采用的是头插法，这种方式插入速度快，但在多线程环境下会造成链表环，而链表环会在下一次插入时找不到链表尾而发生死循环。

那如果结果数据一致性问题呢？解决这个问题有三个方案：

• 采用 Hashtable

• 调用 Collections.synchronizeMap()方法来让 HashMap 具有多线程能力

• 采用 ConcurrentHashMap

前两个方案的思路是相似的，均是每个方法中，对整个对象进行上锁。Hashtable 是老一代的集合框架，很多的设计均以及落后，他在每一个方法中均加上了 synchronize 关键字保证线程安全。

//?Hashtable

public?synchronized?V?get(Object?key)?{...}

public?synchronized?V?put(K?key,?V?value)?{...}

public?synchronized?V?remove(Object?key)?{...}

public?synchronized?V?replace(K?key,?V?value)?{...}

...

第二种方法是返回一个 SynchronizedMap 对象，这个对象默认每个方法会锁住整个对象。如下源码：

img

这里的 mutex 是什么呢？直接看到构造器：

final?Object??????mutex;????????//?Object?on?which?to?synchronize

SynchronizedMap(Map<K,V>?m)?{

this.m?=?Objects.requireNonNull(m);

//?默认为本对象

mutex?=?this;

}

SynchronizedMap(Map<K,V>?m,?Object?mutex)?{

this.m?=?m;

this.mutex?=?mutex;

}

可以看到默认锁的就是本身，效果和 Hashtable 其实是一样的。这种简单粗暴锁整个对象的方式造成的后果是：

• 锁是非常重量级的，会严重影响性能。

• 同一时间只能有一个线程进行读写，限制了并发效率。

ConcurrentHashMap 的设计就是为了解决此问题。他通过降低锁粒度+CAS 的方式来提高效率。简单来说，ConcurrentHashMap 锁的并不是整个对象，而是一个数组的一个节点，那么其他线程访问数组其他节点是不会互相影响，极大提高了并发效率；同时 ConcurrentHashMap 读操作并不需要获取锁，如下图：

img

关于 ConcurrentHashMap 和 Hashtable 的更多内容，限于篇幅，我会在另一篇文章讲解。

那么，使用了上述的三种解决方案是不是绝对线程安全？先观察下面的代码：

ConcurrentHashMap<String,?String>?map?=?new?ConcurrentHashMap<>();

map.put("abc","123");

Thread1:

if?(map.containsKey("abc")){

String?s?=?map.get("abc");

}

Thread2:

map.remove("abc");

当 Thread1 调用 containsKey 之后释放锁，Thread2 获得锁并把“abc”移除再释放锁，这个时候 Thread1 读取到的 s 就是一个 null 了，也就出现了问题了。所以 ConcurrentHashMap 类或者 Collections.synchronizeMap()方法或者 Hashtable 都只能在一定的限度上保证线程安全，而无法保证绝对线程安全。

关于线程安全，还有一个 fast-fail 问题，即快速失败。当使用 HashMap 的迭代器遍历 HashMap 时，如果此时 HashMap 发生了结构性改变，如插入新数据、移除数据、扩容等，那么 Iteractor 会抛出 fast-fail 异常，防止出现并发异常，在一定限度上保证了线程安全。如下源码：

final?Node<K,V>?nextNode()?{

...

if?(modCount?!=?expectedModCount)

throw?new?ConcurrentModificationException();

...

}

创建 Iteractor 对象时会记录 HashMap 的 modCount 变量，每当 HashMap 发生结构性改变时，modCount 会加 1。在迭代时判断 HashMap 的 modCount 和自己保存的 expectedModCount 是否一致即可判断是否发生了结构性改变。

fast-fail 异常只能当做遍历时的一种安全保证，而不能当做多线程并发访问 HashMap 的手段。若有并发需求，还是需要使用上述的三种方法。

小结

1. HashMap 并不能保证线程安全，在多线程并发访问下会出现意想不到的问题，如数据丢失等

2. HashMap1.8 采用尾插法进行扩容，防止出现链表环导致的死循环问题

3. 解决并发问题的的方案有 Hashtable、Collections.synchronizeMap()、ConcurrentHashMap。其中最佳解决方案是 ConcurrentHashMap

4. 上述解决方案并不能完全保证线程安全

5. 快速失败是 HashMap 迭代机制中的一种并发安全保证

源码解析

关键变量的理解

HashMap 源码中有很多的内部变量，这些变量会在下面源码分析中经常出现，首先需要理解这些变量的意义。

//?存放数据的数组

transient?Node<K,V>[]?table;

//?存储的键值对数目

transient?int?size;

//?HashMap 结构修改的次数，主要用于判断 fast-fail

transient?int?modCount;

//?最大限度存储键值对的数目(threshodl=table.length*loadFactor)，也称为阈值

int?threshold;

//?装载因子，表示可最大容纳数据数量的比例

final?float?loadFactor;

//?静态内部类，HashMap 存储的节点类型；可存储键值对，本身是个链表结构。

static?class?Node<K,V>?implements?Map.Entry<K,V>?{...}

扩容

HashMap 源码中把初始化操作也放到了扩容方法中，因而扩容方法源码主要分为两部分：确定新的数组大小、迁移数据。详细的源码分析如下，我打了非常详细的注释，可选择查看。扩容的步骤在上述已经讲过了，读者可以自行结合源码，分析 HashMap 是如何实现上述的设计。

final?Node<K,V>[]?resize()?{

//?变量分别是原数组、原数组大小、原阈值；新数组大小、新阈值

Node<K,V>[]?oldTab?=?table;

int?oldCap?=?(oldTab?==?null)???0?:?oldTab.length;

int?oldThr?=?threshold;

int?newCap,?newThr?=?0;

//?如果原数组长度大于 0

if?(oldCap?>?0)?{

//?如果已经超过了设置的最大长度(1<<30,也就是最大整型正数)

if?(oldCap?>=?MAXIMUM_CAPACITY)?{

//?直接把阈值设置为最大正数

threshold?=?Integer.MAX_VALUE;

return?oldTab;

}

else?if?((newCap?=?oldCap?<<?1)?<?MAXIMUM_CAPACITY?&&

oldCap?>=?DEFAULT_INITIAL_CAPACITY)

//?设置为原来的两倍

newThr?=?oldThr?<<?1;?

}

//?原数组长度为 0，但最大限度不是 0，把长度设置为阈值

//?对应的情况就是新建 HashMap 的时候指定了数组长度

else?if?(oldThr?>?0)?

newCap?=?oldThr;

//?第一次初始化，默认 16 和 0.75

//?对应使用默认构造器新建 HashMap 对象

else?{???????????????

newCap?=?DEFAULT_INITIAL_CAPACITY;

newThr?=?(int)(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY);

}

//?如果原数组长度小于 16 或者翻倍之后超过了最大限制长度，则重新计算阈值

if?(newThr?==?0)?{

float?ft?=?(float)newCap?*?loadFactor;

newThr?=?(newCap?<?MAXIMUM_CAPACITY?&&?ft?<?(float)MAXIMUM_CAPACITY??

(int)ft?:?Integer.MAX_VALUE);

}

threshold?=?newThr;

@SuppressWarnings({"rawtypes","unchecked"})

//?建立新的数组

Node<K,V>[]?newTab?=?(Node<K,V>[])new?Node[newCap];

table?=?newTab;

if?(oldTab?!=?null)?{

//?循环遍历原数组，并给每个节点计算新的位置

for?(int?j?=?0;?j?<?oldCap;?++j)?{

Node<K,V>?e;

if?((e?=?oldTab[j])?!=?null)?{

oldTab[j]?=?null;

//?如果他没有后继节点，那么直接使用新的数组长度取模得到新下标

if?(e.next?==?null)

newTab[e.hash?&?(newCap?-?1)]?=?e;

//?如果是红黑树，调用红黑树的拆解方法

else?if?(e?instanceof?TreeNode)

((TreeNode<K,V>)e).split(this,?newTab,?j,?oldCap);

//?新的位置只有两种可能：原位置，原位置+老数组长度

//?把原链表拆成两个链表，然后再分别插入到新数组的两个位置上

//?不用多次调用 put 方法

else?{?

//?分别是原位置不变的链表和原位置+原数组长度位置的链表

Node<K,V>?loHead?=?null,?loTail?=?null;

Node<K,V>?hiHead?=?null,?hiTail?=?null;

Node<K,V>?next;

//?遍历老链表，判断新增判定位是 1or0 进行分类

do?{

next?=?e.next;

if?((e.hash?&?oldCap)?==?0)?{

if?(loTail?==?null)

loHead?=?e;

else

loTail.next?=?e;

loTail?=?e;

}

else?{

if?(hiTail?==?null)

hiHead?=?e;

else

hiTail.next?=?e;

hiTail?=?e;

}

}?while?((e?=?next)?!=?null);

//?最后赋值给新的数组

if?(loTail?!=?null)?{

loTail.next?=?null;

newTab[j]?=?loHead;

}

if?(hiTail?!=?null)?{

hiTail.next?=?null;

newTab[j?+?oldCap]?=?hiHead;

}

}

}

}

}

//?返回新数组

return?newTab;

}

添加数值

调用 put()方法添加键值对，最终会调用 putVal()来真正实现添加逻辑。代码解析如下：

public?V?put(K?key,?V?value)?{

//?获取 hash 值，再调用 putVal 方法插入数据

return?putVal(hash(key),?key,?value,?false,?true);

}

//?onlyIfAbsent 表示是否覆盖旧值，true 表示不覆盖，false 表示覆盖，默认为 false

//?evict 和 LinkHashMap 的回调方法有关，不在本文讨论范围

final?V?putVal(int?hash,?K?key,?V?value,?boolean?onlyIfAbsent,

boolean?evict)?{

//?tab 是 HashMap 内部数组，n 是数组的长度，i 是要插入的下标，p 是该下标对应的节点

Node<K,V>[]?tab;?Node<K,V>?p;?int?n,?i;

//?判断数组是否是 null 或者是否是空，若是，则调用 resize()方法进行扩容

if?((tab?=?table)?==?null?||?(n?=?tab.length)?==?0)

n?=?(tab?=?resize()).length;

//?使用位与运算代替取模得到下标

//?判断当前下标是否是 null，若是则创建节点直接插入，若不是，进入下面 else 逻辑

if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null)

tab[i]?=?newNode(hash,?key,?value,?null);

else?{

//?e 表示和当前 key 相同的节点，若不存在该节点则为 null

//?k 是当前数组下标节点的 key

Node<K,V>?e;?K?k;

//?判断当前节点与要插入的 key 是否相同，是则表示找到了已经存在的 key

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;?;?++ 《一线大厂 Java 面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》无偿开源 威信搜索公众号【编程进阶路】 binCount)?{

if?((e?=?p.next)?==?null)?{

p.next?=?newNode(hash,?key,?value,?null);

//?长度大于等于 8 时转化为红黑树

//?注意，treeifyBin 方法中会进行数组长度判断，

//?若小于 64，则优先进行数组扩容而不是转化为树

if?(binCount?>=?TREEIFY_THRESHOLD?-?1)?

treeifyBin(tab,?hash);

break;

}

//?找到相同的直接跳出循环

if?(e.hash?==?hash?&&

((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))

break;

p?=?e;

}

}

//?如果找到相同的 key 节点，则判断 onlyIfAbsent 和旧值是否为 null

//?执行更新或者不操作，最后返回旧值

if?(e?!=?null)?{?

V?oldValue?=?e.value;

if?(!onlyIfAbsent?||?oldValue?==?null)

e.value?=?value;

afterNodeAccess(e);

return?oldValue;

}

}

//?如果不是更新旧值，说明 HashMap 中键值对数量发生变化

//?modCount 数值+1 表示结构改变

++modCount;

//?判断长度是否达到最大限度，如果是则进行扩容

if?(++size?>?threshold)

resize();

//?最后返回 null（afterNodeInsertion 是 LinkHashMap 的回调）

afterNodeInsertion(evict);

return?null;

}

代码中关于每个步骤有了详细的解释，这里来总结一下：

1. 总体上分为两种情况：找到相同的 key 和找不到相同的 key。找了需要判断是否更新并返回旧 value，没找到需要插入新的 Node、更新节点数并判断是否需要扩容。

2. 查找分为三种情况：数组、链表、红黑树。数组下标 i 位置不为空且不等于 key，那么就需要判断是否树节点还是链表节点并进行查找。