HashMap 源码详细解析 (JDK1.8)

概要

HashMap 最早出现在 JDK 1.2 中，底层基于散列算法实现。HashMap 允许 null 键和 null 值，在计算哈键的哈希值时，null 键哈希值为 0。HashMap 并不保证键值对的顺序，这意味着在进行某些操作后，键值对的顺序可能会发生变化。另外，需要注意的是，HashMap 是非线程安全类，在多线程环境下可能会存在问题。

HashMap 底层是基于散列算法实现，散列算法分为散列再探测和拉链式。HashMap 则使用了拉链式的散列算法，并在 JDK 1.8 中引入了红黑树优化过长的链表。数据结构示意图如下：

对于拉链式的散列算法，其数据结构是由数组和链表（或树形结构）组成。在进行增删查等操作时，首先要定位到元素的所在桶的位置，之后再从链表中定位该元素。比如我们要查询上图结构中是否包含元素 35 ，步骤如下：

1. 定位元素 35 所处桶的位置， index = 35 % 16 = 3

2. 在 3 号桶所指向的链表中继续查找，发现35在链表中。

上面就是 HashMap 底层数据结构的原理，HashMap 基本操作就是对拉链式散列算法基本操作的一层包装。不同的地方在于 JDK 1.8 中引入了红黑树，底层数据结构由 数组+链表 变为了 数组+链表+红黑树 ，不过本质并未变。

源码分析

下面开始分析 HashMap 源码实现。

1. Node 节点对象

在分析具体代码前，先看 Node 节点对象，这是 HashMap 里面的一个内部类，也是 HashMap 的数据存储对象。具体源码如下：

    static class Node<K,V> implements Map.Entry<K,V> {
　　　　　// hash 值
        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; }
　　　　 // 返回：key的hashCode值和value的hashCode值进行异或运算结果
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

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

　　　　 // 判断相等的依据是，要么是同一个 Node 对象，要么是Map.Entry的一个实例，并且键键、值值都相等就返回True
　　　　 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;
        }
    }

该类继承自 Map.Entry<K, V>，每一个 Entry 就是一个键值对。该类还定一个 next 节点，用于指向下一个节点，也是单链的构成基础。

2. HashMap 继承关系

下面将直接进入源码分析，首先来看 HashMap 的继承关系：

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

继承自 AbstractMap，同时也实现了 Map, Cloneable, Serializable 三个接口。也说明了 HashMap 是可序列化，可克隆的的。Map 接口则是定义了一些常用的增删改查的方法，这样只要是实现该接口的都有相同的方法，方便大家记忆和使用。

2.1 Cloneable 接口

Java 中一个类要实现 clone 功能 必须实现 Cloneable 接口，否则在调用 clone() 时会报 CloneNotSupportedException 异常，也就是说， Cloneable 接口只是个合法调用 clone() 的标识（marker-interface）：

　　// Object   
　　protected Object clone() throws CloneNotSupportedException {
        if (!(this instanceof Cloneable)) {
            throw new CloneNotSupportedException("Class " + getClass().getName() +
                                                 " doesn't implement Cloneable");
        }
        return internalClone();
    }

Object 类的 internalClone() 方法是一个 native 方法，native 方法的效率一般来说都是远高于 Java 中的非 native 方法。这也解释了为什么要用 Object 中 clone() 方法而不是先 new 一个对象，然后把原始对象中的信息赋到新对象中，虽然这也实现了 clone 功能，但效率较低。

Object 类中的 clone() 方法还是一个 protected 属性的方法。为了让其它类能调用这个 clone() 方法，重载之后要把 clone() 方法的属性设置为public。

    // 1 默认的构造函数
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    // 2 传入一个Map集合,将Map集合中元素Map.Entry全部添加进HashMap实例中
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

    // 3 指定容量大小
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    // 4 指定容量大小和负载因子大小
    public HashMap(int initialCapacity, float loadFactor) {
        //指定的容量大小不可以小于0,否则将抛出IllegalArgumentException异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // 判定指定的容量大小是否大于HashMap的容量极限
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        // 指定的负载因子不可以小于0或为Null，若判定成立则抛出IllegalArgumentException异常
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                     loadFactor);

        this.loadFactor = loadFactor;
        // 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
        this.threshold = tableSizeFor(initialCapacity);
    }

可以根据具体场景和需求，使用不同的构造函数。一般对于第1个构造函数，大家用的比较多。不过从构造函数可以看出来的一点是，负载因子 loadFactor 是一个非常重要的参数，默认值是 DEFAULT_LOAD_FACTOR = 0.75f 。当负载因子确定后，会根据负载因子的值给 HashMap 计算一个阈值 threshold ；一旦超过阈值就会调用 resize () 方法扩容。

5. tableSizeFor 计算阈值

先看看阈值的计算方法， 需要指出的一点是：HashMap 要求容量必须是 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;
    }

tableSizeFor() 的主要功能是返回一个比给定整数大且最接近的 2 的幂次方整数。如给定 10，返回 2 的 4 次方 16.

下面分析这个算法： 

首先，要注意的是这个操作是无符号右移后，再或上原来的值。

为什么要对 cap 做减 1 操作：int n = cap - 1 ？这是为了防止，cap 已经是 2 的幂。如果 cap 已经是 2 的幂， 又没有执行这个减 1 操作，则执行完后面的几条无符号右移操作之后，返回的 capacity 将是这个 cap 的 2 倍。如果不懂，要看完后面的几个无符号右移之后再回来看看。

下面看看这几个无符号右移操作：

如果 n 这时为 0 了（经过了 cap-1 之后），则经过后面的几次无符号右移依然是 0，最后返回的 capacity 是 1（最后有个 n+1 的操作）。

这里只讨论 n 不等于 0 的情况。

第一次右移

n |= n >>> 1;

由于 n 不等于 0，则 n 的二进制表示中总会有一bit为 1，这时考虑最高位的 1。通过无符号右移 1 位，则将最高位的 1 右移了 1 位，再做或操作，使得 n 的二进制表示中与最高位的 1 紧邻的右边一位也为 1，如 000011xxxxxx。

第二次右移

n |= n >>> 2;

注意，这个 n 已经经过了 n |= n >>> 1; 操作。假设此时 n 为 000011xxxxxx ，则 n 无符号右移两位，会将最高位两个连续的 1 右移两位，然后再与原来的 n 做或操作，这样 n 的二进制表示的高位中会有 4 个连续的 1。如 00001111xxxxxx 。

第三次右移

n |= n >>> 4;

这次把已经有的高位中的连续的 4 个 1，右移 4 位，再做或操作，这样 n 的二进制表示的高位中会有8个连续的 1。如 00001111 1111xxxxxx 。

以此类推 

注意，容量最大也就是 32bit 的正数，因此最后 n |= n >>> 16; ，最多也就 32 个 1，但是这时已经大于了 MAXIMUM_CAPACITY ，所以取值到 MAXIMUM_CAPACITY 。

举一个例子说明下吧。 

注意，得到的这个 capacity 赋值给了 threshold，因此 threshold 就是所说的容量。当 HashMap 的 size 到达 threshold 这个阈值时会扩容。

但是，请注意，在构造方法中，并没有对 table 这个成员变量进行初始化，table 的初始化被推迟到了 put 方法中，在 put 方法中会对 threshold 重新计算。

上述这段计算逻辑引自 ：  HashMap方法hash()、tableSizeFor()

• 1.首先获取 Node 数组 table 对象和长度，若 table 为 null 或长度为 0，则调用 resize() 扩容方法获取 table 最新对象，并通过此对象获取长度大小

• 2.判定数组中指定索引下的节点是否为 Null，若为 Null 则 new 出一个单向链表赋给 table 中索引下的这个节点

• 3.若判定不为 Null，我们的判断再做分支

3.1 首先对 hash 和key进行匹配,若判定成功直接赋予 e

3.2 若匹配判定失败，则进行类型匹配是否为 TreeNode 若判定成功则在红黑树中查找符合条件的节点并将其回传赋给 e

3.3 若以上判定全部失败则进行最后操作，向单向链表中添加数据若单向链表的长度大于等于 8，则将其转为红黑树保存，记录下一个节点，对 e 进行判定若成功则返回旧值

• 4.最后判定数组大小需不需要扩容

主要是因为 n (HashMap 的容量) 值比较小，hash 只参与了低位运算，高位运算没有用上。这就增大了 hash 值的碰撞概率。而通过这种位运算的计算方式，使得高位运算参与其中，减小了 hash 的碰撞概率，使 hash 值尽可能散开。如何理解呢？把前面举的例子  hash = 185，n = 16，按照 HashMap 的计算方法咱们再来走一遍。

图中的 hash 是由键的 hashCode 产生。计算余数时，由于 n 比较小，hash 只有低 4 位参与了计算，高位的计算可以认为是无效的。这样导致了计算结果只与低位信息有关，高位数据没发挥作用。为了处理这个缺陷，我们可以上图中的 hash 高 4 位数据与低 4 位数据进行异或运算，即 hash ^ (hash >>> 4) 。通过这种方式，让高位数据与低位数据进行异或，以此加大低位信息的随机性，变相的让高位数据参与到计算中。此时的计算过程如下：

经过这次计算以后，发现最后的结果已经不一样了，hash 的高位值对结果产生了影响。这里为了举例子，使用了 8 位数据做讲解。在 Java 中，hashCode 方法产生的 hash 是 int 类型，32 位宽。前 16 位为高位，后16位为低位，所以要右移 16 位。

7. resize() 扩容

8. 链表树化、红黑树链化与拆分

下面这部分内容摘自 HashMap 源码详细分析(JDK1.8) 因为，觉得他这部分写得很好，所以就直接摘过来了。

JDK 1.8 对 HashMap 实现进行了改进。最大的改进莫过于在引入了红黑树处理频繁的碰撞，代码复杂度也随之上升。比如，以前只需实现一套针对链表操作的方法即可。而引入红黑树后，需要另外实现红黑树相关的操作。红黑树是一种自平衡的二叉查找树，本身就比较复杂。本篇文章中并不打算对红黑树展开介绍，本文仅会介绍链表树化需要注意的地方。至于红黑树详细的介绍，如果大家有兴趣，可以参考他的另一篇文章 - 红黑树详细分析 。

在展开说明之前，先把树化的相关代码贴出来，如下：

static final int TREEIFY_THRESHOLD = 8;

/**
 * 当桶数组容量小于该值时，优先进行扩容，而不是树化
 */
static final int MIN_TREEIFY_CAPACITY = 64;

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    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);
    }
}

/**
 * 将普通节点链表转换成树形节点链表
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 桶数组容量小于 MIN_TREEIFY_CAPACITY，优先进行扩容而不是树化
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // hd 为头节点（head），tl 为尾节点（tail）
        TreeNode<K,V> hd = null, tl = null;
        do {
            // 将普通节点替换成树形节点
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);  // 将普通链表转成由树形节点链表
        if ((tab[index] = hd) != null)
            // 将树形链表转换成红黑树
            hd.treeify(tab);
    }
}

TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}

在扩容过程中，树化要满足两个条件：

1. 链表长度大于等于 TREEIFY_THRESHOLD

2. 桶数组容量大于等于 MIN_TREEIFY_CAPACITY

第一个条件比较好理解，这里就不说了。这里来说说加入第二个条件的原因，个人觉得原因如下：

当桶数组容量比较小时，键值对节点 hash 的碰撞率可能会比较高，进而导致链表长度较长。这个时候应该优先扩容，而不是立马树化。毕竟高碰撞率是因为桶数组容量较小引起的，这个是主因。容量小时，优先扩容可以避免一些列的不必要的树化过程。同时，桶容量较小时，扩容会比较频繁，扩容时需要拆分红黑树并重新映射。所以在桶容量比较小的情况下，将长链表转成红黑树是一件吃力不讨好的事。

回到上面的源码中，我们继续看一下 treeifyBin 方法。该方法主要的作用是将普通链表转成为由 TreeNode 型节点组成的链表，并在最后调用 treeify 是将该链表转为红黑树。TreeNode 继承自 Node 类，所以 TreeNode 仍然包含 next 引用，原链表的节点顺序最终通过 next 引用被保存下来。我们假设树化前，链表结构如下：

HashMap 在设计之初，并没有考虑到以后会引入红黑树进行优化。所以并没有像 TreeMap 那样，要求键类实现 comparable 接口或提供相应的比较器。但由于树化过程需要比较两个键对象的大小，在键类没有实现 comparable 接口的情况下，怎么比较键与键之间的大小了就成了一个棘手的问题。为了解决这个问题，HashMap 是做了三步处理，确保可以比较出两个键的大小，如下：

1. 比较键与键之间 hash 的大小，如果 hash 相同，继续往下比较

2. 检测键类是否实现了 Comparable 接口，如果实现调用 compareTo 方法进行比较

3. 如果仍未比较出大小，就需要进行仲裁了，仲裁方法为 tieBreakOrder（大家自己看源码吧）

tie break 是网球术语，可以理解为加时赛的意思，起这个名字还是挺有意思的。

通过上面三次比较，最终就可以比较出孰大孰小。比较出大小后就可以构造红黑树了，最终构造出的红黑树如下：

橙色的箭头表示 TreeNode 的 next 引用。由于空间有限，prev 引用未画出。可以看出，链表转成红黑树后，原链表的顺序仍然会被引用仍被保留了（红黑树的根节点会被移动到链表的第一位），我们仍然可以按遍历链表的方式去遍历上面的红黑树。这样的结构为后面红黑树的切分以及红黑树转成链表做好了铺垫，我们继续往下分析。

8.1 split  红黑树拆分

扩容后，普通节点需要重新映射，红黑树节点也不例外。按照一般的思路，我们可以先把红黑树转成链表，之后再重新映射链表即可。这种处理方式是大家比较容易想到的，但这样做会损失一定的效率。不同于上面的处理方式，HashMap 实现的思路则是上好佳（上好佳请把广告费打给我）。如上节所说，在将普通链表转成红黑树时，HashMap 通过两个额外的引用 next 和 prev 保留了原链表的节点顺序。这样再对红黑树进行重新映射时，完全可以按照映射链表的方式进行。这样就避免了将红黑树转成链表后再进行映射，无形中提高了效率。

以上就是红黑树拆分的逻辑，下面看一下具体实现吧：

// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    /* 
     * 红黑树节点仍然保留了 next 引用，故仍可以按链表方式遍历红黑树。
     * 下面的循环是对红黑树节点进行分组，与上面类似
     */
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }

    if (loHead != null) {
        // 如果 loHead 不为空，且链表长度小于等于 6，则将红黑树转成链表
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            /* 
             * hiHead == null 时，表明扩容后，
             * 所有节点仍在原位置，树结构不变，无需重新树化
             */
            if (hiHead != null) 
                loHead.treeify(tab);
        }
    }
    // 与上面类似
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

从源码上可以看得出，重新映射红黑树的逻辑和重新映射链表的逻辑基本一致。不同的地方在于，重新映射后，会将红黑树拆分成两条由 TreeNode 组成的链表。如果链表长度小于 UNTREEIFY_THRESHOLD，则将链表转换成普通链表。否则根据条件重新将 TreeNode 链表树化。举个例子说明一下，假设扩容后，重新映射上图的红黑树，映射结果如下：

8.2 untreeify  红黑树链化

前面说过，红黑树中仍然保留了原链表节点顺序。有了这个前提，再将红黑树转成链表就简单多了，仅需将 TreeNode 链表转成 Node 类型的链表即可。相关代码如下：

final Node<K,V> untreeify(HashMap<K,V> map) {
    Node<K,V> hd = null, tl = null;
    // 遍历 TreeNode 链表，并用 Node 替换
    for (Node<K,V> q = this; q != null; q = q.next) {
        // 替换节点类型
        Node<K,V> p = map.replacementNode(q, null);
        if (tl == null)
            hd = p;
        else
            tl.next = p;
        tl = p;
    }
    return hd;
}

Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
    return new Node<>(p.hash, p.key, p.value, next);
}

上面的代码并不复杂，不难理解，这里就不多说了。

9. get 添加元素

  //这里直接调用getNode函数实现方法
  public V get(Object key) {
        Node<K,V> e;
        //经过hash函数运算 获取key的hash值
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
   
   final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //判定三个条件 table不为Null & table的长度大于0 & table指定的索引值不为Null
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //判定 匹配hash值 & 匹配key值 成功则返回 该值
            if (first.hash == hash && 
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
             //若 first节点的下一个节点不为Null
            if ((e = first.next) != null) {
                if (first instanceof TreeNode) //若first的类型为TreeNode 红黑树
                    //通过红黑树查找匹配值 并返回
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key); 
                //若上面判定不成功 则认为下一个节点为单向链表,通过循环匹配值
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                       //匹配成功后返回该值
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

10. remove 删除元素

当你看到了 get 获取元素的细节，在来看删除原理，其实大同小异。

HashMap 的删除操作并不复杂，仅需三个步骤即可完成。第一步是定位桶位置，第二步遍历链表并找到键值相等的节点，第三步删除节点。相关源码如下：

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        // 1. 定位桶位置
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 如果键的值与链表第一个节点相等，则将 node 指向该节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {  
            // 如果是 TreeNode 类型，调用红黑树的查找逻辑定位待删除节点
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                // 2. 遍历链表，找到待删除节点
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        
        // 3. 到这里，已经找到了，删除节点，并修复链表或红黑树
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
　　 // 找不到，或者没有数据，返回 null
    return null;
}

删除操作本身并不复杂，有了前面的基础，理解起来也就不难了，这里就不多说了。

11. 其他