前言
点赞在看，养成习惯。
点赞收藏，人生辉煌。
点击关注【微信搜索公众号：编程背锅侠】，第一时间获得最新文章。
HashMap系列文章
第一篇HashMap源码中的成员变量你还不懂? 来来来！！！整理好的成员变量源码解析
第二篇撸啊撸，再次撸HashMap源码，踩坑源码中构造方法！！！每次都有收获
第三篇MoxiMoxi ！！！你看过HashMap中的put方法的源码吗？
第四篇HashMap源码中的resize扩容方法除了扩容还有一个用途你真的知道吗？
第五篇留一半清醒、留一半醉！！！HashMap中treeifyBin、treeify源码解析
面试官：你能讲讲put方法吧？
1、先通过hash值计算出key映射到哪个桶;2、如果桶上没有发生哈希碰撞冲突，则直接插⼊;3、如果出现了哈希碰撞冲突，则需要处理冲突。【处理方式一：红黑树】如果该桶使用红黑树处理冲突，则调用红黑树的方法插入数据;【处理方式二：链表】否则采用传统的链式⽅法插入。如果链的长度达到临界值，则把链转变为红黑树;4、如果桶中存在重复的键，则为该键替换新值value;5、如果size⼤于阈值threshold，则进行扩容;
put方法以及列表
public V put(K key, V value)添加方法
源码阅读
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}
源码分析
HashMap提供了put方法用于添加元素，从源码中可以看到这个方法调用了putVal方法来真正的添加元素从源码中我们也可以看到putVal方法只是给put方法调用的一个方法，并没有提供给用户使⽤。 所以下面的源码分析中我将重点看putVal⽅法。案例演示
@Testpublic void test_hash_map_put(){HashMap<Integer, String> map = new HashMap<>();// 添加方法map.put(1, "put");// HashMap支持key和value为null。但是只能有且仅有一个key为null。map.put(null, null);// 遍历这个集合map.forEach((k, v) -> System.out.println("k: " + k + " v: " + v));}
总结
在这个map中将指定的key和指定的val做关联，如果这个map之前已经有一个映射对于这个指定的key，那么这个key对应的旧的val将会被替换。
static final int hash(Object key)求哈希值方法
源码阅读
// 获取给定的key对应的哈希值static final int hash(Object key) {// 定义一个变量h,用于接收给定key对应的hashCodeint h;// 返回这个给定key的哈希值return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)解析
如果key等于null;可以看到当key等于null的时候也是有哈希值的，返回的是0。如果key不等于null;首先计算出key的hashCode赋值给h,然后与h无符号右移16位后的二进制进行按位异或运算得到最终的hash值。HashMap是支持Key和value为空的。HashTable是直接⽤Key来获取HashCode所以key为空会抛异常，也可以从源码中看出value为空也抛出空指针异常，并且HashTable的源码注释中有这么一句注释@exception NullPointerException if the key or value is。&与运算和^异或运算
&与运算运算规则:相同的二进制数位上，都是1的时候，结果为1，否则为零。案例：5 & 11 = 15 0101&11 1011………………………………结果： 0001【运算结果：1】
^异或运算运算规则:相同的二进制数位上，数字相同，结果为0，不同为1。案例：5 ^ 11 = 145 0101^11 1011………………………………结果： 1110【运算结果：14】
(h = key.hashCode()) ^ (h >>> 16)演示
h = key.hashCode(): 1111 1111 1111 1111 1111 1010 1100 1010这个值代表哈希code值………………………………………………………………………………………………………………………………………………………………………………………………………………………………h: 1111 1111 1111 1111 1111 1010 1100 1010h >>>16 : 0000 0000 0000 0000 1111 1111 1111 1111 h ^ (h >>> 16): 1111 1111 1111 1111 0000 0101 0011 0101………………………………………………………………………………………………………………………………………………………………………………………………………………………………(n - 1)&hash计算的是在集合中的插入桶的位置n - 1: 0000 0000 0000 0000 0000 0000 0000 1111【假设的容量为16-1=15】hash:1111 1111 1111 1111 0000 0101 0011 0101【这个是上面高16位和低16位异或得到的】&与运算的结果:0000 0000 0000 0000 0000 0000 0000 0101 =>[5]………………………………………………………………………………………………………………………………………………………………………………………………………………………………【重点】假如现在扩容，这个容量变为了32，那么上面计算的索引为5，到扩容后的集合的位置可能是5或者是21(n - 1)&hash计算的是在集合中的插入桶的位置n - 1: 0000 0000 0000 0000 0000 0000 0001 1111【假设的容量为32-1=31】hash:1111 1111 1111 1111 0000 0101 0011 0101【这个是上面高16位和低16位异或得到的】&与运算的结果:0000 0000 0000 0000 0000 0000 0001 0101 =>[21]假如hash位置为0 : 0 =>[5]………………………………………………………………………………………………………………………………………………………………………………………………………………………………总结1、高16 bit 不变，低16 bit 和高16 bit 做了⼀个异或运算(得到的 hashcode 转化为32位二进制，低16 bit和高16 bit做了⼀个异或)。2、(n-1) & hash => 得到下标。 (n-1): n表示数组长度16，n-1就是15。3、【取模运算】取余数本质是不断做除法，把剩余的数减去，运算效率要⽐位运算低。
为什么要使用这样的操作？
如果当n，即数组长度很⼩，假设是16的话，那么n-1二进制即为1111 ，这样的值和
hashCode()直接做按位与操作，实际上只使用了哈希值的后4位。如果当哈希值的高位变化很大，低位变化很小， 这样就很容易造成哈希冲突了，所以这里把高低位都利利用起来，从⽽解决了这个问题。
final V putVal实际的添加键值对的方法
参数解释
hash : key的hash值key : 原始Keyvalue: 要存放的值onlyIfAbsent: 如果为true代表不更改现有的值 evict: 如果为false表示table为创建状态
源码阅读
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;// transient Node<K,V>[] table：表示存储Map集合中元素的数组。// (tab = table) == null表示将table赋值给tab,然后判断tab是否等于null，第⼀次添加的时候肯定是 null。// (n = tab.length) == 0 表示获取tab的长度赋值给n，然后判断这个n是否等于0。// 执行完n = (tab = resize()).length，数组tab每个空间都是null。if ((tab = table) == null || (n = tab.length) == 0)// 获取初始化后的数组的容量。// resize()方法有两个用途。用途1:用来初始化HashMap中存储数据的table数组【resize源码可以看的到】。用途2:给table扩容（即*2）。n = (tab = resize()).length;// i = (n - 1) & hash 表示计算数组的索引赋值给i，即确定元素存放在哪个桶中。// p = tab[i = (n - 1) & hash]表示获取计算出的位置的数据赋值给节点p。// (p = tab[i = (n - 1) & hash]) == null 判断节点位置是否等于null。// 这个存放元素的位置是线程不安全的，可能会出现一个正在存这个位置，另一个线程取，出现异常安全 currenthashmap使用cas解决 if ((p = tab[i = (n - 1) & hash]) == null)// 创建一个新的节点存⼊到桶中，索引位置无元素，则创建Node对象，存入数组该位置中tab[i] = newNode(hash, key, value, null);else {// 如果索引位置已有元素，说明hash冲突，存入单链表或者红黑树中// 若已经存在一个节点，它的key与新值的key相等，则用变量e记录这个节点// e的作用就是干这个的，下面很长一段代码都是用来判断是否存在这样一个节点HashMap.Node<K,V> e; K k;// 位置有元素的前提下，判断该位置的key是不是和旧的key值相同// 若新值将要插入的位置已经存在的节点，它的key值与新值的key相等，则用变量e记录下它// p.hash == hash :p.hash表示原来存在数据的hash值，hash表示后添加数据的hash值，比较两个hash值是否相等// (k = p.key) == key :p.key获取原来数据的key赋值给k，key表示后添加数据的key，比较两个key的地址是否相同// key != null && key.equals(k):能够执行到这里说明两个key的地址值不相等，判断后添加的key是否等于null，如果不等于再调用equals⽅法判断两个key的内容是否相等。if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))// e现在为旧值；两个元素哈希值相等，并且key的值也相等，将旧的元素整体对象赋值给e，用e来记录e = p;// 该位置有元素的前提下，hash值不相等或者key不相等;判断p是否为红黑树结点，若已经存在的节点是一个Tree节点，则使用树的方法将节点加入// 用e接收返回值，此处返回值e不为空，表示这棵树上存在与新值的key相同的节点 else if (p instanceof TreeNode)// 用e接收返回值，此处返回值e不为空，表示这棵树上存在与新值的key相同的节点 e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {// 该位置有元素的前提下，hash值不相等或者key不相等;则表示这个位置不是一棵树，而是一个链表// 遍历这个链表，binCount代表当前链表的长度，遍历到链表最后节点然后插⼊，采用循环遍历的方式，判断链表中是否有重复的keyfor (int binCount = 0; ; ++binCount) {// 若已经到达这个链表的最后一个节点，则用新值创建一个新的节点，并将其插入最后一个节点的末端// 判断当前位置的下一个元素是否为空// e = p.next 获取p的下一个元素赋值给e// (e = p.next) == null 判断p.next是否等于null，等于null，说明p没有下一个元素，那么此时到达了了链表的尾部，还没有找到重复的key,则说明HashMap没有包含该键，将该键值对插⼊链表中if ((e = p.next) == null) {// 用新值创建一个新的节点，并将其追加到单链表末尾// 注意第四个参数next是null，因为当前元素插入到链表末尾了，那么下一个节点肯定是null// 这种添加方式也满足链表数据结构的特点，每次向后添加新的元素p.next = newNode(hash, key, value, null);// 若插入这个节点后，这条链表的的节点数目已经到达了树化的阈值// 则将这条链表转换为红黑树// 超过树化阈值则进行树化操作 TREEIFY_THRESHOLD = 8，为啥-1 ，原因是binCount从0开始// int binCount = 0 :表示for循环的初始化值，从0开始计数。记录着遍历节点的个数。值是0表示第一个节点，1表示第⼆个节点。。。。7表示第八个节点，if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st// 树形化，转换为红黑树【接下来单独开一篇文章介绍】treeifyBin(tab, hash);// 跳出循环break;}// 若在遍历这条链表的过程中，发现了一个节点，它的key值与新值的key相等，则不插入新节点// 且此时由于上面的操作，e已经指向了这个key的节点，不需要继续遍历了，跳出循环if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))// 要添加的元素和链表中的存在的元素的key相等了，则跳出for循环。不用再继续比较了，直接执行下面的if语句去替换 if(e != null)break;// 上面判断的节点的下个节点是否为空，显然能执行到这下个节点不为空，并且key也不相同，// 换句话说下个节点下有元素，key不相同，将p节点赋值为当前节点，并且判断它的下个节点。// 新添加的元素和当前节点不相等，继续查找下一个节点。⽤于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表。p = e;}}// 判断e是否为null，若不为空，表示在原来的节点中，存在一个key值与新值的key重复的节点// 在桶中找到key值、hash值与插⼊元素相等的结点// 也就是说通过上⾯的操作找到了重复的键，所以这里就是把该键的值变为新的值，并返回旧值 这里完成了put方法的修改功能if (e != null) {// existing mapping for key// 记录下这个节点原来的value值V oldValue = e.value;// 若onlyIfAbsent的值为false，或者原来的value是null，则用新值替换原来的值if (!onlyIfAbsent || oldValue == null)e.value = value;// 这是一个回调函数，但是在HashMap中是一个空函数// 看源码貌似是留给LinkedHashMap去扩充的// 感觉这个应该属于模板方法设计模式afterNodeAccess(e);// 返回旧value，如果在这里被返回，则不会执行剩下的代码// 也就是说，若执行到剩下的代码，表示并不是执行修改原有值的操作，而是插入了新节点return oldValue;}}// 能运行到这里，表示这次进行的是插入操作，而不是修改// modCount用来记录Map（仅指插入+删除）被修改的次数// 此处modCount+1，因为HashMap被修改了（新插入了一个节点）++modCount;// Map中元素的数量+1，并判断元素数量是否到达允许的最大值，若到达，则对Map进行扩容if (++size > threshold)// 扩容【接下来单独开一篇文章介绍】resize();// 与上面的afterNodeAccess类似，同为留给LinkedHashMap编写的回调函数 afterNodeInsertion(evict);return null;}
总结
++size > threshold根据哈希表中元素个数确定是扩容还是树形化如果是树形化，遍历桶中的元素，创建相同个数的树形节点，复制内容，建立起联系然后让桶中的第⼀个元素指向新创建的树根节点，替换桶的链表内容为树形化内容谢谢点赞
创作不易， 非常欢迎大家的点赞、评论和关注(^_−)☆你的点赞、评论以及关注是对我最大的支持和鼓励，而你的支持和鼓励我继续创作高质量博客的动力 ！！！
