2020-09-18

HashMap【源码分析JDK 1.8版本】

字数统计: 5.2k字 | 阅读时长: 21分

一、前言

在HashMap【源码分析-JDK1.7 版本】中，有介绍JDK1.7版本的底层源码，那么本文主要介绍JDK1.8版本的源码。

二、源码详细讲解

（一）常量与默认值

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    // 默认的初始化容量大小
	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    // 最大初始容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认加载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 转换为红黑树的临界值
    static final int TREEIFY_THRESHOLD = 8;
    // 从树退为链表的临界值
    static final int UNTREEIFY_THRESHOLD = 6;
    // 转换为红黑树时，数组长度应该满足的最小长度
    static final int MIN_TREEIFY_CAPACITY = 64;
}

（二）构造方法

1、构造方法1

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(cap)计算出不小于initialCapacity的最近的2的幂作为初始容量（相当于JDK 7中的 roundUpToPowerOf2），将其先保存在threshold里
    // 当put时判断数组为空会调用resize分配内存，并重新计算正确的threshold
    this.threshold = tableSizeFor(initialCapacity);
}

2、tableSizeFor

// 将创建HashMap时指定的期望容量（其实就是哈希表中数组的长度）转换为2的幂次方
static final int tableSizeFor(int cap) {
    // 经过下面的 或、位移运算， n的地位最终都是1
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    // 返回2的幂次方数
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

3、构造方法2

public HashMap(int initialCapacity) {
    // 使用默认加载因子
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

4、构造方法3

public HashMap() {
    // 使用默认加载因子和默认初始容量
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

5、构造方法4

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

6、putMapEntries

//  将m中的所有元素添加至本HashMap中
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    // 先保存HashMap的元素个数
    int s = m.size();
    if (s > 0) {
        //  判断table是否已经初始化
        if (table == null) { // pre-size
            // 根据m的元素数量和当前表的加载因子，计算出阈值
            float ft = ((float)s / loadFactor) + 1.0F;
             // 修正阈值的边界 不能超过MAXIMUM_CAPACITY
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                // 因为用户没有指定初始容量，所以此处为计算出一个满足2的幂次方的初始容量，并保存在threshold中
                // 在调用 resize() 方法的时候，才会计算真正的threshold 
                threshold = tableSizeFor(t);
        }
        // 数组已经初始化，但是要添加元素的个数大于阈值，则需要进行扩容
        else if (s > threshold)
            resize();
        //遍历 m 依次将元素加入当前表中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

（三）Put

1、put

1
2
3

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

2、hash

// 求当前key的hash值
static final int hash(Object key) {
    int h;
    // 如果当前key为null，那么直接返回0，因为之后会保存在数组的第一个位置
    // 如果不为null，则先调用key的hashCode方法，然后在将值进行位移和异或运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

3、putVal

putVal的整体思路如下：

1）在添加元素之前，先判断数组是否已经初始化或者数组是否需要扩容（resize不仅仅是扩容，还需要完成初始化的任务）

2）如果已经初始化或者不需要扩容，那么久执行添加任务，但又分为以下4种情况：

a. 对应的数组index位置还没有元素，那么直接添加；

b. 对应的数组index位置已经有元素，但是要判断是否在链表的第一个位置，即：是否存在数组中；

c. 对应的数组index位置已经有元素，但是要判断该元素是否为红黑树的一个节点；

d. 对应的数组index位置已经有元素，但是要判断是否为链表的一个节点。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // 创建一些变量
    Node<K,V>[] tab; 
    Node<K,V> p; 
    int n, i;  // n用来保存数组的长度， i用来保存数组的index
    // 如果当前数组未初始化或者长度为0，进行初始化，n为数组的长度
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 将hash转换为数组的index后，发现数组当前位置没有元素，那么直接添加
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else { // 说明数组当前index位置已经存在元素（但是又分为三种情况，需要分别判断）
        Node<K,V> e; K k;
        // p 为数组当前index位置的元素
        // 判断要添加元素的key是否等于数组当前index元素的key，如果是，就用 e 来记录下数组当前index元素 p
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 判断数组index位置的元素是否为红黑树的一个节点
        else if (p instanceof TreeNode)
            // 调用红黑树添加节点的方法
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 前面条件都不满足，那么数组index位置的元素为链表的节点
            // 这个遍历其实做了三件事情：
            // a. 判断当前要插入元素的key是否在数组index位置所对应的链表中已经存在，如果找到相同的key，则直接返回，             //    在之后的代码中将其覆盖即可
            // b. 如果没有相同的key，那么在遍历到链表的末尾时，将节点插入到链表的尾部
            // c. 在遍历到链表末尾时，其实也统计了当前链表上的元素个数，从而可以判断是否需要将链表转换为红黑树
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // 在链表末尾插入节点
                    p.next = newNode(hash, key, value, null);
                    // 根据元素个数判断是否需要转换红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) 
                        treeifyBin(tab, hash);
                    break;
                }
                // 要加入元素的key已经存在于链表中
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // 用于遍历链表，与前面的e = p.next组合，可以遍历链表
                p = e;
            }
        }
        // 不管是将元素添加到数组中，还是将元素插入到链表的末尾，还是说该key已经存在，都需要返回旧值，然后进行覆盖
        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;
}

4、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;
    // 数组长度已经大于0，说明已经初始化过，这一次resize操作时需要进行扩容
    if (oldCap > 0) {
        // 如果当前容量已经是最大容量，那么不在进行扩容，只需要将阈值调整为最大整形
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 否则，容量翻倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 阈值翻倍
            newThr = oldThr << 1; // double threshold
    }
    // 还没有进行初始化，但是用户创建HashMap时，指定的initialCapacity已经调整为2的幂次方，并且已经保存到了         threshold中，只差创建数组了
    else if (oldThr > 0) // initial capacity was placed in threshold
        // 已经有了用户指定的初始化容量，只需将其赋值给数组容量即可
        newCap = oldThr;
    // 还没有进行初始化，并且threshold中也没有值，说明在初始化时需要使用默认值
    else {               // zero initial threshold signifies using defaults
        // 初始容量、阈值都使用默认值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 此处求阈值是因为在第二种情况中（已经有了用户指定的初始化容量，但是还没有进行初始化操作），oldThr保存的是用户给的初始容量，但是初始化之后，还没有求新的阈值
    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"})
    // 在确定了新cap后（可能是初始化的，也有可能是扩容之后的），就创建一个新的数组
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    
    // 之前的table已经初始化过（说明这次resize是执行的扩容操作）
    // 2倍长度的数组在前面已经创建，所以这一部分代码的作用是将所有元素移动到新数组上（使用了2层循环进行遍历）
    if (oldTab != null) {
        // 遍历数组
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 遍历数组每个位置对应的链表
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;  // 将原数组位置置为空，应该是便于垃圾回收吧
                // 说明不是链表结构，只有一个元素，所有再重新计算index后，移动到新数组中
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 判断是否为红黑树的节点，如果是则调用移动红黑树节点的方法
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 前面两个条件都不满足，说明当前元素为链表的节点
                // // 将当前链表中的元素根据(e.hash & oldCap)是否为0进行分割成两个不同的子链表，完成移动操作
                else { 
                    // 分别指向两个子链表的头部和尾部
                    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;
                        }
                        else {  // 保留在高部分即原索引 + oldCap
                            // 第一个结点
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 将低部分的子链表保存在原索引
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 将高部分的子链表保存在原索引 + oldCap
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    // 返回 初始化/扩容 后的数组
    return newTab;
}

5、putTreeVal

该方法属于红黑树如何插入节点的问题，和HashMap的关系不大。

暂时没有仔细研究，目前我们只需要知道它会将一个节点插入到红黑树中即可。

6、treeifyBin

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 如果只是当前链表的个数大于等于树化的临界值，但是数组长度却小于64时，只会进行扩容，而不会转换为红黑树
    // （具体原因后面会讲解）
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    // 否则，将刚加入的元素所在的链表转换为红黑树
    // 以下的几行代码只是将链表节点转换为红黑树节点，然后转换为双向链表
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        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);
        
        // 到目前为止 也只是把Node对象转换成了TreeNode对象，把单向链表转换成了双向链表
        
        // 把转换后的双向链表，替换原来位置上的单向链表
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

7、treeify

该方法的解析请参考:JDK8：HashMap源码解析：put方法

（四）Get

1、get

public V get(Object key) {
    Node<K,V> e;
    // 如果找到了元素，则返回元素的value值
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

2、hash

// 求当前key的hash值
static final int hash(Object key) {
    int h;
    // 如果当前key为null，那么直接返回0，因为之后会保存在数组的第一个位置
    // 如果不为null，则先调用key的hashCode方法，然后在将值进行位移和异或运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

3、getNode

// 分为三种情况：
// 1）要查找的元素存在于数组的index位置，直接判断
// 2）要查找的元素为数组index位置的树节点类型，则调用红黑树的查找方法
// 3）要查找的元素为数组index位置的链表类型，此时会遍历当前链表进行查找
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 数组存在、数组中有元素、数组index位置不为空，三个条件都满足，才会查找
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 1）要查找的元素存在于数组的index位置，直接判断
        if (first.hash == hash && 
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 如果index位置的next不为空，说明后面要么是树节点、要么是链表节点
        if ((e = first.next) != null) {
            // 2）要查找的元素为数组index位置的树节点类型，则调用红黑树的查找方法
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                // 3）要查找的元素为数组index位置的链表类型，此时会遍历当前链表进行查找
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // 否则，直接返回null
    return null;
}

三、结构流程图

（一）Put过程

![Put方法流程图JDK8](HashMap[源码分析JDK 1.8版本]/Put方法流程图JDK8.png)
若图片不清晰，请点击在线查看

（二）resize方法

![resizeJDK8](HashMap[源码分析JDK 1.8版本]/resizeJDK8.png)
若图片不清晰，请点击在线查看

（三）Get过程

![Get方法流程图JDK8](HashMap[源码分析JDK 1.8版本]/Get方法流程图JDK8.png)
若图片不清晰，请点击在线查看

四、补充知识点

1、都知道在 JDK1.8 中 HashMap 的底层数据结构是：数组+链表+红黑树，那为什么要使用这样的数据结构呢？

1）JDK 1.8 以前 HashMap 的实现是数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到数组中时，可能会导致数组某个位置下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。针对这种情况，JDK 1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题。

2）为什么使用红黑树却不使用别的数据结构？

因为不仅仅是要考虑插入时的性能，也要保证查找的性能，红黑树其实就是一种折中的实现方式。

ps：关于红黑树的介绍、HashMap中红黑树的操作，可以参考以下文章

重温数据结构：深入理解红黑树

HashMap 在 JDK 1.8 后新增的红黑树结构

2、和 JDK1.7 中的 hash 方法相比，为什么 JDK1.8 中的 hash 方法更简单呢？

其实 1.7 中的 hash 方法更麻烦是因为它为了提高 HashMap 的散列性，多次使用了移位运算和异或运算，让hash值的高位也参与运算，从而提高获取元素时的性能；

而在 1.8 中，引入了红黑树，这个时候即使散列性没有那么好，但因为链表不会很长，所以其实查询的效率不会低，因此可以简化hash方法。

3、关于数组的扩容与链表转换为红黑树

在 putVal() 方法中，我们看到在使用尾插法往链表中插入节点后，有如下3行代码：
1
2
3
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) 
    treeifyBin(tab, hash);
这三行代码其实是在插入节点后，判断当前链表的节点数是否大于等于8

如果满足条件就会调用 treeifyBin(tab, hash) 方法，也就是所谓的将链表转换为红黑树，

但是如果我们跟进这个方法的源码就会发现有如下代码：
1
2
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();
if（第一个条件是判断数组是否还未初始化）的第二个条件其实是在看当前数组中的元素个数是否小于 64，

如果小于64的话其实执行的是扩容操作，而不是将链表转换为红黑树。

所以就有以下结论：

1）当前链表长度>=8，且数组中元素的个数>=64：将链表转换为红黑树；

1）当前链表长度>=8，但数组中元素的个数<64：执行扩容操作。

ps：关于结论2的补充，为什么<64就只执行扩容操作呢？

1）扩容和树化的本质都是为了防止单一链表过长，从而导致查询效率低，而我们在进行扩容之后也能有效的降低链表长度；

2）在扩容之后其实也会有更多的空间来进行存储，这样其实是基于一个更长远的考虑。

ps：我们都知道链表长度>=8时，会判断是否需要转换为红黑树，但是有没有想过为什么这个阈值是8呢？

对于这个问题，可以参考以下文章：

阿里面试题：为什么Map桶中个数超过8才转为红黑树

4、关于将红黑树转换为链表的操作

其实不仅仅是有将链表转换为红黑树的操作，也有将红黑树转换为链表的操作。

在源码中我们会发现有这样一个常量：
1
static final int UNTREEIFY_THRESHOLD = 6;
这个常量其实就是用来判断，红黑树的节点数是否小于等于6，如果满足这个条件就会将红黑树转换为链表。

但是这个值为什么设置为6，而不是其它数，比如7呢？

其实这是为了避免树与链表之间转换太频繁，从而影响效率。

假设这个值设置为7，并且此时一个链表已经有8个节点，那么会转换为红黑树，但是如果之后又删除了一个节点的话，又满足去树化的条件，红黑树又会转换为链表，如果这样的操作重复出现，就会导致两者之间切换太频繁，从而影响效率。

5、在 JDK1.8 中为什么将头插法改成了尾插法？

在 JDK1.8 中，因为引进了红黑树，从而需要判断链表当前的元素个数，所以需要遍历链表进行统计。

那么既然都已经遍历到链表的末尾了，为什么不直接在尾部插入呢？

当然这不是最主要的原因，最根本的原因如下：

因为JDK1.7是用单链表进行的纵向延伸，当采用头插法时会容易出现逆序且环形链表死循环问题。但是在JDK1.8之后是因为加入了红黑树使用尾插法，能够避免出现逆序且链表死循环的问题。

并且在整个遍历的过程中，其实一共是完成了三件事情：

1）统计链表上的元素个数；

2）需要判断要插入的元素的key，是否在当前链表中已经存在；

3）遍历到尾部后，使用尾插法插入元素。

另：以下文章写得很好，推荐阅读
Java源码分析：HashMap 1.8 相对于1.7 到底更新了什么？

Java新手，若有错误，欢迎指正！

| 阅读量次