HashMap源码大剖析

// 默认的初始化容量，16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 默认的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 链表长度达到8时转化为红黑树
static final int TREEIFY_THRESHOLD = 8;
// 结点个数小于等于6时，红黑树退化为单链表
static final int UNTREEIFY_THRESHOLD = 6;
// 树的最小容量
static final int MIN_TREEIFY_CAPACITY = 64;

// 哈希表
transient Node<K,V>[] table;
// Entry集合
transient Set<Map.Entry<K,V>> entrySet;
// 实际存储kv对的个数
transient int size;
// HashMap内部结构发生变化的次数
transient int modCount;
// 初始化数组容量，若threshold为0，则初始化数组容量为16
int threshold;
// 负载因子
final float loadFactor;

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

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev; 
        boolean red;
}

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}

public HashMap(int initialCapacity, float loadFactor) {
  if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
  if (initialCapacity > MAXIMUM_CAPACITY)
    initialCapacity = MAXIMUM_CAPACITY;
  if (loadFactor <= 0 || Float.isNaN(loadFactor))
    throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
  this.loadFactor = loadFactor;
  this.threshold = tableSizeFor(initialCapacity);
}

public HashMap(int initialCapacity) {
  this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

static final int tableSizeFor(int cap) {
  int n = cap - 1;
  n |= n >>> 1;
  n |= n >>> 2;
  n |= n >>> 4;
  n |= n >>> 8;
  n |= n >>> 16;
  return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

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);
}

int h = key.hashCode();
h ^ (h >>> 16);

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
  
  Node<K,V>[] tab; // 哈希桶数组
  Node<K,V> p; // 结点
  int n; // 哈希桶数组长度
  int i; //索引
  // 如果哈希桶数组为null 或 长度为0
  if ((tab = table) == null || (n = tab.length) == 0)
    // 对哈希桶数组进行扩容
    n = (tab = resize()).length;
  // 标记1：通过i = (n - 1) & hash计算，得到索引为i的槽位为空
  if ((p = tab[i = (n - 1) & hash]) == null)
    // 则直接new一个Node，将其放入空槽位
    tab[i] = newNode(hash, key, value, null);
  else {
    Node<K,V> e; 
    K k;
    // 要put的key 与 标记1中获取的对象p地址相同(是==判断的)，那么equals一定相等，从而hashcode也一定相等
    // 要put的key 与 标记1中获取的对象p equals相等
    
    if (p.hash == hash &&
      ((k = p.key) == key || (key != null && key.equals(k))))
      // 满足上述两个条件之一，则表明要put的key 与 标记1中获取的对象p是同一个对象
      e = p;
    // 表示该槽位是红黑树
    else if (p instanceof TreeNode)
      // 委托给putTreeVal方法，让它去处理红黑树结点的插入
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
      // 表示该槽位是单链表,则在该单链表上顺序查找
      for (int binCount = 0; ; ++binCount) {
        // 代表在该单链表上没有找到相同的key
        if ((e = p.next) == null) {
          // 则直接在单链表的末尾插入新结点
          p.next = newNode(hash, key, value, null);
          if (binCount >= TREEIFY_THRESHOLD - 1)
            // 超过了阈值，委托给treeifyBin方法将单链表转换为红黑树
            treeifyBin(tab, hash);
          break;
        }
        //代表在该单链表上找到了相同的key
        if (e.hash == hash &&
          ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        p = e;
      }
    }
    // 如果成功插入了，则e为null，如果要插入的key已存在，则e为已存在的结点
    if (e != null) { // existing mapping for key
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      afterNodeAccess(e);
      return oldValue;
    }
  }
  
  //成功插入新结点后，需要记录modCount，且判断是否有必要进行扩容
  ++modCount;
  if (++size > threshold)
    // kv对个数超过阈值，则扩容
    resize();
  afterNodeInsertion(evict);
  return null;
}

final Node<K,V>[] resize() {
  Node<K,V>[] oldTab = table; // 旧的哈希桶数组
  int oldCap = (oldTab == null) ? 0 : oldTab.length; // 旧的容量
  int oldThr = threshold; // 旧的阈值
  int newCap = 0; // 新的容量
  int newThr = 0; // 新的阈值
  // 旧容量不为0时，出现这种情况，表示哈希表已经初始化
  if (oldCap > 0) {
    if (oldCap >= MAXIMUM_CAPACITY) {
      // 如果旧容量已经达到最大容量，则将阈值设为int的最大值，且不进行扩容
      threshold = Integer.MAX_VALUE;
      return oldTab;
    }
    // 旧容量>=默认容量 且 扩容后的新容量 < 最大容量,则容量和阈值都扩大两倍
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
         oldCap >= DEFAULT_INITIAL_CAPACITY)
      newThr = oldThr << 1;
  }
  // 标志1：阈值大于0时，新容量=阈值。出现这种情况是因为调用了有参构造方法，且是第一次put元素（即哈希表还未初始化）
  else if (oldThr > 0)
    newCap = oldThr;
  
  // 当旧容量和旧阈值都是0时，进入此分支。出现这种情况是因为调用了无惨构造方法
  else { 
    // 新容量设为默认容量
    newCap = DEFAULT_INITIAL_CAPACITY;
    // 新阈值就是默认容量*默认负载因子
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  // 出现这种情况，是因为走了上面标志1的代码
  if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
          (int)ft : Integer.MAX_VALUE);
  }
  threshold = newThr;
  
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // new一个Node数组，长度为新容量大小
  table = newTab; // 将引用指向新的哈希桶
  // 旧哈希表不为null时，需要对旧哈希表上的元素向新哈希表做迁移；否则，不需要迁移，直接返回上一步new好的新哈希表
  if (oldTab != null) {
    // 遍历旧哈希桶
    for (int j = 0; j < oldCap; ++j) {
      Node<K,V> e; // 旧哈希桶的元素
      
      // 只将不为null的槽位 搬到 新的哈希桶数组中来
      if ((e = oldTab[j]) != null) {
        oldTab[j] = null;
        if (e.next == null)
          // 表示该槽位只有一个元素，则新位置为e.hash & (newCap - 1)
          // 新位置与旧位置的关系：如果hash/旧容量=偶数，那么新位置与旧位置相同，否则不同
          newTab[e.hash & (newCap - 1)] = e;
        else if (e instanceof TreeNode)
          // 表示该槽位是红黑树结构
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        else { 
          // 表示该槽位有多个元素，且是单链表结构
          // java7在复制单链表时，是在while循环里面，单个计算好数组索引位置后，单个地插入新数组中，在多线程情况下，会有回环问题
          // java8是等链表整个while循环结束后,才给新数组赋值，所以多线程情况下，也不会成环
          // 老值表示，迁移后索引不变的元素；新值表示索引会变
          // 举个例子，扩容前容量为16，扩容后容量为31，有两个元素，hash值分别为33,50，33在迁移前后的索引都为1，是老值；50在迁移前索引为2，迁移后索引为18=16+2，是新值
          Node<K,V> loHead = null; // 老值头指针
          Node<K,V> loTail = null; // 老值尾指针
          Node<K,V> hiHead = null; // 新值头指针
          Node<K,V> 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;
}