深入浅出集合框架（一）：HashMap 的底层实现原理

前言

哈希表（hash table）也叫散列表，是一种非常重要的数据结构，应用场景及其丰富，许多缓存技术（比如 memcached）的核心其实就是在内存中维护一张大的哈希表，而 HashMap 的实现原理也常常出现在各类的面试题中，重要性可见一斑。随着 JDK（Java Developmet Kit）版本的更新，JDK 1.8 对 HashMap 底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。本文结合 JDK 1.7 和 JDK 1.8 的区别，深入探讨 HashMap 的结构实现和功能原理。

什么是哈希表？

散列表（Hash table，也叫哈希表），是根据关键码值（Key value）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表 M，存在函数 f(key)，对任意给定的关键字值 key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表 M 为哈希 (Hash）表，函数 f(key) 为哈希 (Hash) 函数。

数据结构

在讨论哈希表之前，我们先大概了解下其他数据结构在新增，查找等基础操作执行性能。

• 数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为 O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为 O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为 O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为 O(n)。
• 线性链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为 O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为 O(n)。
• 二叉树：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为 O(logn)。
• 哈希表：哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为 O(1)，接下来我们就来看看哈希表是如何实现达到惊艳的常数阶 O(1)的。

物理存储结构

我们知道，数据结构的物理存储结构只有两种：顺序存储结构（数组存储）和链式存储结构（链表存储）。

• 数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为 O(1)；数组的特点是：寻址容易，插入和删除困难；
• 链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达 O(n)。链表的特点是：寻址困难，插入和删除容易。

综合这两者的优点，摒弃缺点，哈希表就诞生了，既满足了数据查找方面的特点，占用的空间也不大。比如我们要新增或查找某个元素，我们通过把当前元素的关键字通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。

哈希冲突

然而万事无完美，如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。

数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？哈希冲突的解决方案有多种：

• 开放定址法（当发生地址冲突的时候，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止）
• 再散列函数法（同时构造多个不同的哈希函数，当发生冲突时，使用第二个、第三个…… 哈希函数计算地址，直到无冲突时）
• 链地址法（将所有关键字为同义词的记录存储在同一线性链表中）
• 建立公共溢出区（将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表）

HashMap 即是采用了链地址法，也就是数组 + 链表的方式。

HashMap 实现原理

Java 为数据结构中的映射定义了一个接口 java.util.Map，此接口主要有四个常用的实现类，分别是 HashMap、Hashtable、LinkedHashMap 和 TreeMap，类继承关系如下图所示：

下面针对各个实现类的特点做一些说明：

(1) HashMap：它根据键的 hashCode 值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为 null，允许多条记录的值为 null。HashMap 非线程安全，即任一时刻可以有多个线程同时写 HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections 的 synchronizedMap 方法使 HashMap 具有线程安全的能力，或者使用 ConcurrentHashMap。

(2) Hashtable：Hashtable 是遗留类，很多映射的常用功能与 HashMap 类似，不同的是它承自 Dictionary 类，并且是线程安全的，任一时间只有一个线程能写 Hashtable，并发性不如 ConcurrentHashMap，因为 ConcurrentHashMap 引入了分段锁。Hashtable 不建议在新代码中使用，不需要线程安全的场合可以用 HashMap 替换，需要线程安全的场合可以用 ConcurrentHashMap 替换。

(3) LinkedHashMap：LinkedHashMap 是 HashMap 的一个子类，保存了记录的插入顺序，在用 Iterator 遍历 LinkedHashMap 时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。

(4) TreeMap：TreeMap 实现 SortedMap 接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用 Iterator 遍历 TreeMap 时，得到的记录是排过序的。如果使用排序的映射，建议使用 TreeMap。在使用 TreeMap 时，key 必须实现 Comparable 接口或者在构造 TreeMap 传入自定义的 Comparator，否则会在运行时抛出 java.lang.ClassCastException 类型的异常。

对于上述四种 Map 类型的类，要求映射中的 key 是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化，Map 对象很可能就定位不到映射的位置了。

通过上面的比较，我们知道了 HashMap 是 Java 的 Map 家族中一个普通成员，鉴于它可以满足大多数场景的使用条件，所以是使用频度最高的一个。下文我们主要结合源码，从存储结构、常用方法分析、扩容以及安全性等方面深入讲解 HashMap 的工作原理。

HashMap 存储结构

在 JDK1.6、JDK 1.7 中，HashMap 采用数组 + 链表实现，即使用链表处理冲突，同一 hash 值的元素都存储在一个链表里。但是当位于一个桶中的元素较多，即 hash 值相等的元素较多时，通过 key 值依次查找的效率较低。而 JDK 1.8 中，HashMap 采用数组 + 链表 + 红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间；当链表长度小于链表还原阈值（6）时，将红黑树转换为链表。

Node：Node<K, V> 类用来实现数组及链表的数据结构。Node 是 HashMap 的一个内部类，实现了 Map.Entry 接口，本质是就是一个映射(键值对)。

static class Node<K, V> implements Map.Entry<K, V> {
    // 保存节点的 hash　值
    final int hash;
    // 保存节点的　key　值
    final K key;
    // 保存节点的　value 值
    V value;
    // 指向链表结构下的当前节点的　next 节点, 红黑树　TreeNode　节点中也有用到
    Node<K, V> next;  

    Node(int hash, K key, V value, Node<K, V> next) { ...}

    public final K getKey() { ...}

    public final V getValue() { ...}

    public final String toString() { ...}

    public final int hashCode() { ...}

    public final V setValue(V newValue) { ...}

    public final boolean equals(Object o) { ...}
}

TreeNode：TreeNode<K, V> 继承 LinkedHashMap.Entry<K, V>，用来实现红黑树相关的存储结构。

static final class TreeNode<K, V> extends LinkedHashMap.Entry<K, V> {
    // 存储当前节点的父节点
    HashMap.TreeNode<K, V> parent;  // red-black tree links
    // 存储当前节点的左孩子
    HashMap.TreeNode<K, V> left;
    // 存储当前节点的右孩子
    HashMap.TreeNode<K, V> right;
    // 存储当前节点的前一个节点
    HashMap.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 各常量、成员变量作用　

HashMap 各常量

// 创建 HashMap 时未指定初始容量情况下的默认容量, 即默认的数组长度 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

// HashMap 的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

// HashMap 默认的装载因子, 当 HashMap 中元素数量超过 容量 * 装载因子 时, 进行　resize()　操作
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 用来确定何时将解决 hash 冲突的链表转变为红黑树
static final int TREEIFY_THRESHOLD = 8;

// 用来确定何时将解决 hash 冲突的红黑树转变为链表
static final int UNTREEIFY_THRESHOLD = 6;

// 当需要将解决 hash 冲突的链表转变为红黑树时, 需要判断下此时数组容量, 若是由于数组容量太小（小于　MIN_TREEIFY_CAPACITY）导致的 hash 冲突太多, 则不进行链表转变为红黑树操作, 转为利用　resize() 函数对　hashMap 扩容[为了避免进行扩容、树形化选择的冲突]
static final int MIN_TREEIFY_CAPACITY = 64;

HashMap 各成员变量

// 保存 Node<K,V > 节点的数组
transient Node<K, V>[] table;

// 由 hashMap 中 Node<K,V>　节点构成的 set
transient Set<Map.Entry<K, V>> entrySet;

// 记录 hashMap 当前存储的元素的数量
transient int size;

// 记录　hashMap 发生结构性变化的次数（注意　value 的覆盖不属于结构性变化）
transient int modCount;

// threshold 的值应等于 table.length * loadFactor, size 超过这个值时进行　resize()扩容
int threshold;

// 记录 hashMap 装载因子
final float loadFactor;

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;
　  /* tableSizeFor(initialCapacity)　方法返回的值是最接近 initialCapacity 的 2 的幂, 若指定初始容量为９, 则实际 hashMap 容量为 16 */
　  // 注意此种方法创建的 hashMap 初始容量的值存在　threshold 中
    this.threshold = tableSizeFor(initialCapacity);
}

// tableSizeFor(initialCapacity)　方法返回的值是最接近 initialCapacity 的 2 的幂
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;
}

HashMap 源码分析

根据 key 获取哈希桶数组索引位置

不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。前面说过 HashMap 的数据结构是数组和链表的结合，所以我们当然希望这个 HashMap 里面的元素位置尽量分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用 hash 算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，不用遍历链表，大大优化了查询的效率。HashMap 定位数组索引位置，直接决定了 hash 方法的离散性能。

Hash 算法本质上就是三步：取 key 的 hashCode 值、高位运算、取模运算。

/**
 * 计算 hash 值[JDK 1.8 & JDK 1.7]
 * 在 JDK 1.8 的实现中, 优化了高位运算的算法, 通过 hashCode()的高 16 位异或低 16 位实现的:(h = k.hashCode()) ^ (h >>> 16),
 * 主要是从速度、功效、质量来考虑的, 这么做可以在数组 table 的 length 比较小的时候, 也能保证考虑到高低 Bit 都参与到 Hash 的计算中, 同时不会有太大的开销。
 */
static final int hash(Object key) {
    int h;
    // h = key.hashCode() 为第一步 取 hashCode 值
    // h ^ (h >>> 16)  为第二步 高位参与运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

/**
 * 取模运算[JDK 1.7 的源码, JDK 1.8 没有这个方法, 但是实现原理一样的]
 * 它通过 h & (table.length -1)来得到该对象的保存位,
 * 而 HashMap 底层数组的长度总是 2 的 n 次方, 这是 HashMap 在速度上的优化。
 * 当 length 总是 2 的 n 次方时, h & (length - 1)运算等价于对 length 取模, 也就是 h%length, 但是 & 比 % 具有更高的效率
 */
static int indexFor(int h, int length) {
    // 第三步 取模运算
    return h & (length - 1);
}

HashMap put()及其相关方法

HashMap 的 put 方法执行过程可以通过下图来理解。

1、判断键值对数组 table[i]是否为空或为 null，否则执行 resize()进行扩容；

2、根据键值 key 计算 hash 值得到插入的数组索引 i，如果 table[i]==null，直接新建节点添加，转向步骤六，如果 table[i]不为空，转向步骤三；

3、判断 table[i]的首个元素是否和 key 一样，如果相同直接覆盖 value，否则转向步骤四，这里的相同指的是 hashCode 以及 equals；

4、判断 table[i]是否为 treeNode，即 table[i]是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向步骤五；

5、遍历 table[i]，判断链表长度是否大于 8，大于 8 的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现 key 已经存在直接覆盖 value 即可；

6、插入成功后，判断实际存在的键值对数量 size 是否超多了最大容量 threshold，如果超过，进行扩容。

JDK 1.8HashMap 的 put 方法源码如下:

public V put(K key, V value) {
    // 对 key 的 hashCode()做 hash
    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;
    // 步骤一: tab 为空则创建[如果 table 还未被初始化, 那么初始化它]
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 步骤二: 计算 index, 并对 null 做处理[根据键的 hash 值找到该键对应到数组中存储的索引; 如果为 null, 那么说明此索引位置并没有被占用]
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
        // 不为 null, 说明此处已经被占用, 只需要将构建一个节点插入到这个链表的尾部即可
    else {
        Node<K, V> e;
        K k;
        // 步骤三: 节点 key 存在, 直接覆盖 value[当前结点和将要插入的结点的 hash 和 key 相同, 说明这是一次修改操作]
        if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
            // 步骤四: 判断该链为红黑树[如果 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);
                    // 链表长度大于 8 转换为红黑树进行处理
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // key 已经存在直接覆盖 value[遍历的过程中, 如果发现与某个结点的 hash 和 key, 这依然是一次修改操作 ]
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // e 不是 null, 说明当前的 put 操作是一次修改操作并且 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;
}

HashMap 扩容方法 resize()及其相关方法

扩容 (resize) 就是重新计算容量，向 HashMap 对象里不停的添加元素，而 HashMap 对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然 Java 里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更多的水，就得换大水桶。

我们分析下 resize()的源码，鉴于 JDK 1.8 融入了红黑树，较复杂，为了便于理解我们仍然使用 JDK 1.7 的代码，好理解一些，本质上区别不大，具体区别后文再说。

// 传入新的容量
void resize(int newCapacity) {
    // 引用扩容前的 Entry 数组
    Entry[] oldTable = table;    
    int oldCapacity = oldTable.length;
    // 扩容前的数组大小如果已经达到最大 (2^30) 了
    if (oldCapacity == MAXIMUM_CAPACITY) {
        // 修改阈值为 int 的最大值(2^31-1)，这样以后就不会扩容了
        threshold = Integer.MAX_VALUE; 
        return;
    }

    // 初始化一个新的 Entry 数组
    Entry[] newTable = new Entry[newCapacity];
    // 将数据转移到新的 Entry 数组里
    transfer(newTable);
    // HashMap 的 table 属性引用新的 Entry 数组
    table = newTable;
    // 修改阈值
    threshold = (int)(newCapacity * loadFactor);
}

这里就是使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有 Entry 数组的元素拷贝到新的 Entry 数组里。

void transfer(Entry[] newTable) {
    // src 引用了旧的 Entry 数组
    Entry[] src = table;                   
    int newCapacity = newTable.length;
    // 遍历旧的 Entry 数组
    for (int j = 0; j < src.length; j++) {
        // 取得旧 Entry 数组的每个元素
        Entry<K,V> e = src[j];             
        if (e != null) {
            // 释放旧 Entry 数组的对象引用（for 循环后，旧的 Entry 数组不再引用任何对象）
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                // 重新计算每个元素在数组中的位置
                int i = indexFor(e.hash, newCapacity);
                // 标记[1]
                e.next = newTable[i];
                // 将元素放在数组上
                newTable[i] = e;
                // 访问下一个 Entry 链上的元素
                e = next;            
            } while (e != null);
        }
    }
}

newTable[i]的引用赋给了 e.next，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到 Entry 链的尾部(如果发生了 hash 冲突的话），这一点和 JDK 1.8 有区别，下文详解。在旧数组中同一条 Entry 链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。

下面举个例子说明下扩容过程。假设了我们的 hash 算法就是简单的用 key mod 一下表的大小（也就是数组的长度）。其中的哈希桶数组 table 的 size=2， 所以 key = 3、7、5，put 顺序依次为 5、7、3。在 mod 2 以后都冲突在 table[1]这里了。这里假设负载因子 loadFactor=1，即当键值对的实际大小 size 大于 table 的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize 成 4，然后所有的 Node 重新 rehash 的过程。

下面我们讲解下 JDK 1.8 做了哪些优化。经过观测可以发现，我们使用的是 2 次幂的扩展(指长度扩为原来 2 倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动 2 次幂的位置。看下图可以明白这句话的意思，n 为 table 的长度，图（a）表示扩容前的 key1 和 key2 两种 key 确定索引位置的示例，图（b）表示扩容后 key1 和 key2 两种 key 确定索引位置的示例，其中 hash1 是 key1 对应的哈希与高位运算结果。

元素在重新计算 hash 之后，因为 n 变为 2 倍，那么 n-1 的 mask 范围在高位多 1bit(红色)，因此新的 index 就会发生这样的变化：

因此，我们在扩充 HashMap 的时候，不需要像 JDK 1.7 的实现那样重新计算 hash，只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了，是 0 的话索引没变，是 1 的话索引变成“原索引 + oldCap”，可以看看下图为 16 扩充为 32 的 resize 示意图：

这个设计确实非常的巧妙，既省去了重新计算 hash 值的时间，而且同时，由于新增的 1bit 是 0 还是 1 可以认为是随机的，因此 resize 的过程，均匀的把之前的冲突的节点分散到新的 bucket 了。这一块就是 JDK 1.8 新增的优化点。有一点注意区别，JDK 1.7 中 rehash 的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK 1.8 不会倒置。有兴趣的同学可以研究下 JDK 1.8 的 resize 源码，写的很赞，如下:

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) {
        // 超过最大值就不再扩充了, 就只好随你碰撞去吧
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 没超过最大值, 就扩充为原来的 2 倍
        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
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新的 resize 上限
    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) {
        // 把每个 bucket 都移动到新的 buckets 中
        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 { // 链表优化重 hash 的代码块
                    Node<K, V> loHead = null, loTail = null;
                    Node<K, V> hiHead = null, hiTail = null;
                    Node<K, V> next;
                    do {
                        next = e.next;
                        // 原索引
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 原索引 + oldCap
                        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;
                    }
                    // 原索引 + oldCap 放到 bucket 里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

HashMap 线程安全性

在多线程使用场景中，应该尽量避免使用线程不安全的 HashMap，而使用线程安全的 ConcurrentHashMap。那么为什么说 HashMap 是线程不安全的，下面举例子说明在并发的多线程使用场景中使用 HashMap 可能造成死循环。代码例子如下(便于理解，仍然使用 JDK 1.7 的环境)：

public class HashMapInfiniteLoop {

    private static HashMap<Integer, String> map = new HashMap<>(2, 0.75f);

    public static void main(String[] args) {
        map.put(5, "C");

        new Thread("Thread1") {
            public void run() {
                map.put(7, "B");
                System.out.println(map);
            }
        }.start();
        new Thread("Thread2") {
            public void run() {
                map.put(3, "A");
                System.out.println(map);
            }

        }.start();
    }
}

其中，map 初始化为一个长度为 2 的数组，loadFactor=0.75，threshold=2*0.75=1，也就是说当 put 第二个 key 的时候，map 就需要进行 resize。

通过设置断点让线程 1 和线程 2 同时 debug 到 transfer 方法 (3.3 小节代码块) 的首行。注意此时两个线程已经成功添加数据。放开 thread1 的断点至 transfer 方法的“Entry next = e.next;” 这一行；然后放开线程 2 的的断点，让线程 2 进行 resize。结果如下图。

注意，Thread1 的 e 指向了 key(3)，而 next 指向了 key(7)，其在线程二 rehash 后，指向了线程二重组后的链表。

线程一被调度回来执行，先是执行 newTalbe[i] = e， 然后是 e = next，导致了 e 指向了 key(7)，而下一次循环的 next = e.next 导致了 next 指向了 key(3)。

e.next = newTable[i] 导致 key(3).next 指向了 key(7)。注意：此时的 key(7).next 已经指向了 key(3)， 环形链表就这样出现了。

于是，当我们用线程一调用 map.get(11)时，悲剧就出现了—— Infinite Loop。

JDK 1.7 中 HashMap 和 JDK 1.8 中 HashMap 的实现区別？

JDK 1.8 针对 HashMap 主要优化是减少了 Hash 冲突，提高哈希表的存、取效率。

• 底层数据结构不一样：JDK 1.7 中，HashMap 采用数组 + 链表形式实现，即使用链表处理冲突，同一 hash 值的键值对会被放在同一个链表里，当链表中元素较多时，通过 key 值查找的效率较低。而 JDK 1.8 中，HashMap 采用数组 + 链表 + 红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，来把时间复杂度从 O（n）变成 O（logN），这样大大减少了查找时间。
• 初始化方式不一样：JDK 1.7 中 HashMap 的 resize()方法负责扩容，inflateTable()负责创建表；而 JDK 1.8 中 HashMap 的 resize()方法在表为空时，创建表；在表不为空时，则负责扩容。
• 插入数据方式不一样：JDK 1.7 中 HashMap 新增节点采用头插法，先将原位置的数据移到后 1 位，再插入数据到该位置；而 JDK 1.8 中 HashMap 新增节点采用尾插法。因为 JDK 1.7 中 HashMap 是用单链表进行的纵向延伸，当采用头插法时会容易出现逆序且环形链表死循环问题。但是在 JDK 1.8 中 HashMap 是因为加入了红黑树使用尾插法，能够避免出现逆序且链表死循环的问题。
• 扩容后存储位置的计算方式不一样：在 JDK 1.7 中 HashMap 扩容时全部按照原来方式进行计算，直接用 hash 值和需要扩容的二进制数进行 &（hash 值 & length-1），这里就是为什么扩容的时候为啥一定必须是 2 的多少次幂的原因所在，因为如果只有 2 的 n 次幂的情况时最后一位二进制数才一定是 1，这样能最大程度减少 hash 碰撞；而在 JDK 1.8 中 HashMap 扩容时按照扩容后的规则计算，即扩容后的位置 = 扩容前的原始位置 or 扩容前的原始位置 + 旧容量的大小值。
• 扩容时插入数据的插入时机不一样：JDK 1.7 中 HashMap 在扩容后插入数据，而 JDK 1.8 中 HashMap 在扩容前插入数据。
• hash 值计算方式不一样：在计算 hash 值的时候，JDK 1.7 中 HashMap 用了 9 次扰动处理 = 4 次位运算 + 5 次异或，而 JDK 1.8 中 HashMap 只用了 2 次扰动处理 = 1 次位运算 + 1 次异或。

扩容流程对比图：

总结

(1) 扩容是一个特别耗性能的操作，所以当程序员在使用 HashMap 的时候，估算 map 的大小，初始化的时候给一个大致的数值，避免 map 进行频繁的扩容。

(2) 负载因子是可以修改的，也可以大于 1，但是建议不要轻易修改，除非情况非常特殊。

(3) HashMap 是线程不安全的，不要在并发的环境中同时操作 HashMap，建议使用 ConcurrentHashMap。

(4) JDK 1.8 引入红黑树大程度优化了 HashMap 的性能。

简单来说，HashMap 由数组 + 链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前 entry 的 next 指向 null），那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为 O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过 key 对象的 equals()方法逐一比对查找。所以，性能考虑，HashMap 中的链表出现越少，性能才会越好。

特别感谢

特别感谢 “美团技术团队” 的知识奉献，为我解惑。

---

参考博文

[1]. 深入理解 HashMap 底层原理剖析(JDK 1.8)
[2]. Java 8 系列之重新认识 HashMap
[3]. HashMap 实现原理

---

深入浅出集合框架系列

• 深入浅出集合框架（一）：HashMap 的底层实现原理
• 深入浅出集合框架（二）：为并发而生的 ConcurrentHashMap

---