HashMap是我们常用的集合类,今天我们从头来揭开HashMap的面纱
```java
// 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;
```
# 构造函数
```java
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)
```java
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=2^3,又不能让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倍。
**举一个反例验证:** 调用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`。
```java
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
```
这个构造函数同上,负载系数采用默认的 0.75f
```java
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
```
默认构造函数,大概也是最常用的,将默认的负载因子赋值给loadFactor,loadFactor = 0.75f
未完待续(貌似烂尾了,加班出差断断续续在外1年了,有点时间也不想动🖊了)...
全面解析HashMap