HashMap的扩容机制-蒲公英云

文章目录

- - 先讲扩容原理
  - - 子问题1：hash算法
    - 子问题2：HashMap的resize

先讲扩容原理

在jdk1.7的时候，扩容需要满足如下两个条件：
（1）存放新值的时候当前已有的元素的个数必须大于等于阈值
（2）存的放新值的时候当前存放数据发生了hash碰撞
而在jdk1.8的时候，扩容只需要满足一个条件：当前存放新值（注意不是替换已有元素时）的时候已有元素的个数大于等于阈值（已有的元素等于阈值，下一个存放必然会触发扩容机制）或者存入数据到某一条链表上，此时的数据大于8且总的数量小于64即发生扩容
注意：
（1）扩容一定是放入新值的时候，该新值不是替换以前位置的情况下
（2）扩容发生存放后，会判断存入对象的个数，如果是大于阈值则进行扩容
（3）首次put时，先会触发扩容（实例化的HashMap默认内部数组是null，即没有实例化。第一次调用put方法时，则会开始第一次初始化扩容，长度为16。），然后存入数据，然后判断是否需要扩容；不是首次put，则不再初始化，直接存入数据，然后判断是否需要扩容；
HashMap的容量是有上限的，必须小于1<<30，即1073741824。如果容量超出了这个数，则不再增长，且阈值会被设置为Integer.MAX_VALUE（ [公式] ，即永远不会超出阈值了）。

源码：在jdk7中，当new Hashmap()的时候会对对象进行初始化，而jdk8中new Hashmap()并没有对对象进行初始化，而是在put()方法中通过判断对象是否为空，如果为空通过调用resize()来初始化对象。

public V put(K key, V value) {

        return putVal(hash(key), key, value, false, true);
    }

/* Implements Map.put and related methods @param hash key值计算传来的下标 @param key @param value @param onlyIfAbsent true只是在值为空的时候存储数据，false都存储数据 @param evict @return 返回被覆盖的值，如果没有覆盖则返回null /

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) { 
    // 申明entry数组对象tab[]:当前Entry[]对象
    Node<K,V>[] tab;
    // 申明entry对象p:这里表示存放的单个节点
    Node<K,V> p;
    // n:为当前Entry对象长度 　　　　 // i:为当前存放对象节点的位置下标
    int n, i;
    /** * 流程判断 * 1、如果当前Node数组(tab)为空，则直接创建(通过resize()创建)，并将当前创建后的长度设置给n * 2、如果要存放对象所在位置的Node节点为空，则直接将对象存放位置创建新Node，并将值直接存入 * 3、存放的Node数组不为空，且存放的下标节点Node不为空（该Node节点为链表的首节点） * 1）比较链表的首节点存放的对象和当前存放对象是否为同一个对象，如果是则直接覆盖并将原来的值返回 * 2）如果不是分两种情况 * （1）存储处节点为红黑树node结构，调用方法putTreeVal()直接将数据插入 * （2）不是红黑树，则表示为链表，则进行遍历 * A.如果存入的链表下一个位置为空，则先将值直接存入，存入后检查当前存入位置是否已经大于链表的第8个位置 * a.如果大于,调用treeifyBin方法判断是扩容 还是 需要将该链表转红黑树（大于8且总数据量大于64则转红黑色，否则对数组进行扩容） * b.当前存入位置链表长度没有大于8，则存入成功，终端循环操作。 * B.如果存入链表的下一个位置有值，且该值和存入对象“一样”，则直接覆盖，并将原来的值返回 * 上面AB两种情况执行完成后，判断返回的原对象是否为空，如果不为空，则将原对象的原始value返回 * 上面123三种情况下，如果没有覆盖原值，则表示新增存入数据，存储数据完成后，size+1,然后判断当前数据量是否大于阈值， * 如果大于阈值，则进行扩容。 */
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    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
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 如果不是替换数据存入，而是新增位置存入后，则将map的size进行加1，然后判断容量是否超过阈值，超过则扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

treeifyBin()方法判断是扩容还是将当前链表转红黑树

/** * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. * 从指定hash位置处的链表nodes头部开始，全部替换成红黑树结构。 * 除非整个数组对象（Map集合）数据量很小（小于64），该情况下则通过resize()对这个Map进行扩容，而代替将链表转红黑树的操作。 */
    final void treeifyBin(HashMap.Node<K,V>[] tab, int hash) { 
        int n, index; HashMap.Node<K,V> e;
        // 如果Map为空或者当前存入数据n（可以理解为map的size()）的数量小于64便进行扩容
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        // 如果size()大于64则将正在存入的该值所在链表转化成红黑树
        else if ((e = tab[index = (n - 1) & hash]) != null) { 
            HashMap.TreeNode<K,V> hd = null, tl = null;
            do { 
                HashMap.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);
        }
    }

子问题1：hash算法

Java源代码是这么做的：
在这里插入图片描述

首先根据key计算得到它的hashCode值，然后跟数组的长度减一做一次与运算，为什么hashmap的数组初始化大小都是2的次方大小时，hashmap的效率最高呢？可以看第7个问题。
所以说当数组长度为2的n次幂的时候，不同的key算出的index相同的几率较小，那么数据在数组上分布的也就比较均匀，查询的时候效率就变高了。
HashMap中的默认数组大小是16，因为16是2的整数次幂的原因，在小数据量的情况下能更好的减少key之间的碰撞。在存储大容量的时候，最好预先指定HashMap的size为2的整数次幂方，如果不指定的话，HashMap的构造方法也会以大于且最接近指定值大小的2次幂来进行初始化的。

子问题2：HashMap的resize

HashMap在扩容的时候：原数组中的数组必须重新计算其在新数组中的位置并放进去，这就是resize。那么什么时候进行扩容呢？当HashMap中的元素个数超过数组大小*loadFactor（负载因子）时，就会进行数组的扩容，loadFactor的默认值是0.75。
所以说在最先开始我们在指定HashMap的大小时设置为最接近我们预想中的数量/0.75得到的最接近且大于他的数（这个数是2的幂指数倍），这样既考虑了&的问题，也避免了resize的问题。