全面解析HashMap

全面解析HashMap

mikasa 905 2020-03-13

HashMap是我们常用的集合类,今天我们从头来揭开HashMap的面纱

// HashMap的默认容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// HashMap最大容量 1,073,741,824‬
static final int MAXIMUM_CAPACITY = 1 << 30;
// HashMap的默认负载系数
// 当HashMap的size超过(容量*负载因子)时进行扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;

构造函数

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("...");
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("...");
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

该构造器可设置初始容量和负载系数,重点看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;
}

我们都知道HashMap的容量(capacity)是2的次幂,那么我们初始化容量的时候指定一个非2次幂的值,为何实际容量还是2的次幂呢,是因为tableSizeFor方法的作用就是用于找到大于等于初始容量(initialCapacity)值的最小2的次幂的值(比较绕...)

简单举个例子假设初始化设置的initialCapacity=19,则tableSizeFor(19)返回的就是32。虽然最接近19而又是2的次幂的值是16,但因为19>16=23,又不能让HashMap的容量比初始化的容量更小,所以只能是24 = 32。

tableSizeFor的实现上述的方式是通过右移运算,将cap值的二进制最高位1后面所有低位置为1,辅助理解下面详细分解举例:
例: 假设cap的值为19,首先19转二进制的结果是0001 0011,将最高位1后面的低位全部置为1得到0001 1111,最后再+1,得到 0010 0000,转为十进制得到结果32。

为什么要对cap做减1操作 int n = cap - 1?
这是为了防止cap已经是2的幂,如果cap已经是2的幂,假设没有执行减1操作,则执行完后面的无符号右移操作后,返回的capacity将是这个cap的2倍。

举一个反例验证: 调用tableSizeFor(2)
假设 int n = cap - 1 被修改为 int n = cap 也就是不对cap进行减1
已知 n = 2, 则:
首先对n |= n >>> 1做一个转换得到 n = n | (n>>>1), 将n=2代入,得到n = 2 | (2 >>> 1)2>>>1得到的结果为1,现在得到n = 2 | 1,1的二进制为0001,2的二进制为0010;0001 | 0010 = 0011(b) = 3(d), 之后的右移操作就不用看了,由于举例的数值较小,后续右移的结果都为0,不会改变3的结果所以此处不进行详细描述了,直接看最后一行,带入计算后,上述计算结果+1 则得到4, 4相较于2已经翻了一倍了。

最后将得到的容量大小赋值给threshold注意,这里仅得到容量大小,并没有初始化,在第一次put时调用resize()方法,才会给数组初始化,后面写到resize()时再谈threshold

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

这个构造函数同上,负载系数采用默认的 0.75f

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}

默认构造函数,大概也是最常用的,将默认的负载因子赋值给loadFactor,loadFactor = 0.75f

未完待续(貌似烂尾了,加班出差断断续续在外1年了,有点时间也不想动🖊了)...


# Map