文章目录
- 前言
- 一、Put方法核心流程
- 二、自定义类型当作Key传入
- 三、HashMap的构造方法
- 3.1 无参构造器如下：
- 3.2 有参构造器如下：
- 三、resize方法
- 四、Set集合和Map集合的关系（拓展）
- 总结
前言
上一篇博主对HashMap中的属性和Put方法进行了逐句解读，链接如下：
HashMap源码解读（中篇）
本篇将解读HashMap的resize()方法，构造方法，以及拓展一些HashMap中的特性。
一、Put方法核心流程
1 若HashMap还未初始化，先进行哈希表的初始化操作（默认初始化为16个桶）
2.对传入的Key值做hash，得出要存放该元素的桶编号
- a.若没有发生碰撞，即头节点为空，将该节点直接存放到桶中作为头节点
- b.若发生碰撞 （1） 此时桶中的链表已经树化，将节点构造为树节点后加入红黑树 （2） 链表还未树化，将节点作为链表的最后一个节点入链表
3.若哈希表中存在key值相同的元素，替换为最新的value值
4.若桶满了( size是否大于threshold)，调用resize()扩容哈希表。（threshold = 容量*负载因子）
二、自定义类型当作Key传入
现自定义一个Student类：
代码语言：javascript复制class Student {
private String name;
private int age;
}若自定义的类型需要保存到Map的Key中，则需要同时覆写hashCode和equals，equals相同的俩对象，hashCode必须相同，反之不一定。
覆写后，Student类如下：
代码语言：javascript复制class Student {
private String name;
private int age;
@Override
public int hashCode() {
return Objects.hash(name, age);
}
public Student(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj instanceof Student) {
Student stu = (Student) obj;
return this.age == stu.age && this.name.equals(stu.name);
}
return false;
}
@Override
public String toString() {
return "Student{"
"name='" name '''
", age=" age
'}';
}
}注意：代码中返回的是Object的工具类Objects，传入的属性值相同返回相同的hash值。
三、HashMap的构造方法
3.1 无参构造器如下：
当new一个HashMap的时候，若没有指定HashMap大小，默认调用无参构造器，可是此时内部数组还没有初始化，代码中只是简单的把负载因子初始化了，只有当第一次调用put方法时才初始化内部哈希桶数组（懒加载模式）。 第一次使用（添加）时才初始化相应的内存。
3.2 有参构造器如下：
如图红色框框，代码检查传入的参数是否2的n次幂，若不是调整为最接近
的数。
例如：传入31，实际上初始化后threshold为32。
三、resize方法
源码如下：
代码语言：javascript复制final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j oldCap] = hiHead;
}
}
}
}
}
return newTab;
}源码解读如下：
1.若oldTab 为 null ，则证明还没有初始化。
2. 当旧数组不为空的时候，新数组拓展为原数组的一倍。（扩容操作）
3.初始化操作
4.元素搬移操作，把链表上的元素头插到扩容后的哈希桶中。
详情版本请看如下：
代码语言：javascript复制//扩容兼初始化
final Node<K,V>[] resize() {
/**
* 当前所有元素所在的数组，称为老的元素数组,或称为临时数组
* （即首次为0，第二次插入时为1：前提是此map是用无参构造函数或者设置容量的构造函数实现的）
* 即 public NandaoHashMap()；public NandaoHashMap(int initialCapacity)；public NandaoHashMap(int initialCapacity,float loadFactor)三种
*
* （如果首次不为0：前提是此map是用有参构造函数实现的）public NandaoHashMap(Map<? extends K,? extends V> m)
*/
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;//现在的hash表容量，第一次无参构造函数初始化时为0,指数组长度，即老的元素数组长度
int oldThr = threshold;//现在的扩容前的临界值（阈值），即老的扩容阀值设置
int newCap, newThr = 0; //新的容量，新的阈值，即新数组的容量，新数组的扩容阀值都初始化为0
//step1
if (oldCap > 0) { //hash表容量不为0时，如果老数组长度大于0，说明已经存在元素（比如第二次为 1 ，或第12次为12 时等6种可能情况）
/**
* 如果hash表容量已达到最大临界值，则返回原数组，并且扩容临界值保持不变，
* 否则，数组扩容一倍且扩容后的表不能大于限制值，将扩容临界值（该临界值还未乘以加载因子）翻倍
*
* 原数组长度大于最大容量(1073741824) 则将threshold设为Integer.MAX_VALUE=2147483647
* 接近MAXIMUM_CAPACITY的两倍
*
* 如果数组元素个数大于等于限定的最大容量（2的30次方）
* 扩容阀值设置为int最大值（2的31次方 -1 ），因为oldCap再乘2就溢出了。
*/
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;// 返回老的元素数组
}
/**
* 如果数组元素个数在正常范围内，那么新的数组容量为老的数组容量的2倍（左移1位相当于乘以2）
* 如果扩容之后的新容量小于最大容量 并且老的数组容量大于等于默认初始化容量（16），那么新数组的扩容阀值设置为老阀值的2倍。
* 即（老的数组容量大于16意味着：要么构造函数指定了一个大于16的初始化容量值，要么已经经历过了至少一次扩容）
*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold // 新数组长度 是原来的2倍， 临界值也扩大为原来2倍
}
/**
* step2
* 运行到这个else if 说明老数组没有任何元素
* 如果老数组的扩容阀值大于0，那么设置新数组的容量为该阀值
* 这一步也就意味着构造该map的时候，指定了初始化容量。
*/
else if (oldThr > 0) // initial capacity was placed in threshold // 容量用阈值
newCap = oldThr; // 如果原来的thredshold大于0则将容量设为原来的thredshold, 在第一次带容量参数初始化时候会有这种情况
else { // zero initial threshold signifies using defaults
// 能运行到这里的话，说明是调用无参构造函数创建的该map，并且第一次添加元素，初始化容量大小（首次初始化）
newCap = DEFAULT_INITIAL_CAPACITY;//第一次创建，使用默认值生成相关参数
// 设置新数组扩容阀值为 16*0.75 = 12; 0.75为负载因子（当元素个数达到容量了4分之3，那么扩容）
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {// 如果新的容量 ==0,即扩容阀值为0 （step1的情况）
float ft = (float)newCap * loadFactor; //第一次扩容初始化阈值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; //更新扩容临界值,即将临界值设置为新临界值,设置map的扩容阀值为 新的阀值(首次为12 = 16 * 0.75)
@SuppressWarnings({"rawtypes","unchecked"})
// 创建新的数组（对于第一次添加元素，那么这个数组就是第一个数组；对于存在oldTab的时候，那么这个数组就是要需要扩容到的新数组）
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];// 扩容，创建hash表，首次初始化扩容为16，即新建Node数组容量为16
table = newTab;//将该map的table属性指向到该新数组（首次初始化扩容大小为16）
// 如果老数组不为空，说明是扩容操作，那么涉及到元素的转移操作
if (oldTab != null) {//已存在hash表，即如果原来的table有数据，则将数据复制到新的table中
for (int j = 0; j < oldCap; j) {//遍历hash表中每个桶，根据容量进行循环整个数组，将非空元素进行复制,即遍历老数组
Node<K,V> e;//临时节点变量，指向旧桶中的节点元素
// 如果当前位置元素不为空，那么需要转移该元素到新数组
if ((e = oldTab[j]) != null) {//如果旧的hash表的当前桶位置存在节点，将值赋值于e，获取数组的第j个元素
oldTab[j] = null;//另该桶的值为null，释放掉老数组对于要转移走的元素的引用（主要为了使得数组可被回收）
// 如果元素没有有下一个节点，说明该元素不存在hash冲突
if (e.next == null)//如果取出来的节点不存在下一个元素，则重新计算对应新hash桶的位置，或如果链表只有一个，则进行直接赋值
/**
* step3
* 把元素存储到新的数组中，存储到数组的哪个位置需要根据hash值和数组长度来进行取模
* 【hash值 % 数组长度】 = 【 hash值 & （数组长度-1）】
* 这种与运算求模的方式要求 数组长度必须是2的N次方，但是可以通过构造函数随意指定初始化容量呀，如果指定了17,15这种，
* 岂不是出问题了就？没关系，最终会通过tableSizeFor方法将用户指定的转化为大于其并且最相近的2的N次方。 15 -> 16、17-> 32
*/
newTab[e.hash & (newCap - 1)] = e;//确定元素存放位置
/**
* 如果该元素有下一个节点，那么说明该位置上存在一个链表了（hash相同的多个元素以链表的方式存储到了老数组的这个位置上了）
* 例如：数组长度为16，那么hash值为1（1=1）的和hash值为17（17=1）的两个元素都是会存储在数组的第2个位置上（对应数组下标为1），
* 当数组扩容为32（12=1）时，hash值为1的还应该存储在新数组的第二个位置上，但是hash值为17（172=17）的就应该存储在新数组的第18个位置上了。
* 所以，数组扩容后，所有元素都需要重新计算在新数组中的位置。
*/
else if (e instanceof TreeNode) //红黑树 https://www.cnblogs.com/finite/p/8251587.html
//四个参数含义 分别是：当前hashMap对象、新数组、正在遍历的旧数组下标、旧数组的长度。
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);//方法的作用是将旧数组转移到新数组
else { // preserve order // 链表,进行链表复制, 方法比较特殊：它并没有重新计算元素在数组中的位置,而是采用了原始位置 原数组长度的方法计算得到位置
Node<K,V> loHead = null, loTail = null;//原桶位置,即按命名来翻译的话，应该叫低位首尾节点
Node<K,V> hiHead = null, hiTail = null;//新桶位置，既扩容一倍后的位置，按命名来翻译的话，应该叫高位首尾节点
Node<K,V> next;// 下一个节点，以上的低位指的是新数组的 0 到 oldCap-1 、高位指定的是oldCap 到 newCap - 1
do {
/**
* 注: e本身就是一个链表的节点，它有自身的值和next(链表的值)，但是因为next值对节点扩容没有帮助，
* 所有在下面讨论中，我近似认为 e是一个只有自身值，而没有next值的元素。
*/
/**
* // 这一步判断好狠，拿元素的hash值 和 老数组的长度 做与运算
* PS3里曾说到，数组的长度一定是2的N次方（例如16），如果hash值和该长度做与运算，那么该hash值可参与计算的有效
* 二进制位就是和长度二进制对等的后几位，如果结果为0，说明hash值中参与计算的对等的二进制位的最高位一定为0.
* 因为数组长度的二进制有效最高位是1（例如16对应的二进制是10000），只有*..0**** 和 10000 进行与运算结果才为
* 00000（*..表示不确定的多个二进制位）。又因为定位下标时的取模运算是以hash值和长度减1进行与运算，所以下标 = (*..0**** & 1111)
* 也= (*..0**** & 11111) 。1111是15的二进制、11111是16*2-1 也就是31的二级制（2倍扩容）。
* 所以该hash值再和新数组的长度取摸的话mod值也不会放生变化，也就是说该元素的在新数组的位置和在老数组的位置是相同的，
* 所以该元素可以放置在低位链表中。
*
*/
next = e.next;//指向下一个节点
/**
* 注意：不是(e.hash & (oldCap-1));而是(e.hash & oldCap)
*
* (e.hash & oldCap) 得到的是 元素的在数组中的位置是否需要移动,示例如下
* 示例1：
* e.hash=10 0000 1010
* oldCap=16 0001 0000
* & =0 0000 0000 比较高位的第一位 0
* 结论：元素位置在扩容后数组中的位置没有发生改变
*
* 示例2：
* e.hash=17 0001 0001
* oldCap=16 0001 0000
* & =1 0001 0000 比较高位的第一位 1
* 结论：元素位置在扩容后数组中的位置发生了改变，新的下标位置是原下标位置 原数组长度
*
* (e.hash & (oldCap-1)) 得到的是下标位置,示例如下
* e.hash=10 0000 1010
* oldCap-1=15 0000 1111
* & =10 0000 1010
*
* e.hash=17 0001 0001
* oldCap-1=15 0000 1111
* & =1 0000 0001
*
* 新下标位置
* e.hash=17 0001 0001
* newCap-1=31 0001 1111 newCap=32
* & =17 0001 0001 1 oldCap = 1 16
*
* 元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
* 参考博文：[Java8的HashMap详解](https://blog.csdn.net/login_sonata/article/details/76598675)
* 0000 0001->0001 0001
*/
if ((e.hash & oldCap) == 0) {//判断当前节点的hash值的比hash表容量高一位的二进制位是否为1，如果为0，则节点保持原桶，如果为1，到新桶
// step4
// 如果原元素位置没有发生变化
if (loTail == null) //原桶位置的链表尾(首次肯定为空),如果没有尾，说明链表为空
loHead = e;//将当前节点设置为链表头,即确定首元素,链表为空时，头节点指向该元素
// 第一次进入时 e -> aa ; loHead-> aa
else
loTail.next = e;// 当前节点追加到尾节点的下一节点,如果有尾，那么链表不为空，把该元素挂到链表的最后。
//第二次进入时 loTail-> aa ; e -> bb ; loTail.next -> bb;而loHead和loTail是指向同一块内存的，所以loHead.next 地址为 bb
//第三次进入时 loTail-> bb ; e -> cc ; loTail.next 地址为 cc;loHead.next.next = cc
loTail = e;//将当前节点设置为尾节点
// 第一次进入时 e -> aa ; loTail-> aa loTail指向了和 loHead相同的内存空间
// 第二次进入时 e -> bb ; loTail-> bb loTail指向了和 loTail.next（loHead.next）相同的内存空间 loTail=loTail.next
// 第三次进入时 e -> cc ; loTail-> cc loTail指向了和 loTail.next(loHead.next.next)相同的内存
}
/**
* 如果与运算结果不为0，说明hash值大于老数组长度（例如hash值为17）,此时该元素应该放置到新数组的高位位置上
* 例：老数组长度16，那么新数组长度为32，hash为17的应该放置在数组的第17个位置上，也就是下标为16，
* 那么下标为16已经属于高位了，低位是[0-15]，高位是[16-31]
*/
else {
if (hiTail == null)//同上，即以下逻辑同sp4
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);//这一块就是 旧链表迁移新链表
//总结：1.8中 旧链表迁移新链表 链表元素相对位置没有变化; 实际是对对象的内存地址进行操作
//在1.7中 旧链表迁移新链表 如果在新表的数组索引位置相同，则链表元素会倒置
if (loTail != null) {// 存在链表,低位的元素组成的链表还是放置在原来的位置
loTail.next = null;// 将链表的尾节点 的next 设置为空
newTab[j] = loHead;
}
if (hiTail != null) {//新桶位置存在链表,高位的元素组成的链表放置的位置只是在原有位置上偏移了老数组的长度个位置。
hiTail.next = null;// 将链表的尾节点 的next 设置为空
// 例：hash为 17 在老数组放置在0下标，在新数组放置在16下标； hash为 18 在老数组放置在1下标，在新数组放置在17下标；
newTab[j oldCap] = hiHead;//当前桶位置 旧的hash表容量
}
}
}
}
}
return newTab;// 返回新数组
}四、Set集合和Map集合的关系（拓展）
先下结论：
Set集合的子类实际上在存储元素时就是放在了Map集合的Key中：
这也是为啥Set是不可重复的！！！
- HashSet其实就是使用HashMap保存的
- TreeSet其实就是使用TreeMap保存的
Set就是用的Map的子类来存储元素，Set的不可重复就是因为元素保存在了Map的Key上。
- HashSet 可以保存null ，因为HashMap的key可以为null
- TreeSet 不可以保存null ，因为TreeMap的key 不能为null。
总结
以上三篇就是HashMap的主要源码解读了，有帮助的话可以点个赞收藏起来慢慢学习~
