原创

JDK1.8 HashMap源码解析(二) 数据赋值 put

前面讲到了hashMap的基本数据结构和HashMap 构造初始化过程。
接下来讲讲数据赋值的原理。

核心源码剖析

put 过程: 首先执行put方法

/**
   * Associates the specified value with the specified key in this map.
   * If the map previously contained a mapping for the key, the old
   * value is replaced.
   *
   * @param key   key with which the specified value is to be associated
   * @param value value to be associated with the specified key
   * @return the previous value associated with <tt>key</tt>, or <tt>null</tt> if there was no
   * mapping for <tt>key</tt>. (A <tt>null</tt> return can also indicate that the map previously
   * associated <tt>null</tt> with <tt>key</tt>.)
   */
  /**
   * 将指定参数key和指定参数value插入map中,如果key已经存在,那就替换key对应的value
   * put(K key, V value)可以分为三个步骤:
   * 1.通过hash(Object key)方法计算key的哈希值。
   * 2.通过putVal(hash(key), key, value, false, true)方法实现功能。
   * 3.返回putVal方法返回的结果。
   *
   * @param key   指定key
   * @param value 指定value
   * @return 如果value被替换,则返回旧的value,否则返回null。当然,可能key对应的value就是null
   */
  public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
  }

put方法中对key进行了hash处理,计算其对应的hash值:

  /**
   * HashMap中键值对的存储形式为链表节点,hashCode相同的节点(位于同一个桶)用链表组织
   * hash方法分为三步:
   * 1.取key的hashCode
   * 2.key的hashCode高16位异或低16位
   * 3.将第一步和第二步得到的结果进行取模运算。
   */
  static final int hash(Object key) {
    int h;
    // 让高位码产生作用: https://www.zhihu.com/question/20733617
    //计算key的hashCode, h = Objects.hashCode(key)
    //h >>> 16表示对h无符号右移16位,高位补0,然后h与h >>> 16按位异或
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

此处如果传入的int类型的值:

向一个Object类型赋值一个int的值时,会将int值自动封箱为Integer。

Integer类型的hashcode都是他自身的值,即h=key;

h >>> 16为无符号右移16位,低位挤走,高位补0;

^ 为按位异或,即转成二进制后,相异为1,相同为0.

由此可发现,当传入的值小于 2的16次方-1 时,调用这个方法返回的值,都是自身的值。

put 过程: 然后再执行putVal方法:

/**
   * Implements Map.put and related methods
   *
   * @param hash         hash for key
   * @param key          the key
   * @param value        the value to put
   * @param onlyIfAbsent if true, don't change existing value
   * @param evict        if false, the table is in creation mode.
   * @return previous value, or null if none
   */
  /**
   * Map.put和其他相关方法的实现需要的方法
   * putVal方法可以分为下面的几个步骤:
   * 1.如果哈希表为空,调用resize()创建一个哈希表。
   * 2.如果指定参数hash在表中没有对应的桶,即为没有碰撞,直接将键值对插入到哈希表中即可。
   * 3.如果有碰撞,遍历桶,找到key映射的节点
   *    3.1桶中的第一个节点就匹配了,将桶中的第一个节点记录起来。
   *    3.2如果桶中的第一个节点没有匹配,且桶中结构为红黑树,则调用红黑树对应的方法插入键值对。
   *    3.3如果不是红黑树,那么就肯定是链表。遍历链表,如果找到了key映射的节点,就记录这个节点,退出循环。
   *    如果没有找到,在链表尾部插入节点。
   *    插入后,如果链的长度大于TREEIFY_THRESHOLD这个临界值,则使用treeifyBin方法把链表转为红黑树。
   * 4.如果找到了key映射的节点,且节点不为null
   *    4.1记录节点的vlaue。
   *    4.2如果参数onlyIfAbsent为false,或者oldValue为null,替换value,否则不替换。
   *    4.3返回记录下来的节点的value。
   * 5.如果没有找到key映射的节点(2、3步中讲了,这种情况会插入到hashMap中),插入节点后size会加1,
   * 这时要检查size是否大于临界值threshold,如果大于会使用resize方法进行扩容。
   *
   * @param hash         指定参数key的哈希值
   * @param key          指定参数key
   * @param value        指定参数value
   * @param onlyIfAbsent 如果为true,即使指定参数key在map中已经存在,也不会替换value
   * @param evict        如果为false,数组table在创建模式中
   * @return 如果value被替换,则返回旧的value,否则返回null。当然,可能key对应的value就是null。
   */
  final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                 boolean evict) {
    Node<K, V>[] tab;
    Node<K, V> p;
    int n, i;

    //如果哈希表为空,调用resize()创建一个哈希表,并用变量n记录哈希表长度
    if ((tab = table) == null || (n = tab.length) == 0) {
        /* 这里调用resize,其实就是第一次put时,对数组进行初始化。*/
        n = (tab = resize()).length;
    }

   /**
    * 如果指定参数hash在表中没有对应的桶,即为没有碰撞.
    * (n - 1) & hash 计算key将被放置的槽位.
    * (n - 1) & hash 本质上是hash % n,位运算更快.
    */
    //如果选定的数组坐标处没有元素,直接放入
    if ((p = tab[i = (n - 1) & hash]) == null) {
        //位置为空,将i位置上赋值一个node对象
        tab[i] = newNode(hash, key, value, null);
    } else { // 桶中已经存在元素, 则进入else
      Node<K, V> e;
      K k;

      //如果链表第一个元素或树的根的key与要插入的数元素key 和 hash值完全相同,覆盖旧值
      if (p.hash == hash &&
          ((k = p.key) == key || (key != null && key.equals(k)))) {
        // 将第一个元素赋值给e,用e来记录
        e = p;

      // 当前桶中无该键值对, 进入else. 此时如果桶是红黑树结构,按照红黑树结构插入,调用putTreeVal
      } else if (p instanceof TreeNode) {
        e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);

      //p与新节点既不完全相同,p也不是treenode的实例, 即桶是链表结构,按照链表结构插入到尾部
      //此时只是hash冲突,并且是链表
      } else {
        //遍历链表,找到合适的处理方式 1插入新节点 2覆盖旧值
        for (int binCount = 0; ; ++binCount) { //一个死循环
              //在链表尾部插入新节点
              if ((e = p.next) == null) { //e=p.next,如果p的next指向为null
                  // 先将新节点插入到 p.next
                  p.next = newNode(hash, key, value, null);

                   //如果冲突的节点数已经达到8个,看是否需要改变冲突节点的存储结构,
                   // treeifyBin首先判断当前hashMap的长度,如果不足64,只进行resize,扩容table,
                   // 如果达到64,那么将冲突的存储结构为红黑树
                  if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                  {
                    //将链表转化为二叉树
                    treeifyBin(tab, hash);
                  }
                  break;
              }

              // 如果链表中有一个节点key和新插入的key重复,则跳出循环。
              // 链表节点的<key, value>与put操作<key, value>相同时,不做重复操作,跳出循环
              // 直白一点就是说,如果遍历过程中链表中的元素与新添加的元素完全相同,则跳出循环
              if (e.hash == hash &&
                  ((k = e.key) == key || (key != null && key.equals(k)))) {
                break;
              }

              //将p中的next赋值给p,即将链表中的下一个node赋值给p, 继续循环遍历链表中的元素
              p = e;
        }
      }

      //这个判断中代码作用为:如果添加的元素产生了hash冲突,那么调用put方法时,会将他在链表中他的上一个元素的值返回
      if (e != null) { // existing mapping for key
          // 记录e的value
          V oldValue = e.value;

          //判断条件成立的话,将oldvalue替换
          if (!onlyIfAbsent || oldValue == null) {
              //为newvalue,返回oldvalue;不成立则不替换,然后返回oldvalue
              e.value = value;
          }

          // 访问后回调
          afterNodeAccess(e);

          // 返回旧值
          return oldValue;
      }
    }

    //记录修改次数
    ++modCount;

    // 如果元素数量大于临界值,则进行 rehash 扩容
    // 扩张也是同步判断和执行的,所以恰好触发时会比较慢
    if (++size > threshold) {
      resize();
    }

    // 插入后回调
    afterNodeInsertion(evict);
    return null;
  }

put 过程: putVal执行过程 -- 新元素的插入

  • 1、计算元素的位置。hash&(n-1)就是新元素的位置,n代表的是table长度。
  • 2、查看对应位置是否有元素
  • 3、如果没有,直接插入;如果有,进行hash碰撞的处理
  • 4、hash碰撞三种情况
    • 一是碰撞的元素与要插入的元素hash值和key都相等,直接进行value的更新;
    • 二是结点类型是树结点直接,进行树结点的增加或更新;
    • 三是普通结点,只是hash碰撞,key不相同,于是增长链表。
  • 5、插入之后,会进行hashmap大小的判断,如果元素数量超过了threshold,则会进行resize()扩容。

每当插入一个元素的时候,就会对这个元素的键的Hash值按此时的数组长度取模,然后装入对应的位置。比如一个hash值为14的元素插入一个table长度为16(源码中为DEFAULT_INITIAL_CAPACITY默认值)的hashMap中,14对16取模是14(源码中为(n - 1) & hash, 即 (16 - 1) & 14=14),于是就装入14这个位置。不同的元素取模之后发生碰撞,比如30对16取模也等于14,这样也需要放入14的位置,于是就会在这个桶中形成链表

hashmap-set.png

转折点

  • 随着数据的不断增加,数组(碰撞导致)和链表(数据新增)长度一直增加,当链表长度超过8,且数组长度不超过64时,链表会被扩容
  • 树化的条件是:桶中链表的长度达到了8,并且数组的长度大于等于64,链表就会被树化成为红黑树结构
    hashmap 红黑树.jpg
/**
   * 将链表转化为红黑树
   */
  final void treeifyBin(Node<K, V>[] tab, int hash) {
    int n, index;
    Node<K, V> e;
    //如果桶数组table为空,或者桶数组table的长度小于MIN_TREEIFY_CAPACITY,不符合转化为红黑树的条件
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
      //扩容
      resize();
    } else
      // 如果符合转化为红黑树的条件,而且hash对应的桶不为null, 则重新计算 hash段位,及table的索引位,第一个节点
      if ((e = tab[index = (n - 1) & hash]) != null) {
           /************ 双向链表 start***************/
          // 红黑树的hd头节点, tl尾节点
          TreeNode<K, V> hd = null, tl = null;
          //遍历链表
          do {
            //替换链表node为树node,建立双向链表
            TreeNode<K, V> p = replacementTreeNode(e, null);
            // 确定树头节点
            if (tl == null) {
              hd = p;
            } else {
              p.prev = tl;
              tl.next = p;
            }
            tl = p;
          } while ((e = e.next) != null);
          /************ 双向链表 end***************/


          // 前面仅仅转换为双向链表,treeify才是转换红黑树的处理方法入口 
          // 第一个节点赋值为头节点,也就是根节点
          if ((tab[index] = hd) != null) {
            // 将二叉树转换为红黑树
            hd.treeify(tab);
          }
    }
  }

HashMap本来是以空间换时间,所以填充比(static final float DEFAULT_LOAD_FACTOR = 0.75f;)没必要太大。但是填充比太小又会导致空间浪费。如果关注内存,填充比可以稍大,如果主要关注查找性能,填充比可以稍小。

流程图总结:
hashmap-put流程图.png

按不同阶段划分的整体数据流程图如下:
file

相关话题我们在之后的时间里逐步学习和分析。这里跳过。

resize的源码详解?扩容机制?链接

单元素如何散列到新的数组中?链接

链表中的元素如何散列到新的数组中?链接

红黑树的具体实现方式?链接

最后,附源代码如下:JDK1.8 HashMap源码解析

正文到此结束
广告是为了更好的提供数据服务
本文目录