HashMap的初始容量连环炮

Java集合面试题 1 1.0K

1. 为什么HashMap的初始容量是16？

我们知道扩容是个耗时的过程，有大量链表操作，16作为一个折中的值，即不会存入极少的内容就扩容，也不会在加入大量数据而扩容太多次。16扩容3次就达到128的长度。

其实还有一个很重要的地方，16是2的4次方，我们在看HashMap的源码时，可以看到初始容量的定义方式如下：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

2. 为什么初始容量是2的多次方比较好？

这是我们计算插入位置的算法，n代表的就是容量。假设我们没有设置容量，也没扩容过，那么这个n就是16，n-1=15

if ((p = tab[i = (n - 1) & hash]) = = null)
            tab[i] = newNode(hash, key, value, null);

演示计算过程

1101 0011 0010 1110 0110 0100 0010 1011 `原数`

0000 0000 0000 0000 0000 0000 0000 1111 `15的二进制`

0000 0000 0000 0000 0000 0000 0000 0011 `结果`

我们发现，插入位置实际上又原数的最低的4位决定的，每个位置都有插入的可能。

3. 初始容量如果不是2的次方呢？

HashMap确实提供我们手动设置初始容量

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);

假如我们设置为17，我们看一下计算插入位置的过程，hash & 16

1101 0011 0010 1110 0110 0100 0010 1011 `原数`

0000 0000 0000 0000 0000 0000 0001 0000 `16的二进制`

0000 0000 0000 0000 0000 0000 0000 0000 `结果`

我们发现16的二进制只有一个为1其他都是0，其他数字与上它，不是16就是0。也就是说，这简直是Hash冲突的噩梦。

你将会得到一个Java双单向链表

再举例,初始长度是15 , hash & 14

1101 0011 0010 1110 0110 0100 0010 1011 `原数`

0000 0000 0000 0000 0000 0000 0000 1110 `14的二进制`

0000 0000 0000 0000 0000 0000 0000 0000 `结果`

结果发现，最后一位永远是0，那么0,2,4,6,8,10,12,14这几位就无法插入上了。

这也是2N的性质，2N-1,结果为全是1，插入的位置由原数决定，每个点都有机会插入。

4. HashMap对于你输入非2的次方的数，会怎么样？

当然HashMap不会让你们这么做的，实际上你给定的初始容量，HashMap还会判断是不是2的次幂，如果不是，则给出一个大于给定容量的最小2的次幂的值作为新的容量。

public HashMap(int initialCapacity, float loadFactor) {
 ...
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

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

这也验证了一个重要的编程思想：永远要把客户当成傻子。

1. 为什么HashMap的初始容量是16？

2. 为什么初始容量是2的多次方比较好？

3. 初始容量如果不是2的次方呢？

4. HashMap对于你输入非2的次方的数，会怎么样？

发表评论 取消回复

发表评论取消回复