简介

本文为我对 HashMap 实现原理的笔记整理以及一些个人理解，如若发现有错误的地方，欢迎留言指正

在不同的 Java 版本中 HashMap 的实现也略有不同，本文示例使用的 Java 版本为：“1.8.0_181”

什么是 Hash（散列函数）

Hash 音译为「哈希」，它是把任意长度的输入通过散列算法变换成固定长度的输出，这个输出称为散列值。

这种转换是一种压缩映射，也就是说散列值的空间远小于输入的空间，不同的输入可能会散列成相同的输出，所以 不可能从散列值来确定唯一的输入值。

Map: key 和 value 的映射

在了解了什么是 Hash 后，我们再来看下什么是 Map

Map 是一种最基础的数据结构，它描述的是一个 key 和 一个 value 一 一对应的数据结构。

每种高级语言都有对 Map 的定义和实现。

Map 接口的定义

Map.java

public interface Map<K,V> {···// 增加一个键值对V put(K key, V value);// 传入一个 key，并返回对应的 value// 注意此处传入的 key 的类型不同于 put 方法，不是泛型而是一个 ObjectV get(Object key);// 删除一个键值对V remove(Object key);···}

问题思考为什么 Map 中 put 方法中传入的 key 的类型是泛型，而在 get 或 remove 方法中却是 Object 类型呢？ 

HashMap的实现：数组+链表+(红黑树)

HashMap 是 Map 最常用的实现类，它是通过 key 的 hash 值来决定 value 在数组中的位置。但是上面我们也提到哈希值是有可能会重复的，也就是说不同的 key 得到的哈希值是一样的，这种情况我们称为 哈希冲突。

哈希冲突 意味着不同的 value 要放在数组的同一个位置，那么 HashMap 是如何处理这种情况的呢？

在 Java1.7 中 HashMap 主要以数组+链表的形式实现的，而到了 Java1.8 则引入了黑红树算法来优化 HashMap 的查询速度。

当发生 哈希冲突 时，HashMap 会将相同的 value 以链表的形式存放到对应的数组位置中。

如上图所示，table 的初始长度为 16，每个节点都由四个元素组成：hash、key、value 和 next，其中 next 记录着下一个节点。

举个例子：我们根据 key1 的哈希值得出它在 table 的下标位置为 0，若当前 table[0] 还未有元素则创建一个 Node1，这个 Node1 记录着 key1 的哈希值、key1、key1 对应的 value 值以及 next（默认为 null），然后将这个 Node1 放入 table[0] 的位置中

之后我们再根据 key2 的哈希值得到它在 table 的下标位置也为 0，此时 table[0] 已经存在了一个 Node1, 此时 HashMap 同样会先创建一个 Node2，接着把这个 Node2 放到 Node1 的 next 中

HashMap 源码分析

AbstractMap.java

public abstract class AbstractMap<K,V> implements Map<K,V> {...}

HashMap.java

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {...}

HashMap 继承了 AbstractMap 抽象类，而 AbstractMap 抽象类又实现了 Map 接口

阀值、负载系数、容量

在深入 HashMap 代码之前，我们先来认识 HashMap 的几个变量

HashMap.java

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {```// 初始容量 = 2的4次方 = 16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;// 最大容量 = 2的30次方static final int MAXIMUM_CAPACITY = 1 << 30;// 默认负载系数static final float DEFAULT_LOAD_FACTOR = 0.75f;// 链表树形化的阈值static final int TREEIFY_THRESHOLD = 8;   ```}

DEFAULT_INITIAL_CAPACITY 定义了 HashMap 的初始容量为 16

MAXIMUM_CAPACITY 则表示 HashMap 的最大容量为 2³⁰

比较有意思的是 DEFAULT_INITIAL_CAPACITY 和 MAXIMUM_CAPACITY 都是用位运算来定义的

HashMap.java

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {```// 默认负载系数static final float DEFAULT_LOAD_FACTOR = 0.75f;// 链表树形化的阈值static final int TREEIFY_THRESHOLD = 8;   ```// 扩容阀值int threshold;// 负载系数final float loadFactor;```}

threshold 表示 HashMap 的扩容阀值，HashMap 的初始容量为 16，当 HashMap 的容量超出阀值时则进行自动扩容操作，下次扩容的容量为当前容量的两倍

loadFactor （负载系数）则是用来计算具体的阀值

阀值 = 负载系数（默认0.75） * 容量

threshold = loadFactor * capacity

简单打个比方：一开始我们用 16mL 的瓶子装水，当瓶子里的水超出 12mL 时，这时我们就将 16mL 瓶子里的水倒进 32mL 的瓶子里，用 32mL 的瓶子继续装水。

16mL 就是初始容量，32mL 就是扩容后的容量，12mL 则是阀值。

HashMap 构造函数

    public HashMap() {// 指定负载系数为默认值this.loadFactor = DEFAULT_LOAD_FACTOR;}// 指定初始容量public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}// 放入已有的 Mappublic HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}// 指定初始容量和负载系数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;// tableSizeFor 方法返回大于输入参数且最近的2的整数次幂的数// 如：输入 10 返回 16this.threshold = tableSizeFor(initialCapacity);}

HashMap 中有四个构造函数，可以看到它们并没有一开始就初始化数组

初始化数组的操作是在放入数据时，也就是 put 方法中触发的

HashMap 中的 put 方法

HashMap.java

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {...public V put(K key, V value) {// 此处先调用了 hash 方法，得到 key 的 hash 值return putVal(hash(key), key, value, false, true);}...static final int hash(Object key) {int h;// 扰动处理：一次位运算 + 一次异或// 目的是为了尽可能的防止哈希冲突return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}...final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {...}...}

HashMap 中 putVal 方法除了前面的 hash、key、value 之外，后面还有两个形参 onlyIfAbsent 和 evict

其中 onlyIfAbsent 是用来判断当传入的 key 已存在时是否允许覆盖旧值，传 false 表示不允许覆盖

HashMap.java

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {...final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {// tab：Node 数组// p：已存在的 Node// n：数组长度// i：数组的下标位置Node<K,V>[] tab; Node<K,V> p; int n, i;// 判断数组是否为空，若为空则进行初始化操作// 此处的 table 是一个 Node 数组if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 将 key 的哈希值和(n - 1)进行"与"运算，得到下标位置 i// 判断 tab[i] 是否为 null if ((p = tab[i = (n - 1) & hash]) == null) // p = tab[i]// p 为 null 则说明当前数组的位置还未有值// 新建 Node 并指向 tab[i]tab[i] = newNode(hash, key, value, null);else {// e：已存在的 Node，Node 中的 key 与传入的 key 相同Node<K,V> e; K k;// 判断 key 是否已存在if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode) // 判断 p 是否继承于树形节点e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {// 循环查找节点for (int binCount = 0; ; ++binCount) {// 获取下一节点并判断是否为 nullif ((e = p.next) == null) {// 若下一节点为 null 则在当前节点的 next 上创建新的节点p.next = newNode(hash, key, value, null);// 判断是否超出默认长度，若超出则采用红黑树// TREEIFY_THRESHOLD：8if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 判断 key 是否已存在if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// e 不为 null 则说明 key 已存在if (e != null) {V oldValue = e.value;// 若 onlyIfAbsent 为 false 或 oldValue 为 null 则进行覆盖操作// 若 onlyIfAbsent 为 true 则不进行覆盖。可参考 putIfAbsent 方法if (!onlyIfAbsent || oldValue == null)// 将新的值覆盖到旧的值e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;// 判断是否需要扩容// 若元素个数大于阀值则进行扩容if (++size > threshold)resize();afterNodeInsertion(evict);return null;}...}

HashMap 中的 resize 方法

从 putVal 方法中我们可以看到 HashMap 在初始化或扩容时都调用了 resize 方法

接下来我们具体看下 resize 方法是如何实现的

HashMap.java

    // 用于初始化或扩容表大小// 每次以二的倍数进行扩容final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {// 若 table 长度已经等于或大于最大容量if (oldCap >= MAXIMUM_CAPACITY) {// 将 table 的阀值设为 int 的最大值threshold = Integer.MAX_VALUE;// 返回旧数组return oldTab;}// newCap // 新的 table 长度比原有多一倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // 若阈值大于0，则将 table 初始容量等于阈值newCap = oldThr;else {               // 若阈值小于等于0，则将 table 初始容量等于默认值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);}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);else { // 定义两个链：一个 lo 链，一个 hi 链Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;// 如果 (e.hash & oldCap) == 0 则插入 lo 链中if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else { // 否则插入 hi 链中if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;// 插入到 j 的位置newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;// 插入到 j + oldCap 的位置newTab[j + oldCap] = hiHead;}}}}}return newTab;}