深入理解Java之HashMap源码剖析

 Map map = Collections.synchronizedMap(new HashMap());

 /** Entry是单向链表。 
  * 它是 “HashMap链式存储法”对应的链表。 
  *它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数 
 **/ 
 static class Entry<K,V> implements Map.Entry<K,V> { 
  final K key; 
  V value; 
  // 指向下一个节点 
  Entry<K,V> next; 
  final int hash; 
  // 构造函数。 
  // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)" 
  Entry(int h, K k, V v, Entry<K,V> n) { 
   value = v; 
   next = n; 
   key = k; 
   hash = h; 
  } 
  public final K getKey() { 
   return key; 
  } 
  public final V getValue() { 
   return value; 
  } 
  public final V setValue(V newValue) { 
   V oldValue = value; 
   value = newValue; 
   return oldValue; 
  } 
  // 判断两个Entry是否相等 
  // 若两个Entry的“key”和“value”都相等，则返回true。 
  // 否则，返回false 
  public final boolean equals(Object o) { 
   if (!(o instanceof Map.Entry)) 
    return false; 
   Map.Entry e = (Map.Entry)o; 
   Object k1 = getKey(); 
   Object k2 = e.getKey(); 
   if (k1 == k2 || (k1 != null && k1.equals(k2))) { 
    Object v1 = getValue(); 
    Object v2 = e.getValue(); 
    if (v1 == v2 || (v1 != null && v1.equals(v2))) 
     return true; 
   } 
   return false; 
  } 
  // 实现hashCode() 
  public final int hashCode() { 
   return (key==null ? 0 : key.hashCode()) ^ 
     (value==null ? 0 : value.hashCode()); 
  } 
  public final String toString() { 
   return getKey() + "=" + getValue(); 
  } 
  // 当向HashMap中添加元素时，绘调用recordAccess()。 
  // 这里不做任何处理 
  void recordAccess(HashMap<K,V> m) { 
  } 
  // 当从HashMap中删除元素时，绘调用recordRemoval()。 
  // 这里不做任何处理 
  void recordRemoval(HashMap<K,V> m) { 
  } 
 }

transient Entry[] table;//存储元素的实体数组
transient int size;//存放元素的个数
int threshold; //临界值 当实际大小超过临界值时，会进行扩容threshold = 加载因子*容量
 final float loadFactor; //加载因子
transient int modCount;//被修改的次数

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);
  // Find a power of 2 >= initialCapacity
  int capacity = 1; //初始容量
  while (capacity < initialCapacity) //确保容量为2的n次幂，使capacity为大于initialCapacity的最小的2的n次幂
   capacity <<= 1;
  this.loadFactor = loadFactor;
  threshold = (int)(capacity * loadFactor);
  table = new Entry[capacity];
  init();
 }
 public HashMap(int initialCapacity) {
  this(initialCapacity, DEFAULT_LOAD_FACTOR);
 }
 public HashMap() {
  this.loadFactor = DEFAULT_LOAD_FACTOR;
  threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
  table = new Entry[DEFAULT_INITIAL_CAPACITY];
  init();
 }

public V put(K key, V value) {
  // 若“key为null”，则将该键值对添加到table[0]中。
   if (key == null) 
   return putForNullKey(value);
  // 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。
   int hash = hash(key.hashCode());
  //搜索指定hash值在对应table中的索引
   int i = indexFor(hash, table.length);
  // 循环遍历Entry数组,若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！
   for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
    Object k;
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { //如果key相同则覆盖并返回旧值
     V oldValue = e.value;
     e.value = value;
     e.recordAccess(this);
     return oldValue;
    }
   }
  //修改次数+1
   modCount++;
  //将key-value添加到table[i]处
  addEntry(hash, key, value, i);
  return null;
}

private V putForNullKey(V value) {
  for (Entry<K,V> e = table[0]; e != null; e = e.next) {
   if (e.key == null) { //如果有key为null的对象存在，则覆盖掉
    V oldValue = e.value;
    e.value = value;
    e.recordAccess(this);
    return oldValue;
   }
  }
  modCount++;
  addEntry(0, null, value, 0); //如果键为null的话，则hash值为0
  return null;
 }

//计算hash值的方法 通过键的hashCode来计算
 static int hash(int h) {
  // This function ensures that hashCodes that differ only by
  // constant multiples at each bit position have a bounded
  // number of collisions (approximately 8 at default load factor).
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
 }

  static int indexFor(int h, int length) { //根据hash值和数组长度算出索引值
   return h & (length-1); //这里不能随便算取，用hash&(length-1)是有原因的，这样可以确保算出来的索引是在数组大小范围内，不会超出
  }

h & (table.length-1)     hash       table.length-1
8 & (15-1)：       0100    &    1110   =  0100
9 & (15-1)：       0101    &    1110   =  0100
------------------------------------------------------------------
8 & (16-1)：       0100    &    1111   =   0100
9 & (16-1)：       0101    &    1111   =   0101

 void addEntry(int hash, K key, V value, int bucketIndex) {
   Entry<K,V> e = table[bucketIndex]; //如果要加入的位置有值，将该位置原先的值设置为新entry的next,也就是新entry链表的下一个节点
   table[bucketIndex] = new Entry<>(hash, key, value, e);
   if (size++ >= threshold) //如果大于临界值就扩容
   resize(2 * table.length); //以2的倍数扩容
  }

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);//用来将原先table的元素全部移到newTable里面
  table = newTable; //再将newTable赋值给table
  threshold = (int)(newCapacity * loadFactor);//重新计算临界值
 }

public V get(Object key) { 
 if (key == null) 
  return getForNullKey(); 
 int hash = hash(keyhashCode()); 
 for (Entry<K,V> e = table[indexFor(hash, tablelength)]; 
  e != null; 
  e = enext) { 
  Object k; 
  if (ehash == hash && ((k = ekey) == key || keyequals(k))) 
   return evalue; 
 } 
 return null; 
}

threshold = (int)(capacity * loadFactor);