认真研究HashMap的初始化和扩容机制

本文我们总结HashMap在jdk1.8/jdk1.7下的初始化和扩容机制。

【1】jdk1.8下

① 初始化

HashMap的初始化可以有如下几种方式:

 public HashMap(int initialCapacity);
 public HashMap() ;
 public HashMap(Map m)
 public HashMap(int initialCapacity, float loadFactor)

loadFactor是负载因子,默认是0.75。在实例化HashMap时可以指定初始容量。如果你指定了初始容量,那么就会触发tableSizeFor(initialCapacity);方法,其将会计算threshold值。

其目的就是是将传进来的参数转变为2的n次方的数值然后赋予threshold。>>>表示无符号右移,也叫逻辑右移,即若该数为正,则高位补0。这样就是保证了HashMap容量必须是2的整数幂,比如传入12那么得到的threshold为16。

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 = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

根据HashMap的构造函数可以发现,此时其核心成员transient Node[] table还是null,并未被初始化。指定初始化容量只是对阈值threshold进行了初始化。

② 扩容

扩容的场景


putMapEntries时如果HashMap.size>threshold,触发扩容;

putVal时如果tab未被初始化,则触发扩容;

putVal后如果++size > threshold则触发扩容;也就是整个HashMap中元素个数大于阈值,就会触发扩容

treeifyBin链表转化为红黑树时如果tab.length<MIN_TREEIFY_CAPACITY(64),则触发扩容;

computeIfAbsent 或 compute 或 merge时如果size > threshold || (tab = table) == null ||(n = tab.length) == 0触发扩容;

代码如下所示,这里先说明一点,扩容的本质是获取新的容量和新的临界值,并对链表或者树进行转化。

代码如下所示,这里先说明一点,扩容的本质是获取新的容量和新的临界值,并对链表或者树进行转化。

final


(1) 对链表的处理

如上所示,这里使用(e.hash & oldCap) == 0来判断是否需要拆分链表。如果结果为0,则位置不变,(链表的头结点)仍旧是newTab[j]。如果结果不为0,则(链表的头结点)放到newTab[j + oldCap]位置处。

这里会遍历旧链表的每个结点,通过判断来尝试得到两个链表并记录两个链表的头结点。

那么这里有两个问题:为什么使用(e.hash & oldCap) == 0来判断?为什么改变的位置是newTab[j + oldCap]?

前面我们定位key的索引位置使用的方法是(n-1)&hash。n 表示hashMap的容量(oldCap)也就是tab.length,hash表示key的散列值。也就是说(oldCap-1)&hash相等的key并不意味着(e.hash & oldCap)计算结果也相等,所以存在了拆分链表的可能性(而且只可能拆分为两个链表)。

为什么使用(e.hash & oldCap) == 0来判断?

因为(e.hash & oldCap) == 0,那么位置必然不会发生变化!

我们举例如下。假设oldCap为16,那么扩容后为32。使用(n-1)&hash对一个key来说唯一区别在于高位的1(扩容前后低位都是1),这也就是为什么使用e.hash & oldCap。如果与这个高位的1进行&运算得到0,表示key的hash在高位这个1位置是0,那么扩容前后进行索引位置运算结果不会发生变化!

32 0010 0000
31 0001 1111
16 0001 0000
15 0000 1111

这也能够解释为什么只可能拆分为两个链表了,因为与高位1进行&运算,结果只有两种。


为什么改变的位置是newTab[j + oldCap]


前面我们提到过,扩容的时候(newCap = oldCap << 1),也就是newCap =2*oldCap 。假设oldCap为16,那么扩容后newCap就是32。也就是在(oldCap-1)&hash与(newCap-1)&hash的运算过程中,这个差别仅仅在于后者二进制位高位比前者多了一个1,这个1换算成十进制也就是oldCap。

与高位1的&运算,结果要么是0,要么是1。前者位置不变,后者位置+oldCap。

如下所示四组key分别在新旧数组中的位置,可以看到位置发生改动的 newIndex=oldIndex+olcCap。


key(hash) oldCap=16 newCap=32
key1(16) 0 16
key2(32) 0 0
key3(48) 0 16
key4(64) 0 0


(2) 对树结点的处理

对树结点的处理如下所示,首先从当前结点开始遍历next,同上述链表处理一致。尝试获取两棵树(一棵位置改变,一棵位置+oldCap)。与链表不同的时,扩容的时候还会判断树的结点数量是否满足<=UNTREEIFY_THRESHOLD = 6,如果是,则将树结点转换为链表。

((TreeNode)e).split(this, newTab, j, oldCap);

// int bit = oldCap   int index = j
final void split(HashMap map, Node[] tab, int index, int bit) {
    TreeNode b = this;
    // Relink into lo and hi lists, preserving order

    //数组索引位置没有发生变化的
    TreeNode loHead = null, loTail = null;

    //数组索引位置发生变化的
    TreeNode hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    for (TreeNode e = b, next; e != null; e = next) {
        next = (TreeNode)e.next;
        e.next = null;
        //(e.hash & oldCap) == 0
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;//通过这两步形成链表
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }
// 到这里for循环结束,也是件检索整个树结点
    if (loHead != null) {
        // UNTREEIFY_THRESHOLD = 6
        if (lc <= UNTREEIFY_THRESHOLD)
            // 转为链表
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            //如果hiHead 为null,则说明所有节点位置没有发生变化,
            //其本身就是一棵树,无需再次处理
            if (hiHead != null) 
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
        //转为链表 tab[index + bit]其实就是tab[j+oldCap]
        if (hc <= UNTREEIFY_THRESHOLD)
            //转为链表
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                //转为树,思路同上
                hiHead.treeify(tab);
        }
    }
}

关于树结点的转化我们另起篇章说明。整体扩容流程如下所示:

【2】Jdk1.7下

① 初始化


HashMap的几个构造方法如下所示:

public HashMap(int initialCapacity, float loadFactor);
public HashMap(int initialCapacity);
public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(Map m)

与jdk1.8不同的是,实例化时就初始化了threshold 和capacity 并由此 创建了数组table(这样就存在了空间浪费),如下所示:

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);

    // Find a power of 2 >= initialCapacity
    // 这里使用了while,jdk1.8采取的位运算
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;

    this.loadFactor = loadFactor;
    threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    // 实例化时就为数组分配了空间
    table = new Entry[capacity];
    useAltHashing = sun.misc.VM.isBooted() &&
            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    init();
}


② 扩容

如下所示在put方法中新增结点可能会触发扩容,newCapacity=2*table.length,也就是2倍扩容。

resize方法

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    
    //对旧容量做了最大值判断,如果已经达到最大值则更新threshold ,直接return
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    //实例化新数组,容量为newCapacity
    Entry[] newTable = new Entry[newCapacity];
    
    boolean oldAltHashing = useAltHashing;
    useAltHashing |= sun.misc.VM.isBooted() &&
            (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean rehash = oldAltHashing ^ useAltHashing;
    
    // 数据的转化-旧数组的数据转到新数组中
    transfer(newTable, rehash);
   
    //table指向新数组
    table = newTable;
   
    //计算并更新threshold 
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}



transfer方法

jdk1.7.0_17中HashMap的transfer方法如下所示:

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    
    //遍历数组中的每个“链表”
    for (Entry e : table) {
        while(null != e) {
            //对链表中的每个结点进行循环
            Entry next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            // h & (length-1) 计算当前结点在新数组中的位置
            int i = indexFor(e.hash, newCapacity);
            
            //头插法,会形成倒排效果
            e.next = newTable[i];
            newTable[i] = e;

            //更新 e 为下一个结点
            e = next;
        }
    }
}

我们以如下为例来描述一下数组的转换过程。再次强调一下,(oldCap-1)&hash 与 (newCap-1)&hash不一定相等!

① 首先获取到e=a, Entry next=b,a.next=newTable[i](假设i是0,此时a.next=null),newTable[0]=a,e=b。

② 此时e=b, Entry next=c,b.next=newTable[i](假设i是0,此时b.next=a),newTable[0]=b,e=c。



③ 此时e=c, Entry next=null,c.next=newTable[i](假设 i 是16,发生位置改变,此时c.next=null),newTable[16]=c,e=null,将结束本次循环。跳到位置 1 处…



由于jdk1.7是遍历过程中对每一个结点进行了重新定位,那么并发扩容下是否会存在问题?我们在另一篇博文说明。

【3】仔细分析tableSizeFor方法

可以发现tableSizeFor方法保证了无论指定了什么initialCapacity,都会返回一个2^n的数。当在实例化HashMap实例时,如果给定了initialCapacity,由于HashMap的capacity都是2的幂,因此这个方法用于找到大于等于initialCapacity的最小的2的幂(initialCapacity如果就是2的幂,则返回的还是这个数)。

下面我们仔细分析tableSizeFor方法。

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 = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;//⑦
  }

① cap-1

这是为了防止,cap已经是2的幂。如果cap已经是2的幂, 又没有执行这个减1操作,则执行完后面的几条无符号右移操作之后,返回的capacity将是这个cap的2倍。

n |= n >>> 1

无符号按位右移运算符。左操作数按位右移右操作数指定的位数,符号位跟着移动,空出来的高位补0(左边补充的值永远为0,不管其最高位(符号位)的值)。

先进行无符号右移一位(相当于n/2),然后再与n进行|运算(输入2个参数,a、b对应位只要有一个为1,c对应位就为1;反之为0)。

由于n不等于0,则n的二进制表示中总会有一bit为1,这时考虑最高位的1。通过无符号右移1位,则将最高位的1右移了1位,再做或操作,使得n的二进制表示中与最高位的1紧邻的右边一位也为1,如000011xxxxxx。

n |= n >>> 2;

注意,这个n已经经过了n |= n >>> 1; 操作。假设此时n为000011xxxxxx ,则n无符号右移两位,会将最高位两个连续的1右移两位,然后再与原来的n做或操作,这样n的二进制表示的高位中会有4个连续的1。如00001111xxxxxx 。

④ n |= n >>> 4;

这次把已经有的高位中的连续的4个1,右移4位,再做或操作,这样n的二进制表示的高位中会有8个连续的1。如00001111 1111xxxxxx 。

以此类推

注意,容量最大也就是32bit的正数,因此最后n |= n >>> 16; ,最多也就31个1(int最大正数值),但是这时已经大于了MAXIMUM_CAPACITY ,所以取值到MAXIMUM_CAPACITY 。

static final int MAXIMUM_CAPACITY = 1 << 30


图例如下:

发表评论