//默認初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//默認最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

//默認加載因子, 指哈希表可以達到多滿的尺度
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//空的哈希表
static final Entry<?,?>[] EMPTY_TABLE = {};

//實際使用的哈希表
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

//HashMap大小, 即HashMap存儲的鍵值對數量
transient int size;

//鍵值對的閾值, 用于判斷是否需要擴增哈希表容量
int threshold;

//加載因子
final float loadFactor;

//修改次數, 用于fail-fast機制
transient int modCount;

//使用替代哈希的默認閥值
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

//隨機的哈希種子, 有助于減少哈希碰撞的次數
transient int hashSeed = 0;

static class Entry<K,V> implements Map.Entry<K,V> {
  final K key;   //鍵
  V value;     //值
  Entry<K,V> next; //下一個Entry的引用
  int hash;     //哈希碼
  
  ...        //省略下面代碼
}

//構造器, 傳入初始化容量和加載因子
public HashMap(int initialCapacity, float loadFactor) {
  if (initialCapacity < 0) {
    throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
  }
  //如果初始化容量大于最大容量, 就把它設為最大容量
  if (initialCapacity > MAXIMUM_CAPACITY) {
    initialCapacity = MAXIMUM_CAPACITY;
  }
  //如果加載因子小于0或者加載因子不是浮點數, 則拋出異常
  if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
    throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
  }
  //設置加載因子
  this.loadFactor = loadFactor;
  //閾值為初始化容量
  threshold = initialCapacity;
  init();
}

void init() {}

//放置key-value鍵值對到HashMap中
public V put(K key, V value) {
  //如果哈希表沒有初始化就進行初始化
  if (table == EMPTY_TABLE) {
    //初始化哈希表
    inflateTable(threshold);
  }
  if (key == null) {
    return putForNullKey(value);
  }
  //計算key的hash碼
  int hash = hash(key);
  //根據hash碼定位在哈希表的位置
  int i = indexFor(hash, table.length);
  for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    Object k;
    //如果對應的key已經存在, 就替換它的value值, 并返回原先的value值
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
      V oldValue = e.value;
      e.value = value;
      e.recordAccess(this);
      return oldValue;
    }
  }
  modCount++;
  //如果沒有對應的key就添加Entry到HashMap中
  addEntry(hash, key, value, i);
  //添加成功返回null
  return null;
}

//初始化哈希表, 會對哈希表容量進行膨脹, 因為有可能傳入的容量不是2的冪
private void inflateTable(int toSize) {
  //哈希表容量必須是2的次冪
  int capacity = roundUpToPowerOf2(toSize);
  //設置閥值, 這里一般是取capacity*loadFactor
  threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
  //新建指定容量的哈希表
  table = new Entry[capacity];
  //初始化哈希種子
  initHashSeedAsNeeded(capacity);
}

//添加Entry方法, 先判斷是否要擴容
void addEntry(int hash, K key, V value, int bucketIndex) {
  //如果HashMap的大小大于閥值并且哈希表對應槽位的值不為空
  if ((size >= threshold) && (null != table[bucketIndex])) {
    //因為HashMap的大小大于閥值, 表明即將發生哈希沖突, 所以進行擴容
    resize(2 * table.length);
    hash = (null != key) ? hash(key) : 0;
    bucketIndex = indexFor(hash, table.length);
  }
  //在這里表明HashMap的大小沒有超過閥值, 所以不需要擴容
  createEntry(hash, key, value, bucketIndex);
}

//對哈希表進行擴容
void resize(int newCapacity) {
  Entry[] oldTable = table;
  int oldCapacity = oldTable.length;
  //如果當前已經是最大容量就只能增大閥值了
  if (oldCapacity == MAXIMUM_CAPACITY) {
    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);
}

 //返回哈希碼對應的數組下標
 static int indexFor(int h, int length) {
   return h & (length-1);
 }

//生成hash碼的函數
final int hash(Object k) {
  int h = hashSeed;
  //key是String類型的就使用另外的哈希算法
  if (0 != h && k instanceof String) {
    return sun.misc.Hashing.stringHash42((String) k);
  }
  h ^= k.hashCode();
  //擾動函數
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
}