java 8 hashmap源码分析(二)

在上一章。我们把hashmap中核心部分红黑树整理了一下https://www.jianshu.com/p/140467284050；这一章，我们详细介绍hashmap如何进行扩容，红黑树和bin什么时候进行转换的；

hashmap putVal();

源码分析过程中注意的以下

• (n - 1) & hash 这个是计算元素p所在hash位置
• p.hash的值为p.hashcode与p.hashcode右移16位 按位与运算得到的
• 单链表在resize的过程中，随机的将单链表分布在新的tab中，参考http://yypiao.iteye.com/blog/2355700； HashMap putVal过程.png

     * Implements Map.put and related methods
     *
     * @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;
//  先判断tab是否为空，如果为空，初始化tab的空间；
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;

        if ((p = tab[i = (n - 1) & hash]) == null)
//通过hash计算，找到p元素所在的位置，如果位置为空
//  (n - 1) & hash 这个是计算元素p所在hash位置
            tab[i] = newNode(hash, key, value, null);
        else {
//hash值一样的值的集合；
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
//判断插入值的hash，并且有相同的key,此时key可为空，如果key相同，则返回e=p；
//这个时候key可以为空
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//  如果插入的值hash值相同，root.key不同时，并且p（root）根结点为树结构；以红黑树插入
            else {
//  如果插入的值hash值相同，root.key不同时，并且p（root）根结点为链表结构；
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
// 找到链表的尾端，插入新值，如果插入之前bincount>=7,即新的链表大于等于8元素，转红黑树
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
//  如果插入的值hash值相同，遍历链表中的元素的key与e.key相同时；返回
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;

                    p = e;//指针移动，
                }
            }

            if (e != null) { // existing mapping for key
// 找到key的匹配的对应，如果允许更新该值的时候，更新该值；
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
//  新元素调整listhashmao
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

hashmap的扩容

• 将table 初始化，或者将table的大小扩容到原来的倍；
• 如果table为空，则将hashmap的capacity设置成threshold的值
• 如果table不为空，则hashmap中每个桶必须在相同的索引下，或者按照2倍数进行偏移
• hashmap的扩容分成两块；
• 1: 第一块是capacity，threshold的处理；是否达到最大，如果没有则扩大到原来容量的两倍（如果给定了初始化容量，则按照给定的容量扩增，否则为capacity为16，threshold为12（0.75*capacity））；第二块：
• 2: 第二块非常重要，即将原来的tab中的数据全部迁移到新的tab中；原来index = hash& n-1;迁移之后，每个新节点的index = hash & n-1;这个时候特别注意（table的size始终为16，32，64.。。），因为hash与n按位与，随机的将原来桶中的index拆分成了两块，即hash高位为0，即e.hash & oldCap== 0，放在原来的位置；hash高位为1的，即e.hash & oldCap== oldCap；node对应的inde移动n位；newTab[j + oldCap] = hiHead. 该方法用在了单链表以及红黑树的节点拆分的过程中；

/**
     * Initializes or doubles table size.  If null, allocates in
     * accord with initial capacity target held in field threshold.
     * Otherwise, because we are using power-of-two expansion, the
     * elements from each bin must either stay at same index, or move
     * with a power of two offset in the new table.
     *
     * @return the table
     */
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
//  如果原来的table为空，则oldCap为零；否则为实际的长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;

        int oldThr = threshold;
        int newCap, newThr = 0;
//  如果table不为空，则需要扩容
        if (oldCap > 0) {
//如果  原来的容量大于*能够扩容最大的容量*，即pow(2,30)，则不能在扩容，返回原来的capacity；
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;（注意此时的threshold为capat）
                return oldTab;
            }
// 将原来的容量左移一位，即oldCap*2;且值小于pow(2,30);原来的值大于16
//即至少被初始化过；
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }//endif oldcap>0

//oldCap <=0时候
//  第一种情况：如果hashmap设置了初始化的capacity //this.threshold = tableSizeFor(initialCapacity);
        else if (oldThr > 0) // initial capacity was placed in threshold  
            newCap = oldThr;
// 第二种情况，未设置capacity，使用默认的capacity以及threshold为0.75*capacity；
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        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) {
            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) {
                                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;
    }