通俗易懂Hashmap源码解析_java阳开发之路的博客-CSDN博客_hashmap源码
https://www.csdn.net/tags/MtTaEgxsNTYxMDAyLWJsb2cO0O0O.html
深入理解 HashMap put 方法&＃xff08;JDK 8逐行剖析&＃xff09;_stateiso的博客-CSDN博客_hashmap put方法
·
·
详情参见&＃xff1a;HashMap的结构与构造函数_Morning sunshine的博客-CSDN博客
//HashMap默认的初始容量大小--16&＃xff0c;容量必须是2的幂static final int DEFAULT_INITIAL_CAPACITY &＃61; 1 <<4; // aka 16//HashMap的容量极限&＃xff0c;为2的30次幂&＃xff1b;static final int MAXIMUM_CAPACITY &＃61; 1 <<30;
//负载因子的默认大小&＃xff0c;//元素的数量/容量得到的实际负载数值与负载因子进行对比&＃xff0c;来决定容量的大小以及是否扩容&＃xff1b;static final float DEFAULT_LOAD_FACTOR &＃61; 0.75f;//HashMap的实际元素数量transient int size;
·
//Node是Map.Entry接口的实现类&＃xff0c;可以将这个table理解为是一个entry数组&＃xff1b;//每一个Node即entry&＃xff0c;本质都是一个单向链表transient Node
·
//HashMap已在结构上修改的次数 结构修改是指更改 HashMap 中的映射数量或以其他方式修改其内部结构&＃xff08;例如&＃xff0c;重新散列&＃xff09;的那些transient int modCount;//下一次HashMap扩容的阀值大小&＃xff0c;如果尚未扩容&＃xff0c;则该字段保存初始entry数组的容量&＃xff0c;或用零表示int threshold;//存储负载因子的常量&＃xff0c;初始化的时候将默认的负载因子赋值给它&＃xff1b;final float loadFactor;
扩容阀值threshold &＃61; 负载因子loadFactor * 容量capacity
·
将默认的负载因子0.75f 传给 存储负载因子的常量&＃xff1b;
//默认的构造函数public HashMap() {//将默认的负载因子0.75f传给存储负载因子的常量this.loadFactor &＃61; DEFAULT_LOAD_FACTOR; }
将默认的负载因子0.75f当做负载因子常量&＃xff0c;连同用户传入的容量参数&＃xff0c;一起传给两个参数都带的构造函数&＃xff0c;并调用之。
//带指定容量参数的构造函数public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}
//带指定容量大小和负载因子大小参数的构造函数
public HashMap(int initialCapacity, float loadFactor) {//指定的容量大小不可以小于0,否则将抛出IllegalArgumentException异常if (initialCapacity <0)throw new IllegalArgumentException("Illegal initial capacity: " &＃43;initialCapacity);//判定指定的容量大小是否大于HashMap的容量极限if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity &＃61; MAXIMUM_CAPACITY;//指定的负载因子不可以小于0或为Null&＃xff0c;否则将抛出IllegalArgumentException异常if (loadFactor <&＃61; 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " &＃43;loadFactor);//传入用户指定的负载因子 this.loadFactor &＃61; loadFactor;//Map扩容的阀值大小//tableSizeFor方法用于查找到距离容量initialCapacity最近的2次幂值&＃xff1b;this.threshold &＃61; tableSizeFor(initialCapacity);
}
·
在刚才的构造函数中&＃xff0c;我们看到了tableSizeFor()这一个方法&＃xff0c;将容量参数传进去&＃xff0c;返回结果赋值给threshold 。
看源码&＃xff1a;
static final int tableSizeFor(int cap) {int n &＃61; cap - 1;n |&＃61; n >>> 1;n |&＃61; n >>> 2;n |&＃61; n >>> 4;n |&＃61; n >>> 8;n |&＃61; n >>> 16;return (n <0) ? 1 : (n >&＃61; MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n &＃43; 1;}
可以看出&＃xff0c;其实代码很简单&＃xff0c;就是对容量cap进行了几次无符号右移的操作&＃xff0c;最后返回。
那么这个方法的目的和作用是什么呢&＃xff1f;
这个方法的作用是&＃xff1a;用于查找距离容量cap最近的2次幂值&＃xff0c;比如&＃xff1a;
·
此构造方法主要实现了Map.putAll()方法。
//传入一个Map集合,将Map集合中元素Map.Entry全部添加进HashMap实例中
public HashMap(Map m) {this.loadFactor &＃61; DEFAULT_LOAD_FACTOR;//此构造方法主要实现了Map.putAll()putMapEntries(m, false);
}
·
·
刚才我们讲到&＃xff0c;HashMap的构造函数有四种&＃xff0c;1、默认的无参构造函数&＃xff1b;2、带指定容量参数的构造函数&＃xff1b;3、带指定容量大小和负载因子大小参数的构造函数&＃xff1b;4、传入一个Map集合的构造函数。
//无参的构造函数
public HashMap() {//加载负载因子&＃xff1b;this.loadFactor &＃61; 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: " &＃43;initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity &＃61; MAXIMUM_CAPACITY;if (loadFactor <&＃61; 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " &＃43;loadFactor);this.loadFactor &＃61; loadFactor;this.threshold &＃61; tableSizeFor(initialCapacity);
}
//传入一个Map&＃xff0c;核心是使用了putAll方法
public HashMap(Map m) {this.loadFactor &＃61; DEFAULT_LOAD_FACTOR;putMapEntries(m, false);
}
可以看出&＃xff0c;其实用户在新建一个HashMap的时候&＃xff0c;不管有没有传入容量参数&＃xff0c;HashMap在初始化的时候其容量都是为0&＃xff1b;
比如说&＃xff0c;如果用户没有传入容量参数&＃xff0c;那么调用的是无参的构造函数进行初始化&＃xff0c;此时容量为0&＃xff1b;
如果用户传入了容量参数&＃xff0c;那么也只是将容量参数initialCapacity通过tableSizeFor方法找出距离该initialCapacity最近的2的幂次方数值&＃xff0c;然后将该数值赋给了扩容阀值threshold&＃xff1b;
为什么不管怎么初始化、用哪个构造函数&＃xff0c;HashMap在初始化的时候其容量都是0呢&＃xff1f;
这是因为HashMap使用的懒加载机制&＃xff0c;只有你第一次向HashMap中添加元素时&＃xff0c;才进行第一次的容量设置&＃xff0c;
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}
继续查看putVal()的源码&＃xff1a;
这里我们只分析关于触发初始化容量阀值和扩容的部分&＃xff0c;put元素的详情请参见&＃xff1a;HashMap的put方法与get方法_Morning sunshine的博客-CSDN博客
里边有两句源码是这样写的&＃xff1a;
//触发初始化容量阀值&＃xff1a;
if ((tab &＃61; table) &＃61;&＃61; null || (n &＃61; tab.length) &＃61;&＃61; 0)n &＃61; (tab &＃61; resize()).length;//...其他代码//触发扩容&＃xff1a;
if (&＃43;&＃43;size > threshold)resize();
意思是&＃xff0c;如果此时entry数组为null或者entry数组的长度为0&＃xff0c;也就是意味着这是第一次put元素&＃xff0c;那么会调用resize()方法&＃xff0c;
如果entry数组的长度size大于容量阀值threshold了&＃xff0c;也会去调用resize()方法。
这个resize()方法是做什么的呢&＃xff1f;就是用来初始化容量阀值或者扩容Map的一个方法。
·
final Node
}
逻辑概括&＃xff1a;
1.1、那么将 用户传入的容量参数 * 用户传入的负载因子loadFactor(也可能是默认的负载因子)&＃xff0c;的计算结果&＃xff0c;赋值给扩容阀值threshold
1.2、将容量参数赋值给变量newCap&＃xff1b;
2.1、那么将 默认负载因子0.75f * 默认的容量大小DEFAULT_INITIAL_CAPACITY&＃xff0c;的计算结果&＃xff0c;赋值给扩容阀值threshold
2.2、将默认容量大小DEFAULT_INITIAL_CAPACITY(16)赋给newCap&＃xff1b;
大小为newCap&＃xff1b;将该初始化好的entry数组返回出去。
关于resize()方法里边的扩容逻辑&＃xff0c;请参见下文&＃xff1b;
·
·
·
static final float DEFAULT_LOAD_FACTOR &＃61; 0.75f;final float loadFactor;public HashMap() {this.loadFactor &＃61; DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
负载因子在初始化Map的时候被赋值&＃xff0c;要么被用户传的参数赋值&＃xff0c;要么被默认的0.75f给赋值&＃xff1b;
默认的负载因子我们之前说过&＃xff1a;0.75f&＃xff0c;当然也可以自己设置&＃xff0c;但 0.75 是最均衡的设置&＃xff0c;没有特殊要求不要修改该值&＃xff0c;
负载因子过小&＃xff0c;说明Node元素比较少&＃xff0c;理论上能减少 hash 冲突&＃xff0c;
负载因子过大&＃xff0c;可以节约空间。
·
在Map的构造函数中&＃xff1a;
public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity <0)throw new IllegalArgumentException("Illegal initial capacity: " &＃43;initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity &＃61; MAXIMUM_CAPACITY;if (loadFactor <&＃61; 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " &＃43;loadFactor);this.loadFactor &＃61; loadFactor;this.threshold &＃61; tableSizeFor(initialCapacity);}
从代码中可以看到&＃xff0c;
如果我们设置的初始化容量小于0&＃xff0c;将会抛出异常&＃xff0c;
如果加载因子小于0也会抛出异常。
同时&＃xff0c;如果初始容量大于最大容量&＃xff0c;则重新设置为最大容量。
·
我们看最后两行代码&＃xff0c;首先&＃xff0c;对负载因子进行赋值&＃xff0c;这个没什么可说的。
牛逼的是下面一行代码&＃xff1a;this.threshold &＃61; tableSizeFor(initialCapacity);
我们进入到该tableSizeFor方法查看&＃xff1a;
static final int tableSizeFor(int cap) {int n &＃61; cap - 1;n |&＃61; n >>> 1;n |&＃61; n >>> 2;n |&＃61; n >>> 4;n |&＃61; n >>> 8;n |&＃61; n >>> 16;return (n <0) ? 1 : (n >&＃61; MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n &＃43; 1;}
可以看出&＃xff0c;其实代码很简单&＃xff0c;就是对容量cap进行了几次无符号右移的操作&＃xff0c;最后返回。
那么这个方法的目的和作用是什么呢&＃xff1f;
这个方法的作用是&＃xff1a;用于查找距离容量initialCapacity最近的2次幂值&＃xff0c;比如&＃xff1a;
我们仔细观察其算法的过程&＃xff0c;可以说&＃xff0c;任何一个int 数字&＃xff0c;都能找到离他最近的 2 的幂次方数字&＃xff08;且比他大&＃xff09;。
·
·
扩容阀值threshold &＃61; 负载因子loadFactor * 容量capacity
·
当entry数组的长度到达了扩容的阀值threshold之后&＃xff0c;就会调用resize()方法进行扩容&＃xff1b;
·
resize方法的两个作用是&＃xff1a;用来初始化一个Map&＃xff0c;或者对Map容量进行扩容。
初始化请参见上文&＃xff1b;
扩容时&＃xff0c;因为我们使用二次幂展开&＃xff0c;每个 bin 中的元素必须保持相同的索引&＃xff0c;或者在新表中以二次幂的偏移量移动。
·
//重新设置table大小/扩容 并返回扩容的Node数组即HashMap的最新数据
final Node
·
1.判定数组是否已达到极限大小&＃xff0c;若判定成功将不再扩容&＃xff0c;直接将老表返回&＃xff1b;
2.若新表大小(oldCap2)小于数组极限大小&老表大于等于数组初始化大小 判定成功则 旧数组大小oldThr 经二进制运算向左位移1个位置 即 oldThr2当作新数组的大小
2.1. 若[2]的判定不成功&＃xff0c;则继续判定 oldThr &＃xff08;代表 老表的下一次扩容量&＃xff09;大于0&＃xff0c;若判定成功 则将oldThr赋给newCap作为新表的容量
2.2 若 [2] 和[2.1]判定都失败,则走默认赋值 代表 表为初次创建
3.确定下一次表的扩容量, 将新表赋予当前表
4.通过for循环将老表中的值存入扩容后的新表中
4.1 获取旧表中指定索引下的Node对象 赋予e 并将旧表中的索引位置数据置空
4.2 若e的下面没有其他节点则将e直接赋到新表中的索引位置
4.3 若e的类型为TreeNode红黑树类型
4.3.1 分割树&＃xff0c;将新表和旧表分割成两个树&＃xff0c;并判断索引处节点的长度是否需要转换成红黑树放入新表存储
4.3.2 通过Do循环 不断获取新旧索引的节点
4.3.3 通过判定将旧数据和新数据存储到新表指定的位置
门限值等于&＃xff08;负载因子&＃xff09;x&＃xff08;容量&＃xff09;&＃xff0c;如果构建 HashMap 的时候没有指定它们&＃xff0c;那么就是依据相应的默认常量值。
门限通常是以倍数进行调整 &＃xff08;newThr &＃61; oldThr <<1&＃xff09;&＃xff0c;我前面提到&＃xff0c;根据 putVal 中的逻辑&＃xff0c;当元素个数超过门限大小时&＃xff0c;则调整 Map 大小。
扩容后&＃xff0c;需要将老的数组中的元素重新放置到新的数组&＃xff0c;这是扩容的一个主要开销来源。
·
·
原文链接&＃xff1a;深入理解 HashMap put 方法&＃xff08;JDK 8逐行剖析&＃xff09;_stateiso的博客-CSDN博客_hashmap的put方法实现原理
我们看看该方法实现&＃xff1a;
final Node
该方法可以说还是比较复杂的。初始的时候也是调用的这个方法&＃xff0c;当链表数超过8的时候同时数组长度小于64的时候也是调用的这个方法。该方法步骤如下&＃xff1a;
1、判断entry数组的长度是否大于0&＃xff0c;如果大于0&＃xff0c;并且已经大于最大值MAXIMUM_CAPACITY&＃xff0c;则设置阀值为 int 类型的最大值&＃xff0c;并返回原数组&＃xff0c;不再扩容&＃xff1b;
2、如果entry数组的长度乘以 2 小于最大容量MAXIMUM_CAPACITY&＃xff0c;且大于等于16&＃xff0c;则更新阀值、就是乘以2。
3、如果老的阀值大于0&＃xff0c;则新的容量等于老的阀值。
4、如果老的阀值和容量都不大于0&＃xff0c;则认为是一个新的数组&＃xff0c;默认初始容量为16&＃xff0c;阀值为 16 * 0.75f&＃xff0c;也就是 12。
5、如果&＃xff0c;新的阀值还是0&＃xff0c;那么就使用我们刚刚设置的容量&＃xff08;HashMap 帮我们算的&＃xff09;&＃xff0c;通过乘以 0.75&＃xff0c;得到一个阀值&＃xff0c;然后判断算出的阀值是否合法&＃xff1a;如果容量小于最大容量并且阀值小于最大容量&＃xff0c;那么则使用该阀值&＃xff0c;否则使用 int 最大值。
6、将刚刚的阀值设置到当前Map实例的阀值属性中。
7、将刚刚的entry数组设置到当前Map实例的entry数组属性中。
8、如果老的entry数组不是null&＃xff0c;则将原来entry数组中的值重新散列到新的entry数组中。如果是null&＃xff0c;直接返回新entry数组。
那么&＃xff0c;将老数组重新散列的过程到底是怎么样的呢&＃xff1f;
·
重新散列的代码&＃xff1a;
// 如果老的数组不是null
if (oldTab !&＃61; null) {// 循环老数组for (int j &＃61; 0; j
}
这里楼主重新贴了上面的代码&＃xff0c;因为这段代码比较重要。还是说一下该部分代码的步骤。
1、首先循环老数组。下标从0开始&＃xff0c;如果对应下标的值不是null&＃xff0c;则判断该值有没有next 节点&＃xff0c;也就是判断是否是链表。
2、如果不是链表&＃xff0c;则根据新的数组长度重新hash该元素。
3、如果该节点是树&＃xff0c;则调用红黑树的 split 方法&＃xff0c;传入当前对象和新数组还有下标&＃xff0c;该方法会重新计算红黑树中的每个hash值&＃xff0c;如果重新计算后&＃xff0c;树中元素的hash值不同&＃xff0c;则重新散列到不同的下标中。达到拆分红黑树的目的&＃xff0c;提高性能。具体如何拆分下面再说。
4、之后的判断就是链表&＃xff0c;在Java8中&＃xff0c;该部分代码不是简单的将旧链表中的数据拷贝到新数组中的链表就完了&＃xff0c;而是会对旧的链表进行重新 hash&＃xff0c;如果 hash 得到的值和之前不同&＃xff0c;则会从旧的链表中拆出&＃xff0c;放到另一个下标中去&＃xff0c;提高性能&＃xff0c;刚刚的红黑树也是这么做的。
这里的重新hash 不是使用的 [e.hash & (newCap - 1)] 方法&＃xff0c;而是使用更加效率的方法&＃xff0c;直接 hash 老的数组容量&＃xff0c;就没有了减一的操作&＃xff0c;可见 JDK 的作者为了性能可以说是无所不用其极了。
其实我们的注释已经写了&＃xff0c;但是楼主还是再解释一遍吧&＃xff1a;
仔细阅读下面这段话&＃xff1a;
oldCap 假如是16&＃xff0c;那么二进制为 10000&＃xff0c;扩容变成 100000&＃xff0c;也就是32.
当旧的hash值 与运算 10000&＃xff0c;结果是0的话&＃xff0c;那么hash值的右起第五位肯定也是0&＃xff0c;那么该于元素的下标位置也就不变。
但如果不是0是1的话&＃xff0c;说明该hash值变化了&＃xff0c;那么就需要对这个元素重新散列放置。
那么应该放哪里呢&＃xff1f;如果是16&＃xff0c;那么最左边是1的话&＃xff0c;说明hash值变大了16&＃xff0c;那么只需要在原有的基础上加上16便好了。
这段代码还有一个需要注意的地方&＃xff1a;在JDK 7 中&＃xff0c;这里的的代码是不同的&＃xff0c;在并发情况下会链表会变成环状&＃xff0c;形成死锁。
而JDK 8 已经修复了该问题&＃xff0c;但是仍然不建议使用 HashMap 并发编程。
截至到这里&＃xff0c;我们的 HashMap 的 put 方法已经剖析完了&＃xff0c;此次可以说收获不小&＃xff1a;
我们知道了&＃xff0c;无论我们如何设置初始容量&＃xff0c;HashMap 都会将我们改成2的幂次方&＃xff0c;也就是说&＃xff0c;HashMap 的容量百分之百是 2的幂次方&＃xff0c;因为HashMap 太依赖他了。
但是&＃xff0c;请注意&＃xff1a;如果我们预计插入7条数据&＃xff0c;那么我们写入7&＃xff0c;HashMap 会设置为 8&＃xff0c;虽然是2的幂次方&＃xff0c;但是&＃xff0c;请注意&＃xff0c;当我们放入第7条数据的时候&＃xff0c;就会引起扩容&＃xff0c;造成性能损失&＃xff0c;所以&＃xff0c;知晓了原理&＃xff0c;我们以后在设置容量的时候还是自己算一下&＃xff0c;比如放7条数据&＃xff0c;我们还是都是设置成16&＃xff0c;这样就不会扩容了。
HashMap 的默认加载因子是 0.75&＃xff0c;虽然可以修改&＃xff0c;但是出于安全考虑&＃xff0c;除非你经过大量测试&＃xff0c;请不要修改此值&＃xff0c;HashMap 使用此值基本是平衡了性能和空间的取舍。
HashMap 扩容的时机是&＃xff0c;容器中的元素数量 > 负载因此 * 容量&＃xff0c;如果负载因子是0.75&＃xff0c;容量是16&＃xff0c;那么当容器中数量达到13 的时候就会扩容。还有&＃xff0c;如果某个链表长度达到了8&＃xff0c;并且容量小于64&＃xff0c;则也会用扩容代替红黑树。
HashMap 在 JDK 7 中并发扩容的时候是非常危险的&＃xff0c;非常容易导致链表成环状。但 JDK 8 中已经修改了此bug。但还是不建议使用。强烈推荐并发容器 ConcurrentHashMap。
HashMap 扩容的时候&＃xff0c;不管是链表还是红黑树&＃xff0c;都会对这些数据进行重新的散列计算&＃xff0c;然后缩短他们的长度&＃xff0c;优化性能。
在进行散列计算的时候&＃xff0c;会进一步优化性能&＃xff0c;减少减一的操作&＃xff0c;直接使用& 运算。可谓神来之笔。
总之&＃xff0c;HashMap 中的优秀的设计思想值得我们去学习&＃xff0c;最让楼主震惊的就是那个将任意一个数变成了2的幂次方的数&＃xff0c;并且该数字很合理&＃xff0c;说实话&＃xff0c;如果让楼主写&＃xff0c;楼主是写不出来的。
所以&＃xff0c;请努力吧&＃xff0c;现在做不到&＃xff0c;不代表以后做不到&＃xff0c;通过学习优秀的源码&＃xff0c;一定能够提高我们的编码能力。
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有 ![[大整数乘法] java代码实现](https://img1.php1.cn/3cd4a/24c6f/9f3/0133bb25da242824.jpeg)