一.面试题问题

准备用HashMap存1W条数据，构造时传10000还会触发扩容吗？存1000呢？

1.分析源码

HashMap 的初始化
在 HashMap 中，提供了一个指定初始容量的构造方法 HashMap(int initialCapacity)，这个方法再通过 DEFAULT_LOAD_FACTOR 调用 HashMap 另一个构造方法，初始化 loadFactor 为 0.75。

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
  	......
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}
1
2
3
4
5
6
7
8

  构造方法初始化了两个成员变量 threshold 和 loadFactor，其中 threshold 就是用来存储触发 HashMap 扩容的阈值，也就是说，当 HashMap 存储的数据量达到 threshold 时，就会触发扩容。
  从改造方法中可以看出，threshold 并没有直接使用传入的 initialCapacity 作为扩容阈值，而是通过 tableSizeFor 方法处理后再赋值给 threshold。

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
2
3
4
5
6
7
8
9

tableSizeFor 的作用就是寻找大于 cap 的 2 的整数次方，例如如果传入 10，经过 tableSizeFor 处理后返回 16。(文章最后详讲怎么计算的)

2.答案

  如果我们从外部传递进来 10000 初始化 initialCapacity ，实际上经过 tableSizeFor 方法处理之后，最终 threshold 就会变成 2 的 14 次幂 16384，再在 resize 方法中乘上负载因子 0.75，实际在不触发扩容的前提下，可存储的数据容量是 12288(16384 * 0.75)，用来存放 10000 条数据，绰绰有余，所以并不会触发扩容。
  如果我们从外部传递进来 1000 初始化 initialCapacity ，实际上经过 tableSizeFor 方法处理之后，最终 threshold 就会变成 2 的 10 次幂 1024，再在 resize 方法中乘上负载因子 0.75，实际在不触发扩容的前提下，可存储的数据容量是 768 (1024* 0.75)，它是不足以承载 1000 条数据的，最终在存够 1k 条数据之前，还会触发一次动态扩容。

3.如何选择initialCapacity

  想要使用 HashMap 存放 10000 条数据，应该设置 initialCapacity = 10000 / 0.75 + 1 = 13334，然后哈希表容量会被 tableSizeFor 方法调整到 16384(2^14)，threshold = 16384 * 0.75 = 12288 足够存储 10000 条数据而不会触发扩容。
  想要使用 HashMap 存放 1000 条数据，应该设置 initialCapacity = 1000 / 0.75 + 1 = 1334，然后哈希表容量会被 tableSizeFor 方法调整到 1024(2^10)，threshold = 1024* 0.75 = 768 足够存储 1000条数据而不会触发扩容。

4.总结

• HashMap 构造方法传递的 initialCapacity 实际表示哈希表的容量，不代表扩容阈值。
• 构造方法传递的 initialCapacity，会被 tableSizeFor 方法调整为大于它的 2 的整数次方。
• 如果使用 initialCapacity 进行初始化，HashMap 是否扩容，由 threshold 决定，扩容阈值 threshold = initialCapacity * loadFactor。
• 在初始化 HashMap 时，必须指定 initialCapacity 来提升效率，initialCapacity = (需要存储元素个数 / loadFactor(默认0.75)) + 1。

5.拓展:tableSizeFor的计算方式

我们先复习一下<< >>

2 << 3  
<<表示乘  2 *（2的3次方）= 16
16 >> 4
>>表示除  16 / (2的4次方) = 1
16 >>> 4 （如果前面是负数高位补0和这个有点区别）
>>>表示除  16 / (2的4次方) = 1
1
2
3
4
5
6

|=表示或运算
下面就来计算了，我们cap传10

int n = cap - 1; //n=9
n |= n >>> 1;   //9/2=4
0000 1001(二进制) 9
0000 0100        4
或运算的结果是0000 1101=13
n |= n >>> 2;//13/4=3
0000 1101       13
0000 0011        3
或运算的结果是0000 1111=15  下面三个都是15了
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
第一个是false,走(n >= MAXIMUM_CAPACITY)这个也是false 走n+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14

(n >= MAXIMUM_CAPACITY)为啥是false，我们来看源码，这个值到底是多少
1 * (2的30次方)