HashMap 是基于哈希表的 Map 接口的非同步實現(xiàn)。此實現(xiàn)提供所有可選的映射操作，并允許使用 null 值和 null 鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。
此實現(xiàn)假定哈希函數(shù)將元素適當(dāng)?shù)胤植荚诟魍爸g，可為基本操作（get 和 put）提供穩(wěn)定的性能。迭代 collection 視圖所需的時間與 HashMap 實例的“容量”（桶的數(shù)量）及其大?。ㄦI-值映射關(guān)系數(shù)）成比例。所以，如果迭代性能很重要，則不要將初始容量設(shè)置得太高或?qū)⒓虞d因子設(shè)置得太低。也許大家開始對這段話有一點不太懂，不過不用擔(dān)心，當(dāng)你讀完這篇文章后，就能深切理解這其中的含義了。
需要注意的是：Hashmap 不是同步的，如果多個線程同時訪問一個 HashMap，而其中至少一個線程從結(jié)構(gòu)上（指添加或者刪除一個或多個映射關(guān)系的任何操作）修改了，則必須保持外部同步，以防止對映射進(jìn)行意外的非同步訪問。
在 Java 編程語言中，最基本的結(jié)構(gòu)就是兩種，一個是數(shù)組，另外一個是指針（引用），HashMap 就是通過這兩個數(shù)據(jù)結(jié)構(gòu)進(jìn)行實現(xiàn)。HashMap實際上是一個“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)合體。
http://wiki.jikexueyuan.com/project/java-collection/images/hashmap1.jpg" alt="圖1" />
從上圖中可以看出，HashMap 底層就是一個數(shù)組結(jié)構(gòu)，數(shù)組中的每一項又是一個鏈表。當(dāng)新建一個 HashMap 的時候，就會初始化一個數(shù)組。
我們通過 JDK 中的 HashMap 源碼進(jìn)行一些學(xué)習(xí)，首先看一下構(gòu)造函數(shù)：
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();
}我們著重看一下第 18 行代碼table = new Entry[capacity];。這不就是 Java 中數(shù)組的創(chuàng)建方式嗎？也就是說在構(gòu)造函數(shù)中，其創(chuàng)建了一個 Entry 的數(shù)組，其大小為 capacity（目前我們還不需要太了解該變量含義），那么 Entry 又是什么結(jié)構(gòu)呢？看一下源碼：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
……
}我們目前還是只著重核心的部分，Entry 是一個 static class，其中包含了 key 和 value，也就是鍵值對，另外還包含了一個 next 的 Entry 指針。我們可以總結(jié)出：Entry 就是數(shù)組中的元素，每個 Entry 其實就是一個 key-value 對，它持有一個指向下一個元素的引用，這就構(gòu)成了鏈表。
/**
* 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) {
//其允許存放null的key和null的value，當(dāng)其key為null時，調(diào)用putForNullKey方法，放入到table[0]的這個位置
if (key == null)
return putForNullKey(value);
//通過調(diào)用hash方法對key進(jìn)行哈希，得到哈希之后的數(shù)值。該方法實現(xiàn)可以通過看源碼，其目的是為了盡可能的讓鍵值對可以分不到不同的桶中
int hash = hash(key);
//根據(jù)上一步驟中求出的hash得到在數(shù)組中是索引i
int i = indexFor(hash, table.length);
//如果i處的Entry不為null，則通過其next指針不斷遍歷e元素的下一個元素。
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))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}我們看一下方法的標(biāo)準(zhǔn)注釋：在注釋中首先提到了，當(dāng)我們 put 的時候，如果 key 存在了，那么新的 value 會代替舊的 value，并且如果 key 存在的情況下，該方法返回的是舊的 value，如果 key 不存在，那么返回 null。
從上面的源代碼中可以看出：當(dāng)我們往 HashMap 中 put 元素的時候，先根據(jù) key 的 hashCode 重新計算 hash 值，根據(jù) hash 值得到這個元素在數(shù)組中的位置（即下標(biāo)），如果數(shù)組該位置上已經(jīng)存放有其他元素了，那么在這個位置上的元素將以鏈表的形式存放，新加入的放在鏈頭，最先加入的放在鏈尾。如果數(shù)組該位置上沒有元素，就直接將該元素放到此數(shù)組中的該位置上。
addEntry(hash, key, value, i)方法根據(jù)計算出的 hash 值，將 key-value 對放在數(shù)組 table 的 i 索引處。addEntry 是 HashMap 提供的一個包訪問權(quán)限的方法，代碼如下：
/**
* 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);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
// 獲取指定 bucketIndex 索引處的 Entry
Entry<K,V> e = table[bucketIndex];
// 將新創(chuàng)建的 Entry 放入 bucketIndex 索引處，并讓新的 Entry 指向原來的 Entr
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}當(dāng)系統(tǒng)決定存儲 HashMap 中的 key-value 對時，完全沒有考慮 Entry 中的 value，僅僅只是根據(jù) key 來計算并決定每個 Entry 的存儲位置。我們完全可以把 Map 集合中的 value 當(dāng)成 key 的附屬，當(dāng)系統(tǒng)決定了 key 的存儲位置之后，value 隨之保存在那里即可。
hash(int h)方法根據(jù) key 的 hashCode 重新計算一次散列。此算法加入了高位計算，防止低位不變，高位變化時，造成的 hash 沖突。
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
//得到k的hashcode值
h ^= k.hashCode();
//進(jìn)行計算
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}我們可以看到在 HashMap 中要找到某個元素，需要根據(jù) key 的 hash 值來求得對應(yīng)數(shù)組中的位置。如何計算這個位置就是 hash 算法。前面說過 HashMap 的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表的結(jié)合，所以我們當(dāng)然希望這個 HashMap 里面的 元素位置盡量的分布均勻些，盡量使得每個位置上的元素數(shù)量只有一個，那么當(dāng)我們用 hash 算法求得這個位置的時候，馬上就可以知道對應(yīng)位置的元素就是我們要的，而不用再去遍歷鏈表，這樣就大大優(yōu)化了查詢的效率。
對于任意給定的對象，只要它的 hashCode() 返回值相同，那么程序調(diào)用 hash(int h) 方法所計算得到的 hash 碼值總是相同的。我們首先想到的就是把 hash 值對數(shù)組長度取模運算，這樣一來，元素的分布相對來說是比較均勻的。但是，“?！边\算的消耗還是比較大的，在 HashMap 中是這樣做的：調(diào)用 indexFor(int h, int length) 方法來計算該對象應(yīng)該保存在 table 數(shù)組的哪個索引處。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 底層數(shù)組的長度總是 2 的 n 次方，這是 HashMap 在速度上的優(yōu)化。在 HashMap 構(gòu)造器中有如下代碼：
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;這段代碼保證初始化時 HashMap 的容量總是 2 的 n 次方，即底層數(shù)組的長度總是為 2 的 n 次方。
當(dāng) length 總是 2 的 n 次方時，h& (length-1)運算等價于對 length 取模，也就是 h%length，但是 & 比 % 具有更高的效率。這看上去很簡單，其實比較有玄機(jī)的，我們舉個例子來說明：
假設(shè)數(shù)組長度分別為 15 和 16，優(yōu)化后的 hash 碼分別為 8 和 9，那么 & 運算后的結(jié)果如下：
| 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 |
從上面的例子中可以看出：當(dāng)它們和 15-1（1110）“與”的時候，產(chǎn)生了相同的結(jié)果，也就是說它們會定位到數(shù)組中的同一個位置上去，這就產(chǎn)生了碰撞，8 和 9 會被放到數(shù)組中的同一個位置上形成鏈表，那么查詢的時候就需要遍歷這個鏈 表，得到8或者9，這樣就降低了查詢的效率。同時，我們也可以發(fā)現(xiàn)，當(dāng)數(shù)組長度為 15 的時候，hash 值會與 15-1（1110）進(jìn)行“與”，那么最后一位永遠(yuǎn)是 0，而 0001，0011，0101，1001，1011，0111，1101 這幾個位置永遠(yuǎn)都不能存放元素了，空間浪費相當(dāng)大，更糟的是這種情況中，數(shù)組可以使用的位置比數(shù)組長度小了很多，這意味著進(jìn)一步增加了碰撞的幾率，減慢了查詢的效率！而當(dāng)數(shù)組長度為16時，即為2的n次方時，2n-1 得到的二進(jìn)制數(shù)的每個位上的值都為 1，這使得在低位上&時，得到的和原 hash 的低位相同，加之 hash(int h)方法對 key 的 hashCode 的進(jìn)一步優(yōu)化，加入了高位計算，就使得只有相同的 hash 值的兩個值才會被放到數(shù)組中的同一個位置上形成鏈表。
所以說，當(dāng)數(shù)組長度為 2 的 n 次冪的時候，不同的 key 算得得 index 相同的幾率較小，那么數(shù)據(jù)在數(shù)組上分布就比較均勻，也就是說碰撞的幾率小，相對的，查詢的時候就不用遍歷某個位置上的鏈表，這樣查詢效率也就較高了。
根據(jù)上面 put 方法的源代碼可以看出，當(dāng)程序試圖將一個key-value對放入HashMap中時，程序首先根據(jù)該 key 的 hashCode() 返回值決定該 Entry 的存儲位置：如果兩個 Entry 的 key 的 hashCode() 返回值相同，那它們的存儲位置相同。如果這兩個 Entry 的 key 通過 equals 比較返回 true，新添加 Entry 的 value 將覆蓋集合中原有 Entry 的 value，但key不會覆蓋。如果這兩個 Entry 的 key 通過 equals 比較返回 false，新添加的 Entry 將與集合中原有 Entry 形成 Entry 鏈，而且新添加的 Entry 位于 Entry 鏈的頭部——具體說明繼續(xù)看 addEntry() 方法的說明。
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
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 算法作為基礎(chǔ)，理解起來這段代碼就很容易了。從上面的源代碼中可以看出：從 HashMap 中 get 元素時，首先計算 key 的 hashCode，找到數(shù)組中對應(yīng)位置的某一元素，然后通過 key 的 equals 方法在對應(yīng)位置的鏈表中找到需要的元素。
簡單地說，HashMap 在底層將 key-value 當(dāng)成一個整體進(jìn)行處理，這個整體就是一個 Entry 對象。HashMap 底層采用一個 Entry[] 數(shù)組來保存所有的 key-value 對，當(dāng)需要存儲一個 Entry 對象時，會根據(jù) hash 算法來決定其在數(shù)組中的存儲位置，在根據(jù) equals 方法決定其在該數(shù)組位置上的鏈表中的存儲位置；當(dāng)需要取出一個Entry 時，也會根據(jù) hash 算法找到其在數(shù)組中的存儲位置，再根據(jù) equals 方法從該位置上的鏈表中取出該Entry。
當(dāng) HashMap 中的元素越來越多的時候，hash 沖突的幾率也就越來越高，因為數(shù)組的長度是固定的。所以為了提高查詢的效率，就要對 HashMap 的數(shù)組進(jìn)行擴(kuò)容，數(shù)組擴(kuò)容這個操作也會出現(xiàn)在 ArrayList 中，這是一個常用的操作，而在 HashMap 數(shù)組擴(kuò)容之后，最消耗性能的點就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計算其在新數(shù)組中的位置，并放進(jìn)去，這就是 resize。
那么 HashMap 什么時候進(jìn)行擴(kuò)容呢？當(dāng) HashMap 中的元素個數(shù)超過數(shù)組大小 *loadFactor時，就會進(jìn)行數(shù)組擴(kuò)容，loadFactor的默認(rèn)值為 0.75，這是一個折中的取值。也就是說，默認(rèn)情況下，數(shù)組大小為 16，那么當(dāng) HashMap 中元素個數(shù)超過 16*0.75=12 的時候，就把數(shù)組的大小擴(kuò)展為 2*16=32，即擴(kuò)大一倍，然后重新計算每個元素在數(shù)組中的位置，而這是一個非常消耗性能的操作，所以如果我們已經(jīng)預(yù)知 HashMap 中元素的個數(shù)，那么預(yù)設(shè)元素的個數(shù)能夠有效的提高 HashMap 的性能。
HashMap 包含如下幾個構(gòu)造器：
HashMap 的基礎(chǔ)構(gòu)造器 HashMap(int initialCapacity, float loadFactor) 帶有兩個參數(shù)，它們是初始容量 initialCapacity 和負(fù)載因子 loadFactor。
負(fù)載因子 loadFactor 衡量的是一個散列表的空間的使用程度，負(fù)載因子越大表示散列表的裝填程度越高，反之愈小。對于使用鏈表法的散列表來說，查找一個元素的平均時間是 O(1+a)，因此如果負(fù)載因子越大，對空間的利用更充分，然而后果是查找效率的降低；如果負(fù)載因子太小，那么散列表的數(shù)據(jù)將過于稀疏，對空間造成嚴(yán)重浪費。
HashMap 的實現(xiàn)中，通過 threshold 字段來判斷 HashMap 的最大容量：
threshold = (int)(capacity * loadFactor);結(jié)合負(fù)載因子的定義公式可知，threshold 就是在此 loadFactor 和 capacity 對應(yīng)下允許的最大元素數(shù)目，超過這個數(shù)目就重新 resize，以降低實際的負(fù)載因子。默認(rèn)的的負(fù)載因子 0.75 是對空間和時間效率的一個平衡選擇。當(dāng)容量超出此最大容量時， resize 后的 HashMap 容量是容量的兩倍：
我們知道 java.util.HashMap 不是線程安全的，因此如果在使用迭代器的過程中有其他線程修改了 map，那么將拋出 ConcurrentModificationException，這就是所謂 fail-fast 策略。
ail-fast 機(jī)制是 java 集合(Collection)中的一種錯誤機(jī)制。 當(dāng)多個線程對同一個集合的內(nèi)容進(jìn)行操作時，就可能會產(chǎn)生 fail-fast 事件。
例如：當(dāng)某一個線程 A 通過 iterator去遍歷某集合的過程中，若該集合的內(nèi)容被其他線程所改變了；那么線程 A 訪問集合時，就會拋出 ConcurrentModificationException 異常，產(chǎn)生 fail-fast 事件。
這一策略在源碼中的實現(xiàn)是通過 modCount 域，modCount 顧名思義就是修改次數(shù)，對 HashMap 內(nèi)容（當(dāng)然不僅僅是 HashMap 才會有，其他例如 ArrayList 也會）的修改都將增加這個值（大家可以再回頭看一下其源碼，在很多操作中都有 modCount++ 這句），那么在迭代器初始化過程中會將這個值賦給迭代器的 expectedModCount。
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}在迭代過程中，判斷 modCount 跟 expectedModCount 是否相等，如果不相等就表示已經(jīng)有其他線程修改了 Map：
注意到 modCount 聲明為 volatile，保證線程之間修改的可見性。
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();在 HashMap 的 API 中指出：
由所有 HashMap 類的“collection 視圖方法”所返回的迭代器都是快速失敗的：在迭代器創(chuàng)建之后，如果從結(jié)構(gòu)上對映射進(jìn)行修改，除非通過迭代器本身的 remove 方法，其他任何時間任何方式的修改，迭代器都將拋出 ConcurrentModificationException。因此，面對并發(fā)的修改，迭代器很快就會完全失敗，而不冒在將來不確定的時間發(fā)生任意不確定行為的風(fēng)險。
注意，迭代器的快速失敗行為不能得到保證，一般來說，存在非同步的并發(fā)修改時，不可能作出任何堅決的保證。快速失敗迭代器盡最大努力拋出 ConcurrentModificationException。因此，編寫依賴于此異常的程序的做法是錯誤的，正確做法是：迭代器的快速失敗行為應(yīng)該僅用于檢測程序錯誤。
在上文中也提到，fail-fast 機(jī)制，是一種錯誤檢測機(jī)制。它只能被用來檢測錯誤，因為 JDK 并不保證 fail-fast 機(jī)制一定會發(fā)生。若在多線程環(huán)境下使用 fail-fast 機(jī)制的集合，建議使用“java.util.concurrent 包下的類”去取代“java.util 包下的類”。
Map map = new HashMap();
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}效率高,以后一定要使用此種方式！
Map map = new HashMap();
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
Object key = iter.next();
Object val = map.get(key);
}效率低,以后盡量少使用！
掃碼關(guān)注鍍金池微信號
手機(jī)訂課，優(yōu)惠多多