Java集合4 - Map (HashMap)

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

static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// newCapacity为新的容量
void resize(int newCapacity) {
  // 小数组，临时过度下
  Entry[] oldTable = table;
  // 扩容前的容量
  int oldCapacity = oldTable.length;
  // MAXIMUM_CAPACITY 为最大容量，2 的 30 次方 = 1<<30
  if (oldCapacity == MAXIMUM_CAPACITY) {
      // 容量调整为 Integer 的最大值 0x7fffffff（十六进制）=2 的 31 次方-1
      threshold = Integer.MAX_VALUE;
      return;
  }

  // 初始化一个新的数组（大容量）
  Entry[] newTable = new Entry[newCapacity];
  // 把小数组的元素转移到大数组中
  transfer(newTable, initHashSeedAsNeeded(newCapacity));
  // 引用新的大数组
  table = newTable;
  // 重新计算阈值
  threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

// 新容量 newCapacity 被初始化为原容量 oldCapacity 的两倍
int newCapacity = oldCapacity * 2;
if (newCapacity < 0 || newCapacity >= MAXIMUM_CAPACITY) {
  // 最大容量设置
  newCapacity = MAXIMUM_CAPACITY;
} else if (newCapacity < DEFAULT_INITIAL_CAPACITY) {
  // 小于容量设置
  newCapacity = DEFAULT_INITIAL_CAPACITY;
}

int newCapacity = oldCapacity << 1;
if (newCapacity >= DEFAULT_INITIAL_CAPACITY && oldCapacity >= DEFAULT_INITIAL_CAPACITY) {
  if (newCapacity > MAXIMUM_CAPACITY)
      newCapacity = MAXIMUM_CAPACITY;
} else {
  if (newCapacity < DEFAULT_INITIAL_CAPACITY)
      newCapacity = DEFAULT_INITIAL_CAPACITY;
}

static class Node<K,V> implements Map.Entry<K,V> {
  final int hash;
  final K key;
  V value;
  Node<K,V> next;

  Node(int hash, K key, V value, Node<K,V> next) {
      this.hash = hash;
      this.key = key;
      this.value = value;
      this.next = next;
  }
  ...
}

void transfer(Entry[] newTable, boolean rehash) {
  // 新的容量
  int newCapacity = newTable.length;
  // 遍历小数组
  for (Entry<K,V> e : table) {
    while(null != e) {
      // 拉链法，相同 key 上的不同值
      Entry<K,V> next = e.next;
      // 是否需要重新计算 hash
      if (rehash) {
          e.hash = null == e.key ? 0 : hash(e.key);
      }
      // 根据大数组的容量，和键的 hash 计算元素在数组中的下标
      int i = indexFor(e.hash, newCapacity);

      // 同一位置上的新元素被放在链表的头部
      e.next = newTable[i];

      // 放在新的数组上
      newTable[i] = e;

      // 链表上的下一个元素
      e = next;
    }
  }
}

final Node<K,V>[] resize() {
  Node<K,V>[] oldTab = table; // 获取原来的数组 table
  int oldCap = (oldTab == null) ? 0 : oldTab.length; // 获取数组长度 oldCap
  int oldThr = threshold; // 获取阈值 oldThr
  int newCap, newThr = 0;
  // 如果原来的数组 table 不为空
  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)
        newThr = oldThr << 1; // double threshold
  }
  // 否则说明 oldCap < 0 改一下
  // initial capacity was placed in threshold
  else if (oldThr > 0) 
      newCap = oldThr;
  // 如果 cap 和 阈值 都小于0
  // 初始化
  else { 
    // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  // 计算新的 resize 上限
  if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
  }
  ///////////////////////////////////////////////////////////
  
  threshold = newThr; // 将新阈值赋值给成员变量 threshold
  @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 
    // 创建新数组 newTab
  table = newTab; // 将新数组 newTab 赋值给成员变量 table

  // 如果旧数组 oldTab 不为空
  // 需要扩容+转移
  if (oldTab != null) {
    // 遍历旧数组的每个元素
    for (int j = 0; j < oldCap; ++j) { 
      Node<K,V> e;
      if ((e = oldTab[j]) != null) { 
        // 如果该元素不为空
        oldTab[j] = null; 
        // 将旧数组中该位置的元素置为 null，以便垃圾回收
        if (e.next == null) // 如果该元素没有冲突
            newTab[e.hash & (newCap - 1)] = e; 
            // 直接将该元素放入新数组
        
        // 如果该元素是树节点
        // 将该树节点分裂成两个链表
        else if (e instanceof TreeNode)
            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        
        // 如果该元素是链表
        else { 
            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; // 将低位链表的尾结点指向 null，以便垃圾回收
                newTab[j] = loHead; // 将低位链表作为新数组对应位置的元素
            }
            if (hiTail != null) { // 如果高位链表不为空
                hiTail.next = null; // 将高位链表的尾结点指向 null，以便垃圾回收
                newTab[j + oldCap] = hiHead; // 将高位链表作为新数组对应位置的元素
            }
        }
      }
    }
  }
  return newTab; // 返回新数组
}