静态变量

  1. // 序列号版本UID编号 , 用于序列化
  2. private static final long serialVersionUID = 362498820763181265L;
  3. // 默认初始容量 2^4 = 16 , 必须是2的倍数
  4. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  5. // 最大容量 = 2^30
  6. static final int MAXIMUM_CAPACITY = 1 << 30;
  7. // 默认扩容因子 = 0.75f
  8. static final float DEFAULT_LOAD_FACTOR = 0.75f;
  9. // 默认链表转换红黑树阈值 = 8 
  10. static final int TREEIFY_THRESHOLD = 8;
  11. // 默认由红黑树转换链表的阈值 = 6
  12. static final int UNTREEIFY_THRESHOLD = 6;
  13. // 默认链表转化红黑树的最小容量值 = 64 , 至少是TREEIFY_THRESHOLD的4倍
  14. static final int MIN_TREEIFY_CAPACITY = 64;

成员变量

  1. // hash表数据
  2. transient Node<K, V>[] table;
  3. // Set集
  4. transient Set<Entry<K, V>> entrySet;
  5. // 大小
  6. transient int size;
  7. // modCount
  8. transient int modCount;
  9. // 扩容容量阈值
  10. int threshold;
  11. // 扩容因子
  12. final float loadFactor;

扩容

1.获取扩容容量阈值newThr和新表容量newCap(newThr)

  1. 旧表有数据,newThr2,newCap看情况2/MAX/Default
  2. 旧表无数据,oldThr > 0,newCap=oldThr,新容量等于旧扩容容量阈值
  3. 其他情况赋默认值
  • 最后防止newThr超出最大值
  • threshold = newThr

2.生成新表,copy旧表数据

  • table = newTab = new Node[newCap]
  1. 数组形式:更新新地址下标hashcode & newCap - 1
  2. 红黑树形式:split
  3. 链表形式:原链表根据hascode & oldCap 值[0,1]一分为二,0位置不动 / 1位置增加扩容长度
    1. // 扩容
    2. final Node<K, V>[] resize() {
    3.  // 旧表 = 类成员表
    4.  Node<K, V>[] oldTab = table;
    5.  // 旧表容量初始化 0 / length
    6.  int oldCap = (oldTab == null) ? 0 : oldTab.length;
    7.  // 旧扩容容量阈值 = 类成员扩容容量阈值
    8.  int oldThr = threshold;
    9.  int newCap, newThr = 0;
    10.  // 旧表初始化过
    11.  if (oldCap > 0) {
    12.      // 旧表容量大于最大容量,扩容容量阈值拉满 => 无法再次扩容
    13.      if (oldCap >= MAXIMUM_CAPACITY) {
    14.          threshold = Integer.MAX_VALUE;
    15.          return oldTab;
    16.      }
    17.      // 扩容翻倍小于最大容量 && 旧表容量大于默认容量,扩容容量阈值翻倍
    18.      else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
    19.               oldCap >= DEFAULT_INITIAL_CAPACITY) { newThr = oldThr << 1; }
    20.  }
    21.  // 旧表未初始化,且旧扩容容量阈值 > 0,新容量 = 旧扩容容量阈值
    22.  else if (oldThr > 0) { newCap = oldThr; }
    23.  // 其他情况
    24.  else {
    25.      // 赋默认值
    26.      newCap = DEFAULT_INITIAL_CAPACITY;
    27.      newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    28.  }
    29.  // 新扩容容量阈值未赋值,1.=新容量 * 扩容因子 2.无法扩容
    30.  if (newThr == 0) {
    31.      float ft = (float) newCap * loadFactor;
    32.      newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
    33.                (int) ft : Integer.MAX_VALUE);
    34.  }
    35.  // 类成员扩容容量阈值变量赋值
    36.  threshold = newThr;
    37.  // 警告剔除
    38.  @SuppressWarnings({"rawtypes", "unchecked"})
    39.  Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
    40.  // 类成员表变量赋值
    41.  table = newTab;
    42.  // 旧表不为空情况下
    43.  if (oldTab != null) {
    44.      for (int j = 0; j < oldCap; ++j) {
    45.          Node<K, V> e;
    46.          // j位置数据存在
    47.          if ((e = oldTab[j]) != null) {
    48.              oldTab[j] = null;
    49.              // 不是链表结构,不存在hash冲突
    50.              if (e.next == null)
    51.                  // 计算新hashcode位置并赋值 - 11111 新增前置位随机0/1
    52.              { newTab[e.hash & (newCap - 1)] = e; }
    53.              // 是红黑树结构
    54.              else if (e instanceof TreeNode) { ((TreeNode<K, V>) e).split(this, newTab, j, oldCap); }
    55.              // 是链表结构, 分为两组存储 新标记位0/1
    56.              else {
    57.                  // & oldCap = 0
    58.                  Node<K, V> loHead = null, loTail = null;
    59.                  // & oldCap != 0
    60.                  Node<K, V> hiHead = null, hiTail = null;
    61.                  Node<K, V> next;
    62.                  do {
    63.                      next = e.next;
    64.                      // 新标记位 = 0
    65.                      if ((e.hash & oldCap) == 0) {
    66.                          if (loTail == null) { loHead = e; } else { loTail.next = e; }
    67.                          loTail = e;
    68.                      } else {
    69.                          // 新标记位 != 0
    70.                          if (hiTail == null) { hiHead = e; } else { hiTail.next = e; }
    71.                          hiTail = e;
    72.                      }
    73.                  } while ((e = next) != null);
    74.                  // 原位置
    75.                  if (loTail != null) {
    76.                      loTail.next = null;
    77.                      newTab[j] = loHead;
    78.                  }
    79.                  // 新位置 + 扩容长度
    80.                  if (hiTail != null) {
    81.                      hiTail.next = null;
    82.                      newTab[j + oldCap] = hiHead;
    83.                  }
    84.              }
    85.          }
    86.      }
    87.  }
    88.  return newTab;
    89. }