HashMap 源码解析二、put 相关函数

HashMap put 相关函数

文接上回，我们讲了HashMap 的构造函数，主要就是设置 负载因子 和 扩容阈值。
这章我们来看HashMap put 的相关函数，不多bb，上源码：

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    @Override
    public V putIfAbsent(K key, V value) {
        return putVal(hash(key), key, value, true, true);
    }
    
    public void putAll(Map<? extends K, ? extends V> m) {
        putMapEntries(m, true);
    }
   
复制代码

put 相关的函数就这3 个，前两个都是直接调用的
putVal(hash(key), key, value, true, true),
后面一个应该还有印象，跟参数为Map构造函数调用的是同一个函数putMapEntries()。
接着我们就看下putVal(hash(key), key, value, true, true) 这个函数

putVal(hash(key), key, value, true, true) 函数

    transient Node<K,V>[] table;

    /**
     * 在put 相关方法中被调用
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)//注释1
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null) //注释2
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = 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);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    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;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;//注释3
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
复制代码

第一次调用时

假设我们是通过HashMap()这个构造函数创建的HashMap 对象并第一次调用 put(K key, V value) 函数。

1. 我们先看下Node 类的结构

    static class Node<K,V> implements Map.Entry<K,V> {
        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;
        }
        //省略代码。。。
    }
复制代码

可以看出这是一个单链表结构，存放着 hash、key和value

2. resize() 函数，作用：初始化或者扩容表为原大小的2倍。源码后面再分析。
3. 知道以上的信息我们在看 putVal() 函数的代码，注释1

if ((tab = table) == null || (n = tab.length) == 0)//注释1
    n = (tab = resize()).length;
复制代码

我们知道DEFAULT_INITIAL_CAPACITY = 1 << 4 // aka 16 因此可以知道
tab = (Node<K,V>[])new Node[16] 和 n = 16

4. 接着往下看，注释2

if ((p = tab[i = (n - 1) & hash]) == null) //注释2
    tab[i] = newNode(hash, key, value, null);
复制代码

我们是第一次调用，p = tab[i = (n - 1) & hash]肯定是null ，于是我们这次就成功的把key,value 存到了tab[i] 中。

5. 我们走进了if，else 的代码就不用看了，直接到了//注释3 的位置 ++modCount 用于记录修改的次数，接着往下看：

if (++size > threshold)
    resize();
复制代码

threshold为扩容阈值，初始化时为 DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR //aka 16*0.75 = 12, size 为HashMap 中保存 Node的数量，当等于 扩容阈值 时就需要对 tab 进行扩容。
接着往下是 afterNodeInsertion(evict);这是一个空方法，什么都没做。

void afterNodeInsertion(boolean evict) { }
复制代码

好了，我们第一次调用就结束了。成功的把数据存储到了HashMap 中，再回头看下我们之前没有看的 else 中的情况

else 中的情况

当tab[i = (n - 1) & hash]中已经有值的情况就会走到 else 中，看代码：

        static final int TREEIFY_THRESHOLD = 8;
        
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = 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);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { //existing mapping for key //注释4
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
复制代码

1. TreeNode 为红黑树，有兴趣的同学可以自行了解 红黑树深入剖析及Java实现

2. 我们看接下来的判断，可以分为3中情况

   • p.key 与 参数key 相同

   直接将p 赋值给 Node e

   • p 为 TreeNode

   将需要保存的内容 添加到红黑树p 中，返回值赋给e

   • else

   遍里链表p，且结果赋值给e; 也可分为3 中情况
   1). if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) 当链表中有Node 的key 与参数key 相同时，结束遍历。
   2). if ((e = p.next) == null) 链表遍历完时
   将需要保存的内容 添加到链表末尾。如果链表长度小于8，结束遍历
   3). 链表遍历完,且添加新增内容。链表长度大于等于8 时。
   执行 treeifyBin(tab, hash) 函数，然后结束遍历。

   static final int MIN_TREEIFY_CAPACITY = 64;
   final void treeifyBin(Node<K,V>[] tab, int hash) {
       int n, index; Node<K,V> e;
       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);
           if ((tab[index] = hd) != null)
               hd.treeify(tab);
       }
   }
   复制代码

   treeifyBin(tab, hash) 函数的逻辑是当tab 长度小于64 时就执行resize() 扩容，否则将链表转为红黑树

3. 我们会过来看注释4 处代码

if (e != null) { //当参数key 在tab 中有映射时 
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}
复制代码

onlyIfAbsent 为true 时不修改现有值
当参数key 在tab 中有映射时，根据条件覆盖现有值，并返回旧值。

int hash(Object key) 函数

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
复制代码

1. ^ 如果相对应位值相同，则结果为0，否则为1，＆ 如果相对应位都是1，则结果为1，否则为0

a     = 1010
b     = 0011
------------
a ^ b = 1001
a & b = 0010
复制代码

2. (h = key.hashCode()) ^ (h >>> 16) 这个方法最重要的一句代码。为什么要做 ^ (h >>> 16)这个操作呢？

是因为在putVal 函数中，是这样是使用的 tab[index = (n - 1) & hash],n 是表的长度，表的长度永远都是2的幂次方，那么n-1的高位应该全是0，做 & 操作时会导致hash 的高位无法参与运算，从而会带来哈希冲突的风险。所以在计算key的哈希值的时候，做(h = key.hashCode()) ^ (h >>> 16)操作。这也就让高位参与到tab[index = (n - 1) & hash]的计算中来了，即降低了哈希冲突的风险又不会带来太大的性能问题。

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) {//table中已经有数据
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // newCap = oldCap * 2
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; //newThr = oldThr * 2 
        }
        else if (oldThr > 0) //初始化是设置了容量和阈值 使用非空构造函数初始化
            //回顾一下构造函数中 threshold = tableSizeFor(initialCapacity) 值为2的幂次方
            //原来这个值其实是给newCap 所以需要为2的幂次方
            // 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);
        }
        if (newThr == 0) {// 上面判断进入 (oldThr > 0) 的情况,没有给newThr 赋值，
            // 所以在这里给newThr 赋值
            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 { // preserve order
                        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) {//注释5
                                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;//注释6
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;//注释7
                        }
                    }
                }
            }
        }
        return newTab;
    }
复制代码

resize() 函数可以分为两个部分

• 设置 newCap、newThr。分析已经写在了代码中，逻辑就是：没有初始化的情况初始化、已经有值的乘以2
• 创建newTab 并重新赋值。这里我们重点解释一下 if ((e.hash & oldCap) == 0)注释5 处的代码。

1. 首先我们知道 tab[index = (n - 1) & hash]，假设oldCap = 16 时

oldCap-1  = ... 0000 1111
hash1     = ... 0000 0101  -> index1 = 0000 0101 = 5
hash2     = ... 0001 0101  -> index2 = 0000 0101 = 5
复制代码

2. 此时需要扩容 newCap = oldCap*2 = 32

newCap-1  = ... 0001 1111
hash1     = ... 0000 0101  -> index1 = 0000 0101 = 5
hash2     = ... 0001 0101  -> index2 = 0001 0101 = 5 + 16(oldCap)
复制代码

3. 从以上两步可以看出，在扩容的时候并不是所有index 都会改变的。而改变的关键就是在 hash 值在 oldCap 的位上是否为0。if ((e.hash & oldCap) == 0)注释5 处的代码就类似于一下列子。作用就是判断是否需要位移。

oldCap    = ... 0001 0000
hash1     = ... 0000 0101  -> 0
hash2     = ... 0001 0101  -> 1
复制代码

4. 这也解释了注释6、注释7处的代码

小结

这章我们主要涉及到3个函数

• putVal(…)

该函数负责数据插入，当size 超过扩容阈值时调用resize()函数扩容，当添加数据的链表长度大于等于8 时将链表转为红黑树。

• hash(Object key)

在计算key的哈希值的时候，用其自身hashcode值与其低16位做异或操作。这也就让高位参与到index的计算中来了，即降低了哈希冲突的风险又不会带来太大的性能问题。

• resize()

重新设置table 的容量和扩容阈值，并新建table 把oldTable 的值填充进去。