「Java 集合 碎片知识」HashMap

HashMap
在jdk8中，HashMap底层采用 数组+链表+红黑树 实现，是线程不安全的，可以使用null作为key或value。
（无参构造）刚初始化HashMap时，数组长度还是 0，第一次put时会首次扩容，默认是 16。当一条链表节点数达到 8 时，且这时数组长度达到 64 时，这条链表就会转化为红黑树，否则会继续扩容，每次扩容为原来 2 倍。如果键值对超过扩容阈值threshold，会再次扩容。当一个槽位的节点树小于等于 6 时，又会变回链表。

一些重要的参数

// 默认初始化容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 支持树结构的最小容量
static final int MIN_TREEIFY_CAPACITY = 64;
// 转为树的零界点 大于等于
static final int TREEIFY_THRESHOLD = 8;
// 转为链表的零界点 小于等于
static final int UNTREEIFY_THRESHOLD = 6;

部分源码

数据结构部分

// 数组+链表+红黑树 中的 数组就是这个
transient Node<K,V>[] table;

// 看下Node的结构
// Node是一个内部类，实现了Map.Entry<K,V>，Map是键值对，键值对就被封装成看Entry
static class Node<K,V> implements Map.Entry<K,V> {
  // ...一些源码没有贴
  // 这边可以看出，这是单链表的结构，数组+链表+红黑树 中的链表就在这了
  Node<K,V> next;
}

// 红黑树在此， 这里的继承关系有好几层，其中有继承到了上面的Node，
// 变成TreeNode时，依然保持了链表的东西,所以当红黑树变回链表的时候会非常方便
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
  TreeNode<K,V> parent;  // red-black tree links
  TreeNode<K,V> left;
  TreeNode<K,V> right;
  TreeNode<K,V> prev; 
}

put过程

// 调用hash方法取得hash值，根据hash值来确定保存位置
public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
}

// 这个变量下面一个方法会用到
// 链表节点个数达到这个阈值，则树化
// 是等于8而不是超过8，下面put过程源码会提到这个
static final int TREEIFY_THRESHOLD = 8;

// 逻辑很复杂的，看关键部分就行
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方法初次扩容
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  // 根据hash值计算位置得到位置，若为空则新建节点
  if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  // hash碰撞
  else {
    Node<K,V> e; K k;
    // key相同，则覆盖值。这里是用一个节点 e 指向将要覆盖的节点，之后做同一处理
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      e = p;
    // 如果这个节点是树节点，就加到树后面
    else if (p instanceof TreeNode)
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    // 既不相同，也不是树节点，那就是不同的链表节点
    else {
      for (int binCount = 0; ; ++binCount) {
        // 遍历链表，遍历到尾加上新建节点加入
        // e = p.next这个操作一开始还没看懂，看到这个循环后面p=e，才知道这是遍历用，
        // 且是要获取的节点，与第一个if是一样的
        if ((e = p.next) == null) {
          p.next = newNode(hash, key, value, null);
          // 但循环8次时，也就是有八个节点时，binCount=7 条件成立，树化
          // TREEIFY_THRESHOLD=8
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            // 这里不是马上树化，其中还要再做判断，下面会做一个介绍
            treeifyBin(tab, hash);
          break;
        }
        // 判断这个key是否已存在，存在则覆盖值，到后面统一处理
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        // 这个相当于游标，让链表遍历下去
        p = e;
      }
    }
    // 这里就是上个面说的要同一处理的地方，键一样值不一样，替换值
    if (e != null) { // existing mapping for key
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      afterNodeAccess(e);
      // 覆盖的话就是返回旧值
      return oldValue;
    }
  }
  ++modCount;
  // 如果新增节点后，节点数量大于阈值时，也会扩容
  if (++size > threshold)
    resize();
  afterNodeInsertion(evict);
  // 新增放回null
  return null;
}

// 最小槽位树化阈值
static final int MIN_TREEIFY_CAPACITY = 64;

// 树化判断
final void treeifyBin(Node<K,V>[] tab, int hash) {
  int n, index; Node<K,V> e;
  // 在这里可以看出，不是当一条链表节点数达到8时马上扩容，而会先判断槽位是否到达64，如果到达才会树化
  if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();
  else if ((e = tab[index = (n - 1) & hash]) != null) {
    // ...做一些处理再树化
  }
}

在看扩容方法前，先看下几个参数，及默认值还有构造方法

// 这个是调用指定槽位数构造方法保存指定槽位数的一个变量
// 再下面的构造方法中可以看到
// 之后就作为阈值
int threshold;

// 负载因子
final float loadFactor;
// 负载因子默认值
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 无参构造方法
public HashMap() {
  // 负载因子初始化为默认的0.75
  this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 指定容量（更准确的说应该是底层数组的长度，也有通俗的叫法，桶、槽）构造方法，
public HashMap(int initialCapacity) {
  // 这里调用了另外一个构造方法
  this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap(int initialCapacity, float loadFactor) {
    // ... 这里少贴了代码，是校验参数的
  
  this.loadFactor = loadFactor;
  // 由于HashMap的扩容设计，数组长度必须是2的n次方，tableSizeFor方法返回比参数大的最接近的2的n次方
  this.threshold = tableSizeFor(initialCapacity);
}

扩容

// 最大槽位数
static final int MAXIMUM_CAPACITY = 1 << 30;
// 最小能树化的槽位数
static final int MIN_TREEIFY_CAPACITY = 64;
// 未指定槽位数首次扩容为 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 扩容
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是非首次扩容
  if (oldCap > 0) {
    // 当旧的槽位数 大于等于最大数值，就不再扩容，直接返回
    if (oldCap >= MAXIMUM_CAPACITY) {
      threshold = Integer.MAX_VALUE;
      return oldTab;
    }
    // 否则就2倍扩容，这个扩容是在判断里完成的，这个判断用于计算扩容阈值的
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
      // 做为扩容阈值的threshold也扩大至原来2倍
      newThr = oldThr << 1; // double threshold
  }
  // 指定了槽位数，初次扩容会走这，使槽位扩容至大于指定槽位数最近的一个2的n次方
  else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr;
  // 若没有指定槽位数，那么槽位就扩容至默认的16，
  // threshold就作为扩容阈值
  else {               // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  
  // 计算扩容阈值
  if (newThr == 0) {
    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) {
    for (int j = 0; j < oldCap; ++j) {
      Node<K,V> e;
      // 先判断槽是不是空的
      if ((e = oldTab[j]) != null) {
        oldTab[j] = null;
        // 判断槽是不是一个节点
        if (e.next == null)
          newTab[e.hash & (newCap - 1)] = e;
        // 如果这是课树的话，按树的方式处理，split方法在下面介绍
        else if (e instanceof TreeNode)
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        // 只能是链表了
        else { // preserve order
          // 把一条链表里的节点分成高位与低位两条链表，再放到相应的槽位
          // HashMap为什么要把槽位设计成2的n次方，就是利用hash与槽位相与，快速定位节点迁移位置
          Node<K,V> loHead = null, loTail = null;
          Node<K,V> hiHead = null, hiTail = null;
          Node<K,V> next;
          // 分链表
          do {
            next = e.next;
            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;
            newTab[j] = loHead;
          }
          if (hiTail != null) {
            hiTail.next = null;
            newTab[j + oldCap] = hiHead;
          }
        }
      }
    }
  }
  return newTab;
}

// 当树节点个数小于等于6时，就变回链表，在下面有出现
// 这里有连个特殊的值，6和8，中间有个7作为缓冲，频繁切换
static final int UNTREEIFY_THRESHOLD = 6;

// 这里看下如果是树的话，在扩容时是怎么拆分的
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
  TreeNode<K,V> b = this;
  // Relink into lo and hi lists, preserving order
  TreeNode<K,V> loHead = null, loTail = null;
  TreeNode<K,V> hiHead = null, hiTail = null;
  int lc = 0, hc = 0;
  // 这里可以看到e.next，这个next不属于树的结构，而是链表的结构，就一开始介绍数据结构部分时提到
  // 因为有了这个next，所以这棵树拆分其实并不是按树的方式来，而是看作链表，所以其实与上面链表的拆分差不多
  for (TreeNode<K,V> e = b, next; e != null; e = next) {
    next = (TreeNode<K,V>)e.next;
    e.next = null;
    if ((e.hash & bit) == 0) {
      if ((e.prev = loTail) == null)
        loHead = e;
      else
        loTail.next = e;
      loTail = e;
      ++lc;
    }
    else {
      if ((e.prev = hiTail) == null)
        hiHead = e;
      else
        hiTail.next = e;
      hiTail = e;
      ++hc;
    }
  }
  // 高低位，与之前一样的
  if (loHead != null) {
    // 数的节点个数小于等于 6 时，就变回链表
    if (lc <= UNTREEIFY_THRESHOLD)
      tab[index] = loHead.untreeify(map);
    // 反之则树化
    else {
      tab[index] = loHead;
      if (hiHead != null) // (else is already treeified)
        loHead.treeify(tab);
    }
  }
  if (hiHead != null) {
    if (hc <= UNTREEIFY_THRESHOLD)
      tab[index + bit] = hiHead.untreeify(map);
    else {
      tab[index + bit] = hiHead;
      if (loHead != null)
        hiHead.treeify(tab);
    }
  }
}

// 具体树化的逻辑就不看了，关于红黑树直接去看算法，HashMap中夹杂了业务逻辑就更复杂了。