全面解析HashMap

全面解析HashMap

Scroll Down

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的次幂,tableSizeFor方法的作用是用于找到大于等于initialCapacity的最小的2的次幂的值

简单举个例子就是,你初始化设置的initialCapacity=19,则tableSizeFor(19)返回的就是32。最接近19而又是2的次幂的值是16,因为16=2^3 ,19>16,你不能让HashMap的容量比初始化的容量更小吧,所以只能是2^4 = 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倍。

举个例子:假设没有 int n = cap - 1; 直接调用tableSizeFor(2),先看 n |= n >>> 1,2 >>> 1 = 1;1的二进制是 0001,2的二进制是 0010 ;0001 | 0010 = 0011(b) = 3(d) , 最后+1 则得到4。

最后将得到的容量大小赋值给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

未完待续...