繼ArrayList和LinkedList之後，我準備深入學習下HashMap的源碼。看源碼之前，我隻知道HashMap是HashTable的輕量級實作，允許使用null值和null鍵，非線程安全，并不能保證映射的順序。但是如果想了解諸如HashMap的實作原理，怎樣保證key的唯一性，實作get和put的機制是什麼，那麼就得看看源碼怎麼做的。
HashMap的資料結構是數組和連結清單的結合體，即中和ArrayList和LinkedList的優點。我們知道JAVA最基本的資料結構有數組和連結清單，數組的特點是空間連續，尋址迅速但插入和删除需要移動元素，查詢快而增加删除慢；連結清單剛好相反，可動态增加或減少空間以新增和删除元素，但查找隻能順着一個個節點查找，增加删除快而查找慢。盡管HashMap号稱集兩家之所長，但實際上它查找肯定沒數組快，插入删除沒連結清單快，算是一種折中的方法吧。
她的資料結構如下圖所示：(網上直接下載下傳的~)
言歸正傳。
HashMap內建AbstractMap，實作Map，Cloneable和Serializable接口，擁有Map的特性病可以clone和序列化。
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
HashMap中的屬性：
/**
* 預設初始容量，必須是2的幂
*/
static final int DEFAULT_INITIAL_CAPACITY = 16;
/**
* 最大容量（2的30次方），容量過大将用該值替換
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 預設裝載因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* HashMap中用于存儲資料的數組，長度是2的幂.
*/
transient Entry<K,V>[] table;
/**
* HashMap中儲存鍵值對的數量
*/
transient int size;
/**
* 調整因子：需要調整大小的極限值（容量*裝載因子）
*/
int threshold;
/**
* 裝載因子
*
* @serial
*/
final float loadFactor;
/**
* map結構被改變的次數
*/
transient int modCount;
由于我用的JDK1.7， HashMap中有與優化字元串key帶來的碰撞問題而存在内部類Holder，成員變量useAltHashing，hashSeed等，這些在1.8中移除，是以就不再提了。
接下來是構造函數
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
* 根據給定的初始容量和裝載因子建立一個空的HashMap
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
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))//裝載因子<=0或包含非數字，報異常
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find a power of 2 >= initialCapacity
int capacity = 1;//設定capacity為大于initialCapacity且是2的幂的最小值
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();//空方法，不知做什麼用
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
* 方法重載，根據給定初始容量和預設裝載因子建立一個空的HashMap
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {//構造預設的HashMap（初始容量16，裝載因子0.75）
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* 通過傳入一個Map建立HashMap，容量為預設值16和(m.size() / DEFAULT_LOAD_FACTOR) + 1的較大者
* 裝載因子為預設值
*/
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
putAllForCreate(m);
}
總結如下：
HashMap 包含如下幾個構造器：
HashMap()：建構一個初始容量為 16，負載因子為 0.75 的 HashMap。
HashMap(int initialCapacity)：建構一個初始容量為 initialCapacity，負載因子為 0.75 的 HashMap。
HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的負載因子建立一個 HashMap。
HashMap的基礎構造器HashMap(int initialCapacity, float loadFactor)帶有兩個參數，它們是初始容量initialCapacity和加載因子loadFactor。
initialCapacity：HashMap的最大容量，即為底層數組的長度。
loadFactor：負載因子loadFactor定義為：散清單的實際元素數目(n)/ 散清單的容量(m)。
負載因子衡量的是一個散清單的空間的使用程度，負載因子越大表示散清單的裝填程度越高，反之愈小。對于使用連結清單法的散清單來說，查找一個元素的平均時間是O(1+a)，是以如果負載因子越大，對空間的利用更充分，然而後果是查找效率的降低；如果負載因子太小，那麼散清單的資料将過于稀疏，對空間造成嚴重浪費。
threshold就是在此loadFactor和capacity對應下允許的最大元素數目，超過這個數目就重新resize，以降低實際的負載因子。預設的的負載因子0.75是對空間和時間效率的一個平衡選擇。當容量超出此最大容量時， resize後的HashMap容量是容量的兩倍。
初始化table時使用了Entry，這是HashMap的内部類，實作了Map接口中的Entry接口。
Map.Entry接口中定義的方法：
K getKey(); //擷取key
V getValue(); //擷取value
V setValue(V value); //設定value
boolean equals(Object o);//判斷兩個Entry是否相等
int hashCode(); //擷取hashCode的方法
HashMap.Entry的具體實作
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;//對下一個節點的引用，這裡跟最上面的資料結構對應上了
int hash;
/**
* Creates new entry.
*/
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;
}
//設定newValue之後，傳回的是設定前的值
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;//轉換o為Entry對象
Object k1 = getKey();//key1是目前Entry的key
Object k2 = e.getKey();//key2是待比較Entry的key
if (k1 == k2 || (k1 != null && k1.equals(k2))) {//如果k1，k2相等，比較其value
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))//如果value也相等，傳回true
return true;
}
return false;
}
//該方法傳回的是key的哈希值與value的哈希值異或的結果
public final int hashCode() {
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
void recordAccess(HashMap<K,V> m) {//<span style="font-family: Arial, Helvetica, sans-serif;">英文解釋說調用put(k,v)方法存入鍵值對時，如果key存在，則該方法被調用，但為毛啥也沒有呢</span>
}
/**
* This method is invoked whenever the entry is
* removed from the table.
*/
void recordRemoval(HashMap<K,V> m) {//<span style="font-family: Arial, Helvetica, sans-serif;">英文解釋說當entry移除時調用該方法，</span><span style="font-family: Arial, Helvetica, sans-serif;">但為毛也啥都沒有呢</span><span style="font-family: Arial, Helvetica, sans-serif;">
</span>
}
看完了屬性和構造方法，下面看HashMap中其他常用的方法：
hashMap的存取實作：
public V put(K key, V value)
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
if (key == null)//hashMap允許存放null鍵和null值，當key為null，調用putForNullKey(),将value放在數組第一個位置。
return putForNullKey(value);
int hash = hash(key);//根據key的hashcode計算hash值
int i = indexFor(hash, table.length);//搜尋指定hash值在table中的索引
for (Entry<K,V> e = table[i]; e != null; e = e.next) {//如果索引i處的entry不為空，則循環周遊下一個元素
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//如果k存在，則更新value值
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);//若索引i處的entry為null，則将key，value添加到i處
return null;
}
從上面的源碼我們可以看出hashMap存儲的實作原理：
首先根據key的hashCode重新計算hash值，根據此hash值搜尋在數組中的索引，如果數組中的這個位置的key與待存儲的key相同，則更新value值；如果該位置已經存儲其他元素了，那麼這個位置上的所有元素将以連結清單的形式存放，新加入的放在連結清單頭，最新加入的放在連結清單尾；如果該位置上沒有元素，則直接将該元素放到該位置上
hash(Object k)方法根據k的hashCode重新計算散列，此算法加入了高位計算，防止低位不變，高位變化時造成的hash沖突。
/**
* Retrieve object hash code and applies a supplemental hash function to the
* result hash, which defends against poor quality hash functions. This is
* critical because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
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);
}
我們可以看到在HashMap中要找到某個元素，需要根據key的hash值來求得對應數組中的位置。如何計算這個位置就是hash算法。前面說過HashMap的資料結構是數組和連結清單的結合，是以我們當然希望這個HashMap裡面的 元素位置盡量的分布均勻些，盡量使得每個位置上的元素數量隻有一個，那麼當我們用hash算法求得這個位置的時候，馬上就可以知道對應位置的元素就是我們要的，而不用再去周遊連結清單，這樣就大大優化了查詢的效率。
對于任意給定的對象，隻要它的 hashCode() 傳回值相同，那麼程式調用 hash(int h) 方法所計算得到的 hash 碼值總是相同的。我們首先想到的就是把hash值對數組長度取模運算，這樣一來，元素的分布相對來說是比較均勻的。但是，“模”運算的消耗還是比較大的，在HashMap中是這樣做的：調用 indexFor(int h, int length) 方法來計算該對象應該儲存在 table 數組的哪個索引處。indexFor(int h, int length) 方法的代碼如下：
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
這個方法非常巧妙，它通過 h & (table.length -1) 來得到該對象的儲存位，而 HashMap 底層數組的長度總是 2 的 n 次方，這是 HashMap 在速度上的優化。
當length總是 2 的n次方時，h& (length-1)運算等價于對length取模，也就是h%length，但是&比%具有更高的效率。
這看上去很簡單，其實比較有玄機的，我們舉個例子來說明：
假設數組長度分别為15和16，優化後的hash碼分别為8和9，那麼&運算後的結果如下：
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
從上面的例子中可以看出：當它們和15-1（1110）“與”的時候，産生了相同的結果，也就是說它們會定位到數組中的同一個位置上去，這就産生了碰撞，8和9會被放到數組中的同一個位置上形成連結清單，那麼查詢的時候就需要周遊這個鍊 表，得到8或者9，這樣就降低了查詢的效率。同時，我們也可以發現，當數組長度為15的時候，hash值會與15-1（1110）進行“與”，那麼 最後一位永遠是0，而0001，0011，0101，1001，1011，0111，1101這幾個位置永遠都不能存放元素了，空間浪費相當大，更糟的是這種情況中，數組可以使用的位置比數組長度小了很多，這意味着進一步增加了碰撞的幾率，減慢了查詢的效率！而當數組長度為16時，即為2的n次方時，2n-1得到的二進制數的每個位上的值都為1，這使得在低位上&時，得到的和原hash的低位相同，加之hash(int h)方法對key的hashCode的進一步優化，加入了高位計算，就使得隻有相同的hash值的兩個值才會被放到數組中的同一個位置上形成連結清單。
是以說，當數組長度為2的n次幂的時候，不同的key算得得index相同的幾率較小，那麼資料在數組上分布就比較均勻，也就是說碰撞的幾率小，相對的，查詢的時候就不用周遊某個位置上的連結清單，這樣查詢效率也就較高了。
根據上面 put 方法的源代碼可以看出，當程式試圖将一個key-value對放入HashMap中時，程式首先根據該 key的 hashCode() 傳回值決定該 Entry 的存儲位置：如果兩個 Entry 的 key 的 hashCode() 傳回值相同，那它們的存儲位置相同。如果這兩個 Entry 的 key 通過 equals 比較傳回 true，新添加 Entry 的 value 将覆寫集合中原有Entry 的 value，但key不會覆寫。如果這兩個 Entry 的 key 通過 equals 比較傳回 false，新添加的 Entry 将與集合中原有 Entry 形成 Entry 鍊，而且新添加的 Entry 位于 Entry 鍊的頭部。
（摘自http://zhangshixi.iteye.com/blog/672697）
/**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket. It is the responsibility of this
* method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
/**
* Like addEntry except that this version is used when creating entries
* as part of Map construction or "pseudo-construction" (cloning,
* deserialization). This version needn't worry about resizing the table.
*
* Subclass overrides this to alter the behavior of HashMap(Map),
* clone, and readObject.
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
get方法：
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
private V getForNullKey() {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
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算法作為基礎，了解起來這段代碼就很容易了。從上面的源代碼中可以看出：從HashMap中get元素時，如果key為null，則擷取第一個元素中的value, key不為null，計算key的hashCode，找到數組中對應位置的某一進制素，然後通過key的equals方法在對應位置的連結清單中找到需要的元素。
歸納起來簡單地說，HashMap 在底層将 key-value 當成一個整體進行處理，這個整體就是一個 Entry 對象。HashMap 底層采用一個 Entry[] 數組來儲存所有的 key-value 對，當需要存儲一個 Entry 對象時，會根據hash算法來決定其在數組中的存儲位置，在根據equals方法決定其在該數組位置上的連結清單中的存儲位置；當需要取出一個Entry時，也會根據hash算法找到其在數組中的存儲位置，再根據equals方法從該位置上的連結清單中取出該Entry。
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);
}
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
當HashMap中的元素越來越多的時候，hash沖突的幾率也就越來越高，因為數組的長度是固定的。是以為了提高查詢的效率，就要對HashMap的數組進行擴容，數組擴容這個操作也會出現在ArrayList中，這是一個常用的操作，而在HashMap數組擴容之後，最消耗性能的點就出現了：原數組中的資料必須重新計算其在新數組中的位置，并放進去，這就是resize。
那麼HashMap什麼時候進行擴容呢？當HashMap中的元素個數超過數組大小*loadFactor時，就會進行數組擴容，loadFactor的預設值為0.75，這是一個折中的取值。也就是說，預設情況下，數組大小為16，那麼當HashMap中元素個數超過16*0.75=12的時候，就把數組的大小擴充為 2*16=32，即擴大一倍，然後重新計算每個元素在數組中的位置，而這是一個非常消耗性能的操作，是以如果我們已經預知HashMap中元素的個數，那麼預設元素的個數能夠有效的提高HashMap的性能。
fail-fast 機制
我們知道java.util.HashMap不是線程安全的，是以如果在使用疊代器的過程中有其他線程修改了map，那麼将抛出ConcurrentModificationException，這就是所謂fail-fast政策。
這一政策在源碼中的實作是通過modCount域，modCount顧名思義就是修改次數，對HashMap内容的修改都将增加這個值，那麼在疊代器初始化過程中會将這個值賦給疊代器的expectedModCount。
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
在疊代過程中，判斷modCount跟expectedModCount是否相等，如果不相等就表示已經有其他線程修改了Map：
注意到modCount聲明為volatile，保證線程之間修改的可見性。
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
在HashMap的API中指出：
由所有HashMap類的“collection 視圖方法”所傳回的疊代器都是快速失敗的：在疊代器建立之後，如果從結構上對映射進行修改，除非通過疊代器本身的 remove 方法，其他任何時間任何方式的修改，疊代器都将抛出ConcurrentModificationException。是以，面對并發的修改，疊代器很快就會完全失敗，而不冒在将來不确定的時間發生任意不确定行為的風險。
注意，疊代器的快速失敗行為不能得到保證，一般來說，存在非同步的并發修改時，不可能作出任何堅決的保證。快速失敗疊代器盡最大努力抛出 ConcurrentModificationException。是以，編寫依賴于此異常的程式的做法是錯誤的，正确做法是：疊代器的快速失敗行為應該僅用于檢測程式錯誤。
（摘自http://zhangshixi.iteye.com/blog/672697）
![實驗吧WEBWP(一）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)