HashMap也是比較常用的一個集合，比如ZooKeeper中就用的比較多。而且HashMap也是面試中常被問到，今天就來探讨一下HashMap。
HashMap結構
從上圖可以看出，HashMap底層就是一個數組結構，數組中的每一項又是一個連結清單。
transient Entry<K, V>[] table;
public HashMap(int paramInt, float paramFloat){
if (paramInt < ) {
throw new IllegalArgumentException("Illegal initial capacity: " + paramInt);
}
if (paramInt > )
paramInt = ;
if ((paramFloat <= F) || (Float.isNaN(paramFloat))) {
throw new IllegalArgumentException("Illegal load factor: " + paramFloat);
}
int i = ;
while (i < paramInt) {
i <<= ;
}
this.loadFactor = paramFloat;
this.threshold = ((int)Math.min(i * paramFloat, F));
this.table = new Entry[i]; //初始化數組
this.useAltHashing = ((VM.isBooted()) && (i >= Holder.ALTERNATIVE_HASHING_THRESHOLD));
init();
}
static class Entry<K, V> implements Map.Entry<K, V>{
final K key;
V value;
Entry<K, V> next;
int hash;
....
}
從源碼中可以看出，當建立一個HashMap的時候，就會初始化一個數組，Entry就是數組中的元素，每個 Map.Entry 其實就是一個key-value對，它持有一個指向下一個元素的引用，這就構成了連結清單。
注意：在java8中HashMap稍微有些改變，當連結清單的長度超過8個時，會将連結清單轉換為紅黑樹
HashMap的存取
PUT
/**
* 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，當其key為null時，調用putForNullKey方法，放入到table[]的這個位置
if (key == null)
return putForNullKey(value);
//通過調用hash方法對key進行哈希，得到哈希之後的數值。該方法實作可以通過看源碼，其目的是為了盡可能的讓鍵值對可以分不到不同的桶中
int hash = hash(key);
//根據上一步驟中求出的hash得到在數組中是索引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;
//如果key的hash值相等并且key相同說明已經存在相同的key,将新的value存入并傳回舊的value
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;
}
在注釋中已經說明，當我們put的時候，如果key存在了，那麼新的value會代替舊的value，并且如果key存在的情況下，該方法傳回的是舊的value，如果key不存在，那麼傳回null。
從上面的源代碼中可以看出：當我們往HashMap中put元素的時候，先根據key的hashCode重新計算hash值，根據hash值得到這個元素在數組中的位置（即下标）， 如果數組該位置上已經存放有其他元素了，那麼在這個位置上的元素将以連結清單的形式存放，新加入的放在鍊頭，最先加入的放在鍊尾（java8中剛好相反，新加入的放在鍊尾）。如果數組該位置上沒有元素，就直接将該元素放到此數組中的該位置上。
/**
* 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) {
// 如果目前 HashMap 大小已經達到了門檻值，并且新值要插入的數組位置已經有元素了，那麼要擴容
if ((size >= threshold) && (null != table[bucketIndex])) {
// 2倍擴容，後面會介紹一下
resize( * table.length);
// 擴容以後，重新計算 hash 值
hash = (null != key) ? hash(key) : ;
// 重新計算擴容後的新的下标
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
// 将新值放到連結清單的表頭，然後 size++
void createEntry(int hash, K key, V value, int bucketIndex) {
// 擷取指定 bucketIndex 索引處的 Entry
Entry<K,V> e = table[bucketIndex];
// 将新建立的 Entry 放入 bucketIndex 索引處，并讓新的 Entry 指向原來的 Entr
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
這個方法的主要邏輯就是先判斷是否需要擴容，需要的話先擴容，然後再将這個新的資料插入到擴容後的數組的相應位置處的連結清單的表頭。
數組擴容
前面我們看到，在插入新值的時候，如果目前的 size 已經達到了門檻值，并且要插入的數組位置上已經有元素，那麼就會觸發擴容，擴容後，數組大小為原來的 2 倍（為什麼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, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + );
}
擴容就是用一個新的大數組替換原來的小數組，并将原來數組中的值遷移到新的數組中。
由于是雙倍擴容，遷移過程中，會将原來 table[i] 中的連結清單的所有節點，分拆到新的數組的 newTable[i] 和 newTable[i + oldLength] 位置上。如原來數組長度是 16，那麼擴容後，原來 table[0] 處的連結清單中的所有元素會被配置設定到新數組中 newTable[0] 和 newTable[16] 這兩個位置。
hash值計算
final int hash(Object k) {
int h = ;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
//得到k的hashcode值
h ^= k.hashCode();
//進行計算
h ^= (h >>> ) ^ (h >>> );
return h ^ (h >>> ) ^ (h >>> );
}
hash(int h)方法根據key的hashCode重新計算一次散列。此算法加入了高位計算，防止低位不變，高位變化時，造成的hash沖突。我們可以看到在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-);
}
這個方法非常巧妙，它通過 h & (table.length -1) 來得到該對象的儲存位，而HashMap底層數組的長度總是 2 的 n 次方（是以說2倍擴容也是有原因的），這是HashMap在速度上的優化。在 HashMap 構造器中有如下代碼：
// Find a power of 2 >= initialCapacity
int capacity = ;
while (capacity < initialCapacity)
capacity <<= ;
這段代碼保證初始化時HashMap的容量總是2的n次方，即底層數組的長度總是為2的n次方。
當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（即1111），這使得在低位上&時，得到的和原hash的低位相同，加之hash(int h)方法對key的hashCode的進一步優化，加入了高位計算，就使得隻有相同的hash值的兩個值才會被放到數組中的同一個位置上形成連結清單。
GET
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) ? : 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的hashCode，找到數組中對應位置的某一進制素，然後通過key的equals方法在對應位置的連結清單中找到需要的元素。（如果hashCode不同，equals就不用再比較了）
是以說，當數組長度為2的n次幂的時候，不同的key算得得index相同的幾率較小，那麼資料在數組上分布就比較均勻，也就是說碰撞的幾率小，相對的，查詢的時候就不用周遊某個位置上的連結清單，這樣查詢效率也就較高了
HashMap周遊
第一種：常用，操作友善
foreach周遊
Map< String, String> map = new HashMap<>();
for(Map.Entry<String, String> entry : map.entrySet()){
String key= "+entry.getKey()
String value= "+entry.getValue());
}
第二種：常用，效率高，推薦這種，特别是容量大的時候
Map< String, String> map = new HashMap<>();
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
String key = entry.getKey();
String val = entry.getValue();
}
第三種：效率低，不推薦使用
Map< String, String> map = new HashMap<>();
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
String key = iter.next();
String val = map.get(key);
}
HashMap缺點：
HashMap不支援并發操作，是以不适用與多線程環境。在高并發狀态下，如果産生同時put操作，并且在put時剛好遇上要擴容，可能會形成鍊環，如果get的key的hashcode值剛好在鍊環的位置，而這個key對應的值為 null或不存在，就會進入死循環，耗盡cpu記憶體。可以用ConcurrentHashMap解決這個問題。
參考部落格：李大輝部落格
http://www.importnew.com/28263.html
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)