侧边栏壁纸
博主头像
Ysfun博主等级

一名热爱技术、喜欢折腾的小小程序猿

  • 累计撰写 42 篇文章
  • 累计创建 14 个标签
  • 累计收到 21 条评论

目 录CONTENT

文章目录

源码剖析:HashMap中插入节点put(k, v)和扩容resize()

Ysfun
2022-06-17 / 0 评论 / 2 点赞 / 97 阅读 / 2,765 字

HashMap在不同JDK版本的实现方式和源码有所区别,本文针对jdk1.8展开分析,从源码出发深入探讨HashMap插入元素及其中涉及的扩容的过程。

HashMap数据结构

HashMap本质由数组+链表/红黑树,其源码中定义了一个核心属性table(一个Node数组),Node可以理解为存储哈希表中键值对的容器。

HashMap会根据key哈希值找到当前键值对存放在table中的下标index,当多个key位于同一个下标时(称之为哈希冲突),会采用链表的方式,将当前Node插入到链表尾端;当链表的长度超过TREEIFY_THRESHOLD时,会将链表转换为二叉查找树进行存储(HashMap采用的是红黑树);当发现key相同时只替换value值即可。

上面提到发现”key相同“,进行key比较的时候会按照如下顺序进行比对:

  1. 先判断两个key的哈希值是否相同,如果不同则两个key不同,否则继续比较
  2. 判断是否指向同一个引用,即是否==,如果指向同一个引用则两个key相同,否则继续比较
  3. 判断equals是否相等,如果相等则两个key相同,否则不相同

从这里我们解释为什么说“重写equals方法就一定要重写hashCode方法”?

当我们需要使用到散列结构(HashMap, HashSet等)时,如果只重写equals方法而没有重写hashCode方法,在比较key是否相同时会先进行hashCode比较,没有重写hashCode方法会导致两个equals相等的对象的hashCode不同,因此在put操作时会当做两个不同的key来处理。

HashMap插入节点和扩容

put方法源码注释:

我们可以发现put方法实际是调用了putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)方法,我们先来看计算哈希值的过程:

从源码我们可以发现,计算哈希值的时候,当keynull时指定了哈希值为0,说明HashMap是允许keynull的,并且只能有一个keynull。这里和其他的哈希表不同(如HashTable,ConcurrentHashMap),其他哈希结构都是不允许keynull的。

putVal()插入节点

插入节点的步骤:

  1. 根据哈希值找到当前key在table数组(哈希桶)中的位置
  2. table数组当前位置为空,则在此处创建新Node并放在table的当前位置即可,break
  3. 当前位置不为空,且发现当前位置的节点是一颗红黑树,执行红黑树插入节点的操作,break
  4. 当前位置不为空,也不是红黑树,则当前位置只有可能是链表,执行链表的插入操作
    1. 遍历链表,查找是否有相同key,如果发现了相同key,则进行值替换,break
    2. 遍历到链表尾部,仍未发现相同key,此处创建行Node,并将其插入到链表尾部;插入节点后若发现当前链表长度超过TREEIFY_THRESHOLD时,将链表变成红黑树,break
  5. 插入节点后,判断当前size是否超过threshold,如超过进行resize()
  6. Return

源码分析:(详细分析过程见注释)

/**
     * 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
     */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
  Node<K,V>[] tab; Node<K,V> p; int n, i;
  if ((tab = table) == null || (n = tab.length) == 0)
    // table为空时,初始化table
    n = (tab = resize()).length;
  if ((p = tab[i = (n - 1) & hash]) == null)
    // 哈希桶当前位置为空,则直接把新的Node放到table数组的当前位置即可
    tab[i] = newNode(hash, key, value, null);
  else {
    // 发生哈希冲突
    Node<K,V> e; K k;
    // p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))就是上面提到的「比较key」的源码
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      // 发现key相同,把当前Node赋给e,后面进行value替换操作
      e = p;
    else if (p instanceof TreeNode)
      // 发现哈希桶当前位置已经是一颗树,进行红黑树插入节点操作,此处不进行详细阐述
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
      // table当前位置为链表,遍历链表,寻找是否有相同的key
      for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
          // 遍历到链表尾部,仍未发现相同的key,创建新Node,并插入到链表尾部
          p.next = newNode(hash, key, value, null);
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            // 发现当前链表的长度达到了TREEIFY_THRESHOLD,链表变红黑树,提升查询效率
            treeifyBin(tab, hash);
          break;
        }
        // 此处同样是「比较key」的过程
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        // 发现有相同的key,把当前Node赋给e,后面进行value替换操作
        p = e;
      }
    }
    if (e != null) { // existing mapping for key
      // 发现key相同,进行value替换操作
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      afterNodeAccess(e);
      return oldValue;
    }
  }
  ++modCount;
  if (++size > threshold)
    // 当前HashMap的节点数超过了门槛值,进行扩容
    resize();  // 扩容操作
  afterNodeInsertion(evict);
  return null;
}

resize()扩容

源码注释:

从上面注释我们可以知道,当初始化或者哈希桶大小翻倍时会执行resize()方法。

resize()方法分为两个部分:

  1. 重新计算thresholdcapacity
  2. 重新放置所有Node

第一个过程较为简单,基本过程就是table大小翻倍,然后重新计算threshold = newCap * loadFactor,源码部分涉及到很多越界处理,看着有些复杂。

第二个过程遍历旧table,将节点放入到新table对应的位置,主要分为以下几步:

  1. table当前位置为空,直接跳过

  2. table当前位置只有一个节点,将该节点放到新tablee.hash & (newCap - 1)位置上即可

  3. table当前位置是一颗二叉树,执行红黑树的重新放置节点操作

  4. table当前位置是一个长度大于1的链表

    1. 在链表中存在位置不变和位置往后移动oldCap的节点,使用loHead,loTail来记录位置不变节点的头尾节点,使用hiHead, hiTail记录位置需要往后移动oldCap的头尾节点

    怎么判断哪些节点位置不变,哪些需要移动?为什么是向后移动oldCap个位置?
    e.hash & (newCap - 1) 代表新table的位置,且newCap = oldCap << 1,并且newCap和oldCap都是2的倍数
    举例说明:
    我们假定oldCap = 8(即0b1000),则newCap = 16(即0b10000)
    e.hash & 0b111 表示在旧table中的位置,& 操作是对e.hash进行截断,即e.hash的后三位即代表旧位置
    e.hash & 0b1111 表示在新table中的位置,同理,e.hash的后四位代表新位置
    因此我们只要判断e.hash在第四位是否为0即可,如果为0,则表示新位置和旧位置一致;如果不为0,则新位置比旧位置大0b1000
    结论:
    e.hash & oldCap == 0 : 新位置和旧位置一致
    e.hash & oldCap != 0 : 新位置比旧位置大oldCap

    1. 位置不动的节点通过newTab[j] = loHead来实现;位置往后移动通过newTab[j + oldCap] = hiHead来实现

源码分析:(详细分析过程见注释)

final Node<K,V>[] resize() {
  Node<K,V>[] oldTab = table;
  // ==============第一部分 开始==============
  int oldCap = (oldTab == null) ? 0 : oldTab.length;
  int oldThr = threshold;
  int newCap, newThr = 0;
  if (oldCap > 0) {
    if (oldCap >= MAXIMUM_CAPACITY) {
      threshold = Integer.MAX_VALUE;
      return oldTab;
    }
    // newCap = oldCap << 1,capacity翻倍,即table大小翻倍
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
      // threshold翻倍
      newThr = oldThr << 1; // double threshold
  }
  else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr;
  else {               // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  if (newThr == 0) {
    // 重新计算threshold = newCap * loadFactor
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
              (int)ft : Integer.MAX_VALUE);
  }
  threshold = newThr;
  // ==============第一部分 结束==============
  
  // ==============第二部分 开始==============
  @SuppressWarnings({"rawtypes","unchecked"})
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  table = newTab;
  if (oldTab != null) {
    // 遍历原来的table
    for (int j = 0; j < oldCap; ++j) {
      Node<K,V> e;
      // 原来table当前位置为null的直接跳过
      if ((e = oldTab[j]) != null) {
        oldTab[j] = null;
        if (e.next == null)
          // 当前位置上的链表只有一个节点,重新计算在新table中的位置,并放置到新table对应位置即可
          newTab[e.hash & (newCap - 1)] = e;
        else if (e instanceof TreeNode)
          // 当前位置上是一颗红黑树,进行树的重新放置操作,此处不进行详细阐述
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        else { // preserve order
          // 当前位置上是一颗节点数大于1的链表
          // 不需要改变位置的头结点和尾节点
          Node<K,V> loHead = null, loTail = null;
          // 需要将位置往后移动oldCap个位置的头节点和尾节点
          Node<K,V> hiHead = null, hiTail = null;
          Node<K,V> next;
          do {
            next = e.next;
            /* 
            (e.hash & oldCap) == 0 是判断当前节点哈希值在新table中的位置是否需要改变
            e.hash & (newCap - 1) 代表新table的位置,且newCap = oldCap << 1,并且newCap和oldCap都是2的倍数
            举例说明:
            我们假定oldCap = 8(即0b1000),则newCap = 16(即0b10000)
            e.hash &  0b111 表示在旧table中的位置,& 操作是对e.hash进行截断,即e.hash的后三位即代表旧位置
            e.hash & 0b1111 表示在新table中的位置,同理,e.hash的后四位代表新位置
            因此我们只要判断e.hash在第四位是否为0即可,如果为0,则表示新位置和旧位置一致;如果不为0,则新位置比旧位置大0b1000
            结论:
            e.hash & oldCap == 0 : 新位置和旧位置一致
            e.hash & oldCap != 0 : 新位置比旧位置大oldCap
            */
            if ((e.hash & oldCap) == 0) {
              if (loTail == null)
                loHead = e;
              else
                loTail.next = e;
              loTail = e;
            }
            else {
              if (hiTail == null)
                hiHead = e;
              else
                hiTail.next = e;
              hiTail = e;
            }
          } while ((e = next) != null);
          if (loTail != null) {
            loTail.next = null;
            // 将新旧位置不变的节点仍放到j位置上
            newTab[j] = loHead;
          }
          if (hiTail != null) {
            hiTail.next = null;
            // 将需要往后移的节点放到j+oldCap位置上
            newTab[j + oldCap] = hiHead;
          }
        }
      }
    }
  }
  return newTab;
}
2

评论区