MoxiMoxi ！！！你看过HashMap中的put方法的源码吗？

点赞在看，养成习惯。

点赞收藏，人生辉煌。

点击关注【微信搜索公众号：编程背锅侠】，防止迷路。

HashMap系列文章

第一篇 HashMap源码中的成员变量你还不懂? 来来来！！！整理好的成员变量源码解析

第二篇 撸啊撸，再次撸HashMap源码，踩坑源码中构造方法！！！每次都有收获

第三篇 MoxiMoxi ！！！你看过HashMap中的put方法的源码吗？

面试官：你能讲讲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⽅法。

案例演示

@Test
public 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对应的hashCode
 int 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 = 1
 5   0101
& 11  1011
………………………………
结果： 0001【运算结果：1】
复制代码

^异或运算
运算规则:相同的二进制数位上，数字相同，结果为0，不同为1。
案例：5 ^ 11 = 14
 5   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 1010
       h >>>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 : 原始Key
value: 要存放的值
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代表当前链表的长度，遍历到链表最后节点然后插⼊，采用循环遍历的方式，判断链表中是否有重复的key
   for (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 根据哈希表中元素个数确定是扩容还是树形化

• 如果是树形化，遍历桶中的元素，创建相同个数的树形节点，复制内容，建立起联系

• 然后让桶中的第⼀个元素指向新创建的树根节点，替换桶的链表内容为树形化内容

谢谢点赞

• 创作不易， 非常欢迎大家的点赞、评论和关注(^_−)☆

• 你的点赞、评论以及关注是对我最大的支持和鼓励，而你的支持和鼓励

• 我继续创作高质量博客的动力 ！！！