智能摘要文章源自JAVA秀-https://www.javaxiu.com/40922.html
MyBatis、Redis、MongoDB、ES、分库分表、读写分离、SpringMVC、Webflux、权限、WebSocket、Dubbo、RabbitMQ、RocketMQ、Kafka、性能测试等等内容。提供近3W行代码的SpringBoot示例，以及超6W行代码的电商微服务项目。文章源自JAVA秀-https://www.javaxiu.com/40922.html
原文约 5712 字 | 图片 10 张 | 建议阅读 12 分钟 | 评价反馈文章源自JAVA秀-https://www.javaxiu.com/40922.html
【面朝大厂】盘点 HashMap 源码中的那些优雅的设计！
点击关注 ? Java基基 文章源自JAVA秀-https://www.javaxiu.com/40922.html
收录于话题文章源自JAVA秀-https://www.javaxiu.com/40922.html
#Java基基299文章源自JAVA秀-https://www.javaxiu.com/40922.html
#面朝大厂7文章源自JAVA秀-https://www.javaxiu.com/40922.html
点击上方“Java基基”，选择“设为星标”文章源自JAVA秀-https://www.javaxiu.com/40922.html
做积极的人，而不是积极废人！文章源自JAVA秀-https://www.javaxiu.com/40922.html
每天 14:00 更新文章，每天掉亿点点头发...文章源自JAVA秀-https://www.javaxiu.com/40922.html
文章源自JAVA秀-https://www.javaxiu.com/40922.html 源码精品专栏文章源自JAVA秀-https://www.javaxiu.com/40922.html
原创 | Java 2021 超神之路，很肝~文章源自JAVA秀-https://www.javaxiu.com/40922.html
中文详细注释的开源项目文章源自JAVA秀-https://www.javaxiu.com/40922.html
RPC 框架 Dubbo 源码解析文章源自JAVA秀-https://www.javaxiu.com/40922.html
网络应用框架 Netty 源码解析文章源自JAVA秀-https://www.javaxiu.com/40922.html
消息中间件 RocketMQ 源码解析文章源自JAVA秀-https://www.javaxiu.com/40922.html
数据库中间件 Sharding-JDBC 和 MyCAT 源码解析文章源自JAVA秀-https://www.javaxiu.com/40922.html
作业调度中间件 Elastic-Job 源码解析文章源自JAVA秀-https://www.javaxiu.com/40922.html
分布式事务中间件 TCC-Transaction 源码解析文章源自JAVA秀-https://www.javaxiu.com/40922.html
Eureka 和 Hystrix 源码解析文章源自JAVA秀-https://www.javaxiu.com/40922.html
Java 并发源码文章源自JAVA秀-https://www.javaxiu.com/40922.html
来源：blog.csdn.net/m0_37892044/文章源自JAVA秀-https://www.javaxiu.com/40922.html
article/details/108329893文章源自JAVA秀-https://www.javaxiu.com/40922.html
一、HashMap构造器文章源自JAVA秀-https://www.javaxiu.com/40922.html
二、HashMap插入机制文章源自JAVA秀-https://www.javaxiu.com/40922.html
1.插入方法源码文章源自JAVA秀-https://www.javaxiu.com/40922.html
2.插入流程图文章源自JAVA秀-https://www.javaxiu.com/40922.html
三、总结文章源自JAVA秀-https://www.javaxiu.com/40922.html
文章源自JAVA秀-https://www.javaxiu.com/40922.html
一、HashMap构造器
HashMap总共给我们提供了三个构造器来创建HashMap对象。文章源自JAVA秀-https://www.javaxiu.com/40922.html
1.无参构造函数public HashMap()：使用无参构造函数创建的hashmap对象，其默认容量为16，默认的负载因子为0.75。文章源自JAVA秀-https://www.javaxiu.com/40922.html
2.有参构造函数public HashMap(int initialCapacity，float loadFactor)：使用该构造函数，我们可以指定hashmap的初始化容量和负载因子，但是在hashmap底层不一定会初始化成我们传入的容量，而是会初始化成大于等于传入值的最小的2的幂次方，比如我们传入的是17，那么hashmap会初始化成32（2^5）。那么hashmap是如何高效计算大于等于一个数的最小2的幂次方数的呢，源码如下：文章源自JAVA秀-https://www.javaxiu.com/40922.html
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; }它的设计可以说很巧妙，其基本思想是如果一个二进制数低位全是1，那么这个数+1则肯定是一个2的幂次方数。举个例子看一下：文章源自JAVA秀-https://www.javaxiu.com/40922.html
文章源自JAVA秀-https://www.javaxiu.com/40922.html
图片文章源自JAVA秀-https://www.javaxiu.com/40922.html
可以看到，它的计算过程是：首先将我们指定的那个数cap减1（减1的原因是，如果cap正好是一个2的幂次方数，也可以正确计算），然后对cap-1分别无符号右移1位、2位，4位、8位、16位(加起来正好是31位)，并且每次移位后都与上一个数做按位或运算，通过这样的运算，会使得最终的结果低位都是1。那么最终对结果加1，就会得到一个2的幂次方数。文章源自JAVA秀-https://www.javaxiu.com/40922.html
3.另一个有参构造函数就是有参构造函数public HashMap(int initialCapacity),该构造函数和上一个构造函数唯一不同之处就是不能指定负载因子。文章源自JAVA秀-https://www.javaxiu.com/40922.html
推荐下自己做的 Spring Boot 的实战项目：文章源自JAVA秀-https://www.javaxiu.com/40922.html
https://github.com/YunaiV/ruoyi-vue-pro文章源自JAVA秀-https://www.javaxiu.com/40922.html
二、HashMap插入机制
1.插入方法源码
public V put(K key, V value) { return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 初始化桶数组 table， table 被延迟到插入新数据时再进行初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 如果桶中不包含键值对节点引用，说明当前数组下标下不存在任何数据，则将新键值对节点的引用存入桶中即可 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; //如果hash相等，并且equals方法返回true，这说明key相同，此时直接替换value即可，并且返回原值 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //如果第一个节点是树节点，则调用putTreeVal方法，将当前值放入红黑树中 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //如果第一个节点不是树节点，则说明还是链表节点，则开始遍历链表，将值存储到链表合适的位置 for (int binCount = 0; ; ++binCount) { //如果遍历到了链接末尾，则创建链表节点，将数据存储到链表结尾 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //判断链表中节点树是否超多了阈值8，如果超过了则将链表转换为红黑树（当然不一定会转换，treeifyBin方法中还有判断） if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //如果在链表中找到，完全相同的key，则直接替换value if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //e!=null说明只是遍历到中间就break了，该种情况就是在链表中找到了完全相等的key,该if块中就是对value的替换操作 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; //加入value之后，更新size，如果超过阈值，则进行扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }2.插入流程图
文章源自JAVA秀-https://www.javaxiu.com/40922.html
图片文章源自JAVA秀-https://www.javaxiu.com/40922.html
（1）在put一个k-v时，首先调用hash()方法来计算key的hashcode,而在hashmap中并不是简单的调用key的hashcode求出一个哈希码，还用到了扰动函数来降低哈希冲突。源码如下：文章源自JAVA秀-https://www.javaxiu.com/40922.html
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }从源码中可以看到，最终的哈希值是将原哈希码和原哈希码右移16位得到的值进行异或运算的结果。16正好是32的一半，因此hashmap是将hashcode的高位移动到了低位，再通过异或运算将高位散播的低位，从而降低哈希冲突。文章源自JAVA秀-https://www.javaxiu.com/40922.html
至于为什么能够降低冲突呢，我们可以看看作者对hash方法的注释：文章源自JAVA秀-https://www.javaxiu.com/40922.html
Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide.(Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed,utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don’t benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.从注释中我们可以得出，作者进行高位向低位散播的原因是：由于hashmap在计算bucket下标时，计算方法为hash&n-1,n是一个2的幂次方数，因此hash&n-1正好取出了hash的低位，比如n是16，那么hash&n-1取出的是hash的低四位，那么如果多个hash的低四位正好完全相等，这就导致了always collide（冲突），即使hash不同。因此将高位向低位散播，让高位也参与到计算中，从而降低冲突，让数据存储的更加散列。文章源自JAVA秀-https://www.javaxiu.com/40922.html
（2）在计算出hash之后之后，调用putVal方法进行key-value的存储操作。在putVal方法中首先需要判断table是否被初始化了（因为hashmap是延迟初始化的，并不会在创建对象的时候初始化table），如果table还没有初始化，则通过resize方法进行扩容。文章源自JAVA秀-https://www.javaxiu.com/40922.html
if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;（3）通过(n-1)&hash计算出当前key所在的bucket下标，如果当前table中当前下标中还没有存储数据，则创建一个链表节点直接将当前k-v存储在该下标的位置。文章源自JAVA秀-https://www.javaxiu.com/40922.html
if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);（4）如果table下标处已经存在数据，则首先判断当前key是否和下标处存储的key完全相等，如果相等则直接替换value，并将原有value返回，否则继续遍历链表或者存储到红黑树。文章源自JAVA秀-https://www.javaxiu.com/40922.html
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))) e = p;（5）当前下标处的节点是树节点，则直接存储到红黑树中文章源自JAVA秀-https://www.javaxiu.com/40922.html
else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);（6）如果不是红黑树，则遍历链表，如果在遍历链表的过程中，找到相等的key，则替换value，如果没有相等的key，就将节点存储到链表尾部（jdk8中采用的是尾插法），并检查当前链表中的节点树是否超过了阈值8，如果超过了8，则通过调用treeifyBin方法将链表转化为红黑树。文章源自JAVA秀-https://www.javaxiu.com/40922.html
for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; }（7）将数据存储完成之后，需要判断当前hashmap的大小是否超过扩容阈值Cap*load_fact,如果大于阈值，则调用resize()方法进行扩容。文章源自JAVA秀-https://www.javaxiu.com/40922.html
f (++size > threshold) resize();HashMap在扩容后的容量为原容量的2倍，起基本机制是创建一个2倍容量的table，然后将数据转存到新的散列表中，并返回新的散列表。和jdk1.7中不同的是，jdk1.8中多转存进行了优化，可以不再需要重新计算bucket下标，其实现源码如下：文章源自JAVA秀-https://www.javaxiu.com/40922.html
文章源自JAVA秀-https://www.javaxiu.com/40922.html
图片文章源自JAVA秀-https://www.javaxiu.com/40922.html
从源码中我们可以看出，如果一个key hash和原容量oldCap按位与运算结果为0，则扩容前的bucket下标和扩容后的bucket下标相等，否则扩容后的bucket下标是原下标加上oldCap。文章源自JAVA秀-https://www.javaxiu.com/40922.html
推荐下自己做的 Spring Cloud 的实战项目：文章源自JAVA秀-https://www.javaxiu.com/40922.html
https://github.com/YunaiV/onemall文章源自JAVA秀-https://www.javaxiu.com/40922.html
三、总结
使用的基本原理总结如下：文章源自JAVA秀-https://www.javaxiu.com/40922.html
1、如果一个数m和一个2的幂次方数n进行按位与运算不等于0，则有：m&(n2-1)=m&(n-1)+n理解：一个2的幂次方数n，在二进制中只有一位为1（假设第k位是1），其他位均为0，那个如果一个数m和n进行按位与运算结果为0的话，则说明m的二进制第k位肯定为0，那么m的前n位和前n-1位所表示的值肯定是相等的。文章源自JAVA秀-https://www.javaxiu.com/40922.html
2、如果一个数m和一个2的幂次方数n进行按位与运算等于0，则有：m&(n2-1)=m&(n-1)理解：一个2的幂次方数n，在二进制中只有一位为1（假设第k位是1），其他位均为0，那个如果一个数m和n进行按位与运算结果不为0的话，则说明m的二进制第k位肯定为1，那么m的前n位和前n-1位所表示的值的差恰好是第k位上的1所表示的数，二这个数正好是n。文章源自JAVA秀-https://www.javaxiu.com/40922.html
原理图：文章源自JAVA秀-https://www.javaxiu.com/40922.html
文章源自JAVA秀-https://www.javaxiu.com/40922.html
图片文章源自JAVA秀-https://www.javaxiu.com/40922.html
- END -文章源自JAVA秀-https://www.javaxiu.com/40922.html
欢迎加入我的知识星球，一起探讨架构，交流源码。加入方式，长按下方二维码噢：文章源自JAVA秀-https://www.javaxiu.com/40922.html
文章源自JAVA秀-https://www.javaxiu.com/40922.html
已在知识星球更新源码解析如下：文章源自JAVA秀-https://www.javaxiu.com/40922.html
文章源自JAVA秀-https://www.javaxiu.com/40922.html
文章源自JAVA秀-https://www.javaxiu.com/40922.html
文章源自JAVA秀-https://www.javaxiu.com/40922.html
文章源自JAVA秀-https://www.javaxiu.com/40922.html
最近更新《芋道 SpringBoot 2.X 入门》系列，已经 101 余篇，覆盖了 MyBatis、Redis、MongoDB、ES、分库分表、读写分离、SpringMVC、Webflux、权限、WebSocket、Dubbo、RabbitMQ、RocketMQ、Kafka、性能测试等等内容。文章源自JAVA秀-https://www.javaxiu.com/40922.html
提供近 3W 行代码的 SpringBoot 示例，以及超 6W 行代码的电商微服务项目。文章源自JAVA秀-https://www.javaxiu.com/40922.html
获取方式：点“在看”，关注公众号并回复 666 领取，更多内容陆续奉上。文章源自JAVA秀-https://www.javaxiu.com/40922.html
文章源自JAVA秀-https://www.javaxiu.com/40922.html
文章有帮助的话，在看，转发吧。谢谢支持哟 (*^__^*）文章源自JAVA秀-https://www.javaxiu.com/40922.html
阅读原文文章源自JAVA秀-https://www.javaxiu.com/40922.html
评论