一 概述

public class HashMap<K,V>  extends AbstractMap<K,V>  implements Map<K,V>, Cloneable, Serializable

基于哈希表的Map接口的實現。此實現提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。此實現不是同步的。如果多個線程同時訪問一個哈希映射，而其中至少一個線程從結構上修改了該映射，則它必須 保持外部同步。

二 構造函數

static final int DEFAULT_INITIAL_CAPACITY = 16;//默認大小16
static final int MAXIMUM_CAPACITY = 1 << 30;//2的30次方
static final float DEFAULT_LOAD_FACTOR = 0.75f;//默認裝填因子0.75
transient Entry<K,V>[] table;
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)            capacity <<= 1;        this.loadFactor = loadFactor;        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);        table = new Entry[capacity];        useAltHashing = sun.misc.VM.isBooted() &&                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);        init();    }    public HashMap(int initialCapacity) {        this(initialCapacity, DEFAULT_LOAD_FACTOR);    }    public HashMap() {        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);    }hash表的裝填因子=表中填入記錄數/表的長度。分析第一個構造函數：
int capacity = 1;while (capacity < initialCapacity)    capacity <<= 1;保證capacity的大小為大于且最接近initialCapacity的2的次冪。原因后續討論。
三 indexFor()函數
static int indexFor(int h, int length) {     return h & (length-1);}采用&運算尋找索引，先看indexFor()的使用：
final Entry<K,V> getEntry(Object key) {        int hash = (key == null) ? 0 : hash(key);        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 != null && key.equals(k))))                return e;        }        return null;}hash()函數：
final int hash(Object k) {        int h = 0;        if (useAltHashing) {            if (k instanceof String) {                return sun.misc.Hashing.stringHash32((String) k);            }            h = hashSeed;        }        h ^= k.hashCode();        // 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); }由上述調用邏輯可以看出，給定一個key尋找它所對應entry的過程為：
（1）計算hash(key)。
（2）計算indexFor(hash(key),table.length),即為該條目在table[]中的索引。
（3）遍歷該索引上的鏈表找到==或equal key的entry返回。
四 capacity為何要是2的次方（個人理解）
（1）當capacity=2的次方時：h&(capacity-1)==h%capacity，例：
h=7,capacity=8        h%capacity=7,h&(7)=0111&0111=0111;
h=9,capacity=8        h%capacity=1,h&(7)=1001&0111=0001;
于是，可用位運算代替模運算大大加快運算速度。
（2）取capacity為2的次方能提高存儲空間利用率，減少沖突。例：
h=9,capacity=8       h%capacity=1,h&(7)=1001&0111=0001;
h=8,capacity=8       h%capacity=0,h&(7)=1000&0111=0000;
h=9,capacity=7       h%capacity=2,h&(6)=1001&0110=0000;
h=8,capacity=7       h%capacity=1,h&(6)=1000&0110=0000;
由上可見當capacity為奇數時，capacity-1位偶數，其二進制最低為必為0，與h進行與運算后最低位必為0，意味著只有編號為偶數的index才有可能存儲數據，浪費了存儲空間，增加沖突概率；而capacity為2的n次方時，capacity-1的二進制最低位為1，進行&運算后最低位為0或1都有可能，不存在上述缺陷。
五 為什么不直接用hashcode()（個人理解）
hashcode()為32位，而capacity默認為16位，如果兩個對象的hashcode（）后16位相同，與16位的capacity-1進行&后得到相同的結果，產生沖突，所以通過hash（）函數進行處理。
六 resize()
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];        boolean oldAltHashing = useAltHashing;        useAltHashing |= sun.misc.VM.isBooted() &&                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);        boolean rehash = oldAltHashing ^ useAltHashing;        transfer(newTable, rehash);        table = newTable;        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);    }（1）何時擴容（resize）?
當HashMap中的元素個數超過數組大小*loadFactor時。
（2）如何擴容？
容量變為原來的兩倍，然后重新計算每個元素在數組中的位置，這是一個非常消耗性能的操作，所以如果我們已經預知HashMap中元素的個數，那么預設元素的個數能夠有效的提高HashMap的性能。
七 Fail-Fast機制
HashMap不是線程安全的，如果在使用迭代器的過程中有其他線程修改了map，那么將拋出ConcurrentModificationException異常。判斷是否修改了map是通過modCount（修改次數）域，對HashMap內容的修改都將增加這個值，那么在迭代器初始化過程中會將這個值賦給迭代器的expectedModCount。
在迭代過程中，判斷modCount和expectedModCount是否相等，如果不相等就表示已經有其他線程修改了Map。
一般來說，存在非同步的并發修改時不可能作出任何的保證。Fail-Fast盡最大努力拋出 ConcurrentModificationException。因此，編寫依賴于此異常的程序的做法是錯誤的，正確做法是：迭代器的快速失敗行為應該僅用于檢測程序錯誤。