原文链接:
通俗易懂Hashmap源码解析_java阳开发之路的博客-CSDN博客_hashmap源码
https://www.csdn.net/tags/MtTaEgxsNTYxMDAyLWJsb2cO0O0O.html
深入理解 HashMap put 方法(JDK 8逐行剖析)_stateiso的博客-CSDN博客_hashmap put方法
·
·
一, 先来看几个变量、常量、静态变量、静态常量:
1) Map的默认初始化容量以及容量极限:
//HashMap默认的初始容量大小--16,容量必须是2的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//HashMap的容量极限,为2的30次幂;
static final int MAXIMUM_CAPACITY = 1 << 30;2) 默认负载因子、实际元素数量:
//负载因子的默认大小,
//元素的数量/容量得到的实际负载数值与负载因子进行对比,来决定容量的大小以及是否扩容;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//HashMap的实际元素数量
transient int size;·
3)table——Entry数组;
//Node是Map.Entry接口的实现类,可以将这个table理解为是一个entry数组;
//每一个Node即entry,本质都是一个单向链表
transient Node<K,V>[] table;·
4)Map已经修改的次数、扩容阀值、存储负载因子的常量:
//HashMap已在结构上修改的次数 结构修改是指更改 HashMap 中的映射数量或以其他方式修改其内部结构(例如,重新散列)的那些
transient int modCount;
//下一次HashMap扩容的阀值大小,如果尚未扩容,则该字段保存初始entry数组的容量,或用零表示
int threshold;
//存储负载因子的常量,初始化的时候将默认的负载因子赋值给它;
final float loadFactor;扩容阀值threshold = 负载因子loadFactor * 容量capacity
·
二,HashMap的四个构造函数:
1)构造函数1——默认的无参构造函数:
将默认的负载因子0.75f 传给 存储负载因子的常量;
//默认的构造函数
public HashMap() {
//将默认的负载因子0.75f传给存储负载因子的常量
this.loadFactor = DEFAULT_LOAD_FACTOR;
}2)构造函数2——带指定容量参数的构造函数
将默认的负载因子0.75f当做负载因子常量,连同用户传入的容量参数,一起传给两个参数都带的构造函数,并调用之。
//带指定容量参数的构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}3)构造函数3——带指定容量大小和负载因子大小参数的构造函数
//带指定容量大小和负载因子大小参数的构造函数
public HashMap(int initialCapacity, float loadFactor) {
//指定的容量大小不可以小于0,否则将抛出IllegalArgumentException异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//判定指定的容量大小是否大于HashMap的容量极限
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//指定的负载因子不可以小于0或为Null,否则将抛出IllegalArgumentException异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//传入用户指定的负载因子
this.loadFactor = loadFactor;
//Map扩容的阀值大小
//tableSizeFor方法用于查找到距离容量initialCapacity最近的2次幂值;
this.threshold = tableSizeFor(initialCapacity);
}·
3.5)tableSizeFor()方法:
在刚才的构造函数中,我们看到了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;
}可以看出,其实代码很简单,就是对容量cap进行了几次无符号右移的操作,最后返回。
那么这个方法的目的和作用是什么呢?
这个方法的作用是:用于查找距离容量cap最近的2次幂值,比如:
- cap是5~7,那么该方法的返回结果就是8;
- cap是9~15,那么该方法的返回结果就是16;
- cap是17~31,那么该方法的返回结果就是32;
- 以此类推...
·
4)构造函数4——传入一个Map集合的构造函数:
此构造方法主要实现了Map.putAll()方法。
//传入一个Map集合,将Map集合中元素Map.Entry全部添加进HashMap实例中
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
//此构造方法主要实现了Map.putAll()
putMapEntries(m, false);
}·
·
三,HashMap的初始化:
1)HashMap无论如何初始化,其容量都为0;
刚才我们讲到,HashMap的构造函数有四种,1、默认的无参构造函数;2、带指定容量参数的构造函数;3、带指定容量大小和负载因子大小参数的构造函数;4、传入一个Map集合的构造函数。
//无参的构造函数
public HashMap() {
//加载负载因子;
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//传入容量参数的构造函数
public HashMap(int initialCapacity) {
//调用下边的构造函数
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//传入容量参数和负载因子的构造函数
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
//传入一个Map,核心是使用了putAll方法
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}可以看出,其实用户在新建一个HashMap的时候,不管有没有传入容量参数,HashMap在初始化的时候其容量都是为0;
比如说,如果用户没有传入容量参数,那么调用的是无参的构造函数进行初始化,此时容量为0;
如果用户传入了容量参数,那么也只是将容量参数initialCapacity通过tableSizeFor方法找出距离该initialCapacity最近的2的幂次方数值,然后将该数值赋给了扩容阀值threshold;
为什么不管怎么初始化、用哪个构造函数,HashMap在初始化的时候其容量都是0呢?
这是因为HashMap使用的懒加载机制,只有你第一次向HashMap中添加元素时,才进行第一次的容量设置,
查看put()方法的源码:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}继续查看putVal()的源码:
这里我们只分析关于触发初始化容量阀值和扩容的部分,put元素的详情请参见:HashMap的put方法与get方法_Morning sunshine的博客-CSDN博客
里边有两句源码是这样写的:
//触发初始化容量阀值:
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//...其他代码
//触发扩容:
if (++size > threshold)
resize();意思是,如果此时entry数组为null或者entry数组的长度为0,也就是意味着这是第一次put元素,那么会调用resize()方法,
如果entry数组的长度size大于容量阀值threshold了,也会去调用resize()方法。
这个resize()方法是做什么的呢?就是用来初始化容量阀值或者扩容Map的一个方法。
详情请见: