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)： 1000 & 1110 = 1000 9 & (15-1)： 1001 & 1110 = 1000 ----------------------------------------------------------------------------------------------------------------------- 8 & (16-1)： 1000 & 1111 = 1000 9 & (16-1)： 1001 & 1111 = 1001

 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(key.hashCode());  for (Entry<K,V> e = table[indexFor(hash, table.length)];  e != null;  e = e.next) {  Object k;  if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  return e.value;  }  return null; } 

threshold = (int)(capacity * loadFactor);