在JDK 1.7 中， HashMap是通过数组 + 链表/红黑树的结构进行实现

在HashMap中定义了几个链表转化为红黑树的阈值，当达到那些阈值时，则会将链表转化为红黑树，否则，和1.7中一样 ,还是数组 + 链表的结构
image.png
在1.8中，HashMap的主要变化为put方法，resize() 扩容方法，以及转化为红黑树的逻辑，其他逻辑与1.7中相同，详见

HashMap1.7 源码分析

PUT()

首先，第一步，计算key的hash值，调用putVal方法

  1. public V put(K key, V value) {
  2.     return putVal(hash(key), key, value, false, true);
  3. }

putVal方法的逻辑

  • 判断当前的table属性是否为null，如果为null，进行初始化table属性，这里直接调用resize()扩容方法进行初始化，在resize()方法中再进行分析

    1. if ((tab = table) == null || (n = tab.length) == 0)
    2.   n = (tab = resize()).length;

  • 计算当前hash值所对应的下标，准备进行添加操作 (和1.7中相同，还是通过 (n-1)& hash 来计算下标)

    • 如果当前的下标对应的数组元素中没有值，即没有hash冲突，直接创建一个新的节点，赋值给数组对应的下标

      1. if ((p = tab[i = (n - 1) & hash]) == null)
      2. tab[i] = newNode(hash, key, value, null);

    • 否则，当前的下标对应的数组元素中有值，即发生了hash冲突(或者为同一个key，进行了覆盖操作)

      • 判断当前下标对应的元素(头节点)的hash值和key值是否相等，如果相等，说明是覆盖(头节点)的操作

        1. if (p.hash == hash &&
        2. ((k = p.key) == key || (key != null && key.equals(k))))
        3. e = p;

      • 否则，不是覆盖操作，即真正的发生了hash冲突

      • 发生了hash冲突，判断当前的Node类型是否为TreeNode，如果是TreeNode，说明，已经将链表转化为了红黑树，执行红黑树的putTreeVal()操作

        1. else if (p instanceof TreeNode)
        2. e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

      • 否则，不是TreeNode，即还没转化成红黑树，还是个链表，此时从头节点，开始遍历整个链表，当遍历到链表的末尾之后，还没有hash值相等且key相等的(即没有覆盖操作)，那么，就表明需要插入一个新的节点。通过(p.next = newNode(hash, key, value, null);)进行插入，因为已经循环到链表的末尾，所以插入到尾节点中(1.7中是插入到头节点中)。其中，利用binCount进行计数，链表的长度大于 TREEIFY_THRESHOLD (8) 时，尝试将链表转化为红黑树，但不一定会直接转化为红黑树，详见附录 一。

        1. if ((e = p.next) == null) {
        2. p.next = newNode(hash, key, value, null);
        3. if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
        4. treeifyBin(tab, hash);
        5. break;
        6. }

      • 循环过程中，如果链表中的某个节点的hash值和key与传入的相等，意味着覆盖这个冲突的节点，跳出循环

        1. if (e.hash == hash &&
        2. ((k = e.key) == key || (key != null && key.equals(k))))
        3. break;

    • 最后，不管是头节点冲突，树节点冲突，还是链表中间的某个节点冲突，最终通过这个逻辑，将节点的值替换成新的

      1. if (e != null) { // existing mapping for key
      2. V oldValue = e.value;
      3. if (!onlyIfAbsent || oldValue == null)
      4.    e.value = value;
      5. afterNodeAccess(e);
      6. return oldValue;
      7. }

    • 插入完成之后，判断当前的容量，是否达到扩容的阈值，如果达到了，执行resize()进行扩容

      1. if (++size > threshold)
      2. resize();

resize()

第一次进行put操作时，在1.8中是通过resize进行初始化的，所以如下几个局部变量中，默认值都是0

  1. int oldCap = (oldTab == null) ? 0 : oldTab.length;
  2. int oldThr = threshold;
  3. int newCap, newThr = 0;

所以在第一次resize的时候，newCap 为默认的容量(16)，newThr 阈值为 (16 * 0.75 = 12)

  1. if (oldCap > 0) {
  2.     if (oldCap >= MAXIMUM_CAPACITY) {
  3.         threshold = Integer.MAX_VALUE;
  4.         return oldTab;
  5.     }
  6.     else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  7.              oldCap >= DEFAULT_INITIAL_CAPACITY)
  8.         newThr = oldThr << 1; // double threshold
  9. }
  10. else if (oldThr > 0) // initial capacity was placed in threshold
  11.     newCap = oldThr;
  12. else {               // zero initial threshold signifies using defaults
  13.     newCap = DEFAULT_INITIAL_CAPACITY;
  14.     newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  15. }

判断oldTab是否为null，如果不为null，则说明之前HashMap中存在元素，是真正意义上的扩容，而不是初始化
所以，在第一次put的时候，以下逻辑不会执行，直接返回一个空数组，执行上述的put()，操作，往里添加元素
在后续不断的往里put的时候，终将有满足 ++size > threshold 等于的这一时候，此时，就是真正意义上的扩容
假设，这里使用默认的HashMap的长度(16)以及扩容因子(0.75)，那么即当 size 达到12的时候，将会触发resize()机制
这一次进行resize(), 这些局部变量的值就为 如下的几个value

  1. int oldCap = (oldTab == null) ? 0 : oldTab.length; // 16
  2. int oldThr = threshold; // 12
  3. int newCap, newThr = 0; //0

此时，将会进入到下面这段逻辑中，一般肯定达不到 MAXIMUM_CAPACITY(1<<30)，就将新的容量直接左移一位，放大两倍(即目前的容量为32，阈值为24)

  1. if (oldCap > 0) {
  2.     if (oldCap >= MAXIMUM_CAPACITY) {
  3.         threshold = Integer.MAX_VALUE;
  4.         return oldTab;
  5.     }
  6.     else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  7.              oldCap >= DEFAULT_INITIAL_CAPACITY)
  8.         newThr = oldThr << 1; // double threshold
  9. }

此时，因为oldTab中原先有值，则会遍历旧数组，将元素转移到新数组中，其逻辑为

  • 开始遍历oldTab

    • 如果当前遍历的数组元素只有一个元素(即 e.next ==null) ，则直接转移到新数组中

      1. if (e.next == null)
      2. newTab[e.hash & (newCap - 1)] = e;

    • 否则，则说明，这个下标中有多个节点

      • 如果是TreeNode(已经转化为了红黑树)，调用split 进行转移

        1. else if (e instanceof TreeNode)
        2. ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

      • 否则， 就是一个链表，将其转移至新数组中（将Hash值与原数组的长度进行&运算，来判断当前的元素是放在原始的位置，还是新的位置）

      • 如果hash值与原数组的长度与运算之后 等于 0，直接赋值到新数组的原下标中
      • 如果hash值与原数组的长度与运算之后 不等于0，将其放入到原下标 + 原数组长度对应的数组下标中
      • 经过上面的这样转移元素，既不会产生像1.7中HashMap扩容的死锁问题(1.8中尾插法，以及直接将头进行转移来进行解决)，同时通过这样，将数组中的元素在此分散到了所有的下标中，从而减少hash冲突的发生