敞开生长之旅!这是我参与「日新方案 12 月更文应战」的第1天,点击检查活动详情

为什么?

关于调集类,《阿里巴巴Java开发手册》中写道:

为什么阿里巴巴建议HashMap初始化时需要指定容量大小?

咱们先来写一段代码在JDK 1.7 (jdk1.7.0_80)下面来别离测验下,在不指定初始化容量和指定初始化容量的情况下功能情况如何。(jdk 8 成果会有所不同,我会在后面的文章中分析)

public static void main(String[] args) {
    int aHundredMillion = 10000000;
    Map<Integer, Integer> map = new HashMap<>();
    long s1 = System.currentTimeMillis();
    for (int i = 0; i < aHundredMillion; i++) {
        map.put(i, i);
    }
    long s2 = System.currentTimeMillis();
    System.out.println("未初始化容量,耗时 : " + (s2 - s1));
    Map<Integer, Integer> map1 = new HashMap<>(aHundredMillion / 2);
    long s5 = System.currentTimeMillis();
    for (int i = 0; i < aHundredMillion; i++) {
        map1.put(i, i);
    }
    long s6 = System.currentTimeMillis();
    System.out.println("初始化容量5000000,耗时 : " + (s6 - s5));
    Map<Integer, Integer> map2 = new HashMap<>(aHundredMillion);
    long s3 = System.currentTimeMillis();
    for (int i = 0; i < aHundredMillion; i++) {
        map2.put(i, i);
    }
    long s4 = System.currentTimeMillis();
    System.out.println("初始化容量为10000000,耗时 : " + (s4 - s3));
}

为什么阿里巴巴建议HashMap初始化时需要指定容量大小?

以上代码不难理解,咱们创立了3个HashMap,别离运用默许的容量(16)、运用元素个数的一半(5千万)作为初始容量、运用元素个数(一亿)作为初始容量进行初始化。然后别离向其中put一亿个KV。

从成果中,咱们能够知道,在已知HashMap中将要寄存的KV个数的时分,设置一个合理的初始化容量能够有用的进步功能。

这是由于HashMap有扩容机制,就是当到达扩容条件时会进行扩容。HashMap的扩容条件就是当HashMap中的元素个数(size)超越临界值(threshold)时就会主动扩容。在HashMap中,threshold = loadFactor * capacity

所以,假如咱们没有设置初始容量巨细,随着元素的不断增加,HashMap会发生屡次扩容,而HashMap中的扩容机制决议了每次扩容都需要重建hash表,是十分影响功能的。

从上面的代码示例中,咱们还发现,同样是设置初始化容量,设置的数值不同也会影响功能,那么当咱们已知HashMap中行将寄存的KV个数的时分,容量设置成多少为好呢?

HashMap中容量的初始化

默许情况下,当咱们设置HashMap的初始化容量时,实际上HashMap会选用第一个大于该数值的2的幂作为初始化容量。

当咱们通过HashMap(int initialCapacity)设置初始容量的时分,HashMap并不一定会直接选用咱们传入的数值,而是通过核算,得到一个新值,目的是进步hash的功率。(1->1、3->4、7->8、9->16)

不管是Jdk 1.7仍是Jdk 1.8,核算初始化容量的算法其实是千篇一律的,主要代码如下:

    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;

JDK1.7中是highestOneBit()办法,1.8中是tableSizeFor()办法。

为什么阿里巴巴建议HashMap初始化时需要指定容量大小?

为什么阿里巴巴建议HashMap初始化时需要指定容量大小?

作用都是回来一个比入参刚好大的2的次方的一个数。仿制测验以下

public class TestTableSizeFor {
    public static void main(String[] args) {
        System.out.println(tableSizeFor(1));
        System.out.println(tableSizeFor(2));
        System.out.println(tableSizeFor(3));
        System.out.println(tableSizeFor(10));
        System.out.println(tableSizeFor(27));
    }
    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 + 1;
    }
}

为什么阿里巴巴建议HashMap初始化时需要指定容量大小?

HashMap初始容量机遇

在Jdk 1.7和Jdk 1.8中,HashMap初始化这个容量的机遇不同。jdk1.8中,在调用HashMap的构造函数定义HashMap的时分,就会进行容量的设定。而在Jdk 1.7中,要比及第一次put操作时才进行这一操作。

咱们能够通过反射来验证一下。

public static void main(String[] args) {
        int aHundredMillion = 10000000;
        Map<Integer, Integer> map = new HashMap<>();
        long s1 = System.currentTimeMillis();
        for (int i = 0; i < aHundredMillion; i++) {
            map.put(i, i);
        }
        long s2 = System.currentTimeMillis();
        System.out.println("未初始化容量,耗时 : " + (s2 - s1));
        Map<Integer, Integer> map1 = new HashMap<>(aHundredMillion / 2);
        long s5 = System.currentTimeMillis();
        for (int i = 0; i < aHundredMillion; i++) {
            map1.put(i, i);
        }
        long s6 = System.currentTimeMillis();
        System.out.println("初始化容量5000000,耗时 : " + (s6 - s5));
        Map<Integer, Integer> map2 = new HashMap<>(aHundredMillion);
        long s3 = System.currentTimeMillis();
        for (int i = 0; i < aHundredMillion; i++) {
            map2.put(i, i);
        }
        long s4 = System.currentTimeMillis();
        System.out.println("初始化容量为10000000,耗时 : " + (s4 - s3));
    }

由于HashMap没有容量这个特点,可是capacity办法会回来容量

JDK1.7

为什么阿里巴巴建议HashMap初始化时需要指定容量大小?

在jdk1.7初始化容量的机遇是在第一次put的时分,咱们能够检查一下capacity()源码

为什么阿里巴巴建议HashMap初始化时需要指定容量大小?

为什么阿里巴巴建议HashMap初始化时需要指定容量大小?

1.7中capacity()办法回来的是table.length即HashMap的容量,而构造办法并没有对改特点进行赋值操作。反而是在第一次put的时分才进行了操作。

为什么阿里巴巴建议HashMap初始化时需要指定容量大小?

为什么阿里巴巴建议HashMap初始化时需要指定容量大小?

put()—->inflateTable()—->table中才进行操作

JDK1.8

jdk1.8中,在调用HashMap的构造函数定义HashMap的时分,就会进行容量的设定。

赋值了threshold特点

为什么阿里巴巴建议HashMap初始化时需要指定容量大小?

检查capacity()办法,HashMap容量回来的是threshold特点

为什么阿里巴巴建议HashMap初始化时需要指定容量大小?

HashMap中初始容量的合理值

当咱们运用HashMap(int initialCapacity)来初始化容量的时分,jdk会默许帮咱们核算一个相对合理的值当做初始容量。那么,是不是咱们只需要把已知的HashMap中行将寄存的元素个数直接传给initialCapacity就能够了呢?

关于这个值的设置,在《阿里巴巴Java开发手册》有以下主张:

initialCapacity = (需要存储的元素个数 / 负载因子) + 1。留意负载因子(即 loader factor)默许 为 0.75,假如暂时无法确定初始值巨细,请设置为 16(即默许值)。

也就是说,假如咱们设置的默许值是7,通过Jdk处理之后,会被设置成8,可是,这个HashMap在元素个数到达 8*0.75 = 6的时分就会进行一次扩容,这显着是咱们不期望见到的。

假如咱们通过expectedSize / 0.75F + 1.0F核算,7/0.75 + 1 = 10 ,10通过Jdk处理之后,会被设置成16,这就大大的减少了扩容的几率。

当HashMap内部保护的哈希表的容量到达75%时(默许情况下),会触发rehash,而rehash的进程是比较耗费时刻的。所以初始化容量要设置成expectedSize/0.75 + 1的话,能够有用的减少抵触也能够减小误差。

所以,我能够以为,当咱们明确知道HashMap中元素的个数的时分,把默许容量设置成expectedSize / 0.75F + 1.0F是一个在功能上相对好的挑选,可是,同时也会牺牲些内存。

总结

当咱们想要在代码中创立一个HashMap的时分,假如咱们已知这个Map中行将寄存的元素个数,给HashMap设置初始容量能够在一定程度上进步功率。在已知HashMap中将要寄存的KV个数的时分,设置一个合理的初始化容量按照 expectedSize / 0.75F + 1.0F 能够有用的进步功能,减少扩容次数。

可是,JDK并不会直接拿用户传进来的数字当做默许容量,而是会进行一番运算,最终得到一个2的幂。得到这个数字的算法其实是运用了运用无符号右移和按位或运算来进步功率。

参阅文章

www.hollischuang.com/archives/35…

www.freesion.com/article/265…