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) 添加方法
static final int hash(Object key) 求哈希值方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,<br/> boolean evict) 实际的添加键值对的方法


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
    根据哈希表中元素个数确定是扩容还是树形化
  • 如果是树形化,遍历桶中的元素,创建相同个数的树形节点,复制内容,建立起联系

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

谢谢点赞

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

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

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

- END -

原文 

https://juejin.im/post/5f06bacb5188252e9b46f3df

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » MoxiMoxi !!!你看过HashMap中的put方法的源码吗?

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址