JDK8之HashMap源码解析

本篇将详细分析JDK8中HashMap的源码及其工作原理

版本

本篇使用版本

java version "1.8.0_151"
Java(TM) SE Runtime Environment (build 1.8.0_151-b12)
Java HotSpot(TM) 64-Bit Server VM (build 25.151-b12, mixed mode)

HashMap继承关系

常量

// 初始化容量，这里是位运算，实际也就是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 扩容因子，0.75表示使用的容量达到 当前容量的 75% 就扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表转红黑树的阈值，链表长度达到此值，会进化成红黑树（该值必须大于2，并且应该至少为8，为了方便红黑树）
static final int TREEIFY_THRESHOLD = 8;
// 红黑树收缩为链表的阈值，链表长度小于此值后再转回链表结构
static final int UNTREEIFY_THRESHOLD = 6; 
// 转变成树之前，还会有一次判断，只有键值对数量大于 64 才会发生转换。这是为了避免在哈希表建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。
static final int MIN_TREEIFY_CAPACITY = 64;

变量

// Node数组，实际存放 键值对 的地方（Node是内部类，链表结构）
transient Node<K,V>[] table;
// 遍历是使用的，用来缓存entrySet()方法
transient Set<Map.Entry<K,V>> entrySet;
// 已使用的容量
transient int size;
// 用来记录修改次数，防止在foreach过程中其他线程修改数据（如果修改了抛出ConcurrentModificationException）
transient int modCount;
// 当前 HashMap 所能容纳键值对数量的最大值，超过这个值，则需扩容
int threshold;
// 扩容因子 ，当size>table.size*loadFactor 时扩容
final float loadFactor;

构造方法

// 无参构造，使用默认扩容因子
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// int 构造，传入初始数组容量，调用(int,float)构造
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// (int,float)构造，传入初始数组容量和扩容因子
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;
    // 计算初始数组长度
    this.threshold = tableSizeFor(initialCapacity);
}
// map构造参数，传入一个Map类型，将KV转移到新的HashMap
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

方法

tableSizeFor

(int,float)构造初始化时调用的，作用是给定一个参数，返回大于输入参数且最近的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;
}

详解：

1. 假设我们现在输入10，那么n的初始值为9，转换为二进制就是 0000…1001
2. 右移一位变成0000…0100，再位或变成0000…1101
3. 右移两位变成0000…0011，再位或变成0000…1111
4. 右移四位变成0000…0000，再位或变成0000…1111 ，我们发现，到这里之后，无论如何运算，n都不会再改变了，最后n的结果为15
5. 最后一句return表示 当n小于0返回1；大于最大容量时，返回最大容量。如果正常合法，则返回n+1

解释一下这个方法，其实就是利用位运算，将传入参数的最高位前一位变为0且后面的所有位都为1。这样当n+1时，最高位前一位变成1，其他位全为0，这样就得到了大于这个数字且最近的2的整数次幂。

备注：

1. 为什么要先减一int n = cap - 1 当输入参数是本就是2的幂次方时，位运算计算出来的就是大于这个参数且最近的2的幂次方。其实就是为了解决当参数是2的整数次幂时的计算错误问题。
2. 为什么要加一，因为位运算算出来的结果必然为001…1 ，…中全是1，加一后才能得到2的整数次幂。

putMapEntries

map构造时调用的，传入一个map类型，初始化数组容量并将入参Map的KV键值对添加到当前的HashMap中。
源码如下:

// 这里传入了一个参数evict，evict参数用于LinkedHashMap中的尾部操作，这里没有实际意义。
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    // 入参size大于0时操作
    if (s > 0) {
        // 初始化时预先设置数组长度
        if (table == null) { // pre-size
            // 数组长度*扩容因子=扩容阈值（这里的操作其实就是算出不需要扩容的最小数组长度），而由于float是舍弃小数点的，加一位才能保证不需要扩容。
            float ft = ((float)s / loadFactor) + 1.0F;
            // 判断是否大于最大长度，大于则用最大长度
            int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
            // 如果大于当前通容积，则重新设置容积
            if (t > threshold) 
                threshold = tableSizeFor(t);
        }
        // table 不为null 说明不是初始化时使用的，且入参size大于桶容积，调用扩容方法
        else if (s > threshold)
            resize();
        // 调用putVal方法将KV对放入桶中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            // putVal 下面详解
            putVal(hash(key), key, value, false, evict);
        }
    }
}

put

// 这里计算hash然后调用了putVal方法
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

hash

static final int hash(Object key) {
    int h;
    // 如果key为null返回0，否则调用hashCode方法并将hashCode的高16位和低16位做异或操作，这样减少key的hash位数的同时也会因为高16位的变化变化，其实就是增加低16位的随机性，减少hash碰撞
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

putVal

// hash： key的hash，onlyIfAbsent 如果是true则不覆盖原有数据，evict如果是false说明是在创建模式
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 如果table为空，说明初始化后第一次使用，则创建table并初始化（懒加载），将table.length赋值给n
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // table不为空，将n-1也就是数组最大下标（一定是1...1,因为数组长度必定是2的整数次幂），再将i与hash做与运算，求出数组下标
        // 如果当前下标没有元素，则新建一个node链表
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        // 当前下标位已有元素
        else {
            Node<K,V> e; K k;
            // key相同，直接覆盖value
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 如果当前节点是红黑树节点，则调用putTreeVal 做红黑树处理
            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);
                        // 如果链表长度大于阈值，则转换为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 如果链表上存在当前key，则替换value
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                // 允许覆盖，或者原数据为null，赋值并返回
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // LinkedHashMap用的，这里没意义
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 修改次数，防止在foreach过程中其他线程修改数据（如果修改了抛出ConcurrentModificationException）
        ++modCount;
        // 大于阈值扩容
        if (++size > threshold)
            resize();
        // LinkedHashMap用的，这里没意义
        afterNodeInsertion(evict);
        return null;
    }

扩容resize

final Node<K,V>[] resize() {
    // 原table
    Node<K,V>[] oldTab = table;
    // 原table的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 原扩容阈值
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 原table长度不为0表示非初始化时调用
    if (oldCap > 0) {
        // 当 table 容量超过容量最大值，则不再扩容
        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
    }
    // 初始化时，将 threshold 的值赋值给 newCap，
    // HashMap 使用 threshold 变量暂时保存 initialCapacity 参数的值
    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);
    }
    // 新扩容阈值为 0 时，按阈值计算公式进行计算
    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) {
        // 如果旧的桶数组不为空，则遍历桶数组，并将键值对映射到新的桶数组中
        // 这样可以使元素更加分散，减少hash冲突，提升性能
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null; // 拿到元素并将原数组位置设置为null
                // 如果链表没有next节点，则直接new Node放入newTab
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                     // 重新映射时，需要对红黑树进行拆分
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 有next节点，循环转移
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                         // 遍历链表，并将链表节点按原顺序进行分组
                        next = e.next;
                        // 比如当前数组长度为4 则可能在下标为1的位置上同时存在 hash为1,5,9 ,现在将 这些hash与oldCap 做与运算
                        // 1 二进制 0001 和1000与运算后 0000
                        // 5 二进制 0101 和1000与运算后 0000
                        // 9 二进制 1001 和1000与运算后 1000 （不等于0） 
                        // 其实就是将原链表的元素分散开，减少链表长度新下标一定是（原下标 或者 原下标+扩容长度）
                        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;
}

获取方法get

public V get(Object key) {
    Node<K,V> e;
    // 计算hash并调用getNode方法
    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中已有元素，而且hash对应的下标位不为空
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        // 如果hash相同且key相同，直接返回value
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // key不相同，如果链表存在next节点，则开始循环链表查找
        if ((e = first.next) != null) {
            // 红黑树节点
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                // 找到hash相同且key相同的元素
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // 未找到返回null
    return null;
}

图解

存储结构

put流程图

扩容

备注

• 有关红黑树的知识有点多，决定单独写一篇来说红黑树和HashMap中的红黑树实现