HashMap源码解读——创建与扩容

有了解过HashMap的同学们应该都清楚,在JDK1.8中HashMap的底层数据结构其实是数组+链表+红黑树,既然是数组,那么必然存在扩容的问题,那么想创建一个容量合理,性能较高HashMap自然需要了解其创建方法及扩容机制,那么本文会基于1.8.0_91的源码粗略的解析一下创建与扩容,分享给大家,如果有解析错误的地方欢迎大家解析讨论。

首先大致的描述创建与扩容是怎样实现的

当我们在new 一个HashMap的时候其实并没有真正的在底层创建了什么东西,真正的创建是在put方法中实现的,new的这个过程只是初始化了一些相关变量的值,这些变量包括一下几个

//哈希桶数组
transient Node<K,V>[] table;

//默认的HashTable的长度,默认为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

//负载系数
final float loadFactor;
//默认的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//临界值
int threshold;

//已使用容量
transient int size;

创建一个HashMap对象的第一步是是创建一个哈希桶数组(table)既然创建的是数组那么就需要在创建是指定其长度,当我们使用的是空参构造函数是,数组使用的就是默认的长度DEFAULT_INITIAL_CAPACITY = 16,使用带参数的构造函数那么长度就是大于或等于该参数的最小的2次幂(例如我传的是31,那么创建出来的哈希桶数组长度就是大于31的2^5,即为32)。初始化过后当里面的存放对象过多时,就会出现越来越多的哈希冲突,影响HashMap的查询插入效率,这个时候就需要扩容,使得HashMap有越多的Hash槽来减少哈希冲突,提高效率,但是我们知道扩容是非常消耗内容的,所以频繁的扩容也是不可行的。那么什么时候需要扩容呢?HashMap在设计上已经考虑了这一点,扩容的时机就是在达到当内部存放的元素数量(size)达到临界值时(threshold),那么HashTable就会进行扩容,临界值 = 哈希桶长度 x 负载因子(loadFactor)。了解了这些基本的变量也就粗略了解了HashMap的扩容原理,我们接下来跟着源码深入刨析一下其实现。

以下是构造函数源码

//核心构造函数
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        //初始容量小于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);
}

//含容量构造函数
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//空参构造函数
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//复制初始化
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

比较常见的问题是:获取大于或等于一个数的最小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 < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

首先分析 n |= n >>> x 这个就是把一个数或该数无符号右移x位的值,上面这个代码达到的效果如下

    01 00000 00000 00000 00000 00000 00000 (n)   
    
    01 10000 00000 00000 00000 00000 00000 (n |= n >>> 1)    
    
    01 11100 00000 00000 00000 00000 00000 (n |= n >>> 2)    
    
    01 11111 11000 00000 00000 00000 00000 (n |= n >>> 4)    
    
    01 11111 11111 11111 00000 00000 00000 (n |= n >>> 8)    
    
    01 11111 11111 11111 11111 11111 11111 (n |= n >>> 16)    

其实目的就是让n的二进制最高位之后所有的位上都是1,最后算出来+1 ,所有位进1,得到的结果就是最高为是1其他都为0的数,这样的数就是2的n次方,也是最接近n的2的幂。

接着为什么要cap - 1呢?
是因为如果传进来的数就是2的n次方,那么默认值就应该是2的n次方,不减一的话那么按上述运算出来就变成了2的(n+1)次方。

例如传进来是32,那么减一之后计算出来是32,不减一算出来的结果是64。

讲解完构造函数接下来就是扩容的resize()函数

final Node<K,V>\[\] resize() {

    //由于初始化是调用的也是resize方法所table 可能为空

     Node<K,V>\[\] oldTab = table;

  

    //获取旧Hash桶长度

    int oldCap = (oldTab == null) ? 0 : oldTab.length;

  

    //获取旧负载临界值

    int oldThr = threshold;

    int newCap, newThr = 0;

    if (oldCap > 0) {

        //已初始化,map是扩容

        //旧Hash桶已到最大长度无法扩容,则将负载临界值设置到最大,返回旧的Hash桶

        if (oldCap >= MAXIMUM\_CAPACITY) {

            threshold = Integer.MAX\_VALUE;

            return oldTab;

        }

        else if ((newCap = oldCap << 1) < MAXIMUM\_CAPACITY && oldCap >= DEFAULT\_INITIAL\_CAPACITY)

        //2倍当前容量<最大容量且原容量大于默认初始容量,则进行扩容至之前的2倍(<<1 = \\\*2) 

            newThr = oldThr << 1; // double threshold

    }else if (oldThr > 0)

        //未初始化,oldThr只在带有参数的Map构造函数中有定义

        //如果指定了初始容量参数作为容量则Hash会选择一个大于或等于该数字的第一2的幂作为容量,在构造函数逻辑中已完成

        newCap = oldThr;

    else {

        //未初始化,无参构造行数,按默认的数据进行参数

        newCap = DEFAULT\_INITIAL\_CAPACITY;

        newThr = (int)(DEFAULT\_LOAD\_FACTOR \* DEFAULT\_INITIAL\_CAPACITY);

    }

  

    if (newThr == 0) {

        /*

        根据上面的逻辑,有两种情况newThr是0

        1.扩容,且容量大于16

        2.无参构造函数初始化

        */

        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;

    //以上完成新建,非扩容返回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;

}

JDK1.7之前,扩容时都会rehash,Jdk1.8之后对这个点进行了优化

//原位置链表
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;
    //新链表hash槽为原为+原hashtable长度
    newTab[j + oldCap] = hiHead;
}

看了述代码就会产生一个问题:(e.hash & oldCap) == 0为什么能判断是否需要改变位置?
假设:计算hashtbale槽位时算法 e.hash & (newCap - 1),那么我们以16扩容至32为例

扩容前:

16        0000 0000 0000 0000 0000 0000 0001 0000

16-1=15   0000 0000 0000 0000 0000 0000 0000 1111        

hash1     1111 1111 1111 0000 1111 0000 0000 1010     

hash2     1111 1111 1111 0000 1111 0000 0001 1010                  

hash1:
    &(newCap - 1) 结果 :1010 =10
    
    &newCap       结果 :0

hash2:
    &(newCap - 1) 结果 :1010 =10 
    
    &newCap       结果 :0001 0000

所以hash1,hash2 &15的结构是一样的在同一个hash槽中。

扩容后:

32        0000 0000 0000 0000 0000 0000 0010 0000     

32-1=31   0000 0000 0000 0000 0000 0000 0001 1111        

hash1     1111 1111 1111 0000 1111 0000 0000 1010     

hash2     1111 1111 1111 0000 1111 0000 0001 1010                  

hash1:
    &(newCap - 1) 结果 :1010 =10
    
    &newCap       结果 :0

hash2:
    &(newCap - 1) 结果 :0001 1010 =26 = 10+16 = 原位置+oldCap  
    
    &newCap       结果 :0001 0000

因为扩容后本来只取4位计算变成了五位。所以rehash的结果是两种,一种是在原位子,还有一种在原位置+oldCap。所以我们只需要对hash结果在新位置上的key进行rehash计算。那么可以根据(e.hash & oldCap) == 0则说明e.hash最高位是左边一位是0,所以 e.hash & newCap-1的结果与e.hash & oldCap-1的结果是相等的。(e.hash & oldCap) != 0则说明最高位是左边一位是1,则原位置+oldcap

评论

暂无评论