693
Java中的HashMap淺析
在Java的集合框架中，HashSet，HashMap是用的比較多的一種，順序結構的ArrayList、LinkedList這種也比較多，而像那幾個線程同步的容器就用的比較少，像Vector和HashTable，因為這兩個線程同步的容器已經不被JDK推薦使用了，這是個比較老式的線程安全的容器，JDK比較推薦的是采用Collections裏麵的關於線程同步的方法。問題來源：
1.為什麼要有HashMap？
《Thinking In Java》裏麵有一個自己采用二維數組實現的保存key-value的demo，書上也說到性能問題，因為從數據結構的順序結構的觀點來看，常規的線性存儲，你弱需要找到其中的某個元素，就需要遍曆這個鏈表或者數組，而遍曆的同時需要讓鏈表中的每一個元素都和目標元素做比較，相等才返回，Java裏麵用equals或者==。這對性能是毀滅性的傷害。
2.HashMap的優勢是什麼？
Hash算法就是根據某個算法將一係列目標對象轉換成地址，當要獲取某個元素的時候，隻需要將目標對象做相應的運算獲得地址，直接獲取。
3.Java中的Hash？
事實上Java的數據無非就三種，基本類型，引用類型(類似C裏麵的指針類型）和數組，有些地方說是2種類型，隻有引用類型和數組。通過這三種數據類型可以構建出任何數據結構。在Java中，ArrayList這種底層就是用Objec數組來構建的，而HashMap也是用數組來構建，隻不過數據數組的數據類型是一個叫做Entry的內部類來保存key、value、hash(不是hashCode)和next(也就是鏈表的下一個元素)。其實HashSet也是HashMap，隻不過比較特殊，沒有使用Entry的value而隻用了key而已。看看HashSet的構造方法：
public HashSet() {
map = new HashMap<E,Object>();
}
所以從這個意義上來講就沒必要討論HashSet了，他隻不過是特殊的HashMap而已。
HashMap詳解：
基調：由於通過hash算法產生的邏輯地址可能導致衝突，所以對於一個長度為length的數組，裏麵存放小於length個數據元素的時候就有可能出現衝突的現象，因為比如說要在長度為16的數組中存放字符串(也就是一個空的HashMap默認的長度)，每個字符串通過調用自身的hashCode()方法會得到該字符串的hashCode，然後通過HashMap的這兩個方法會算出在數組中的位置，也就是下麵的 i。
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
任意字符串的hashCode通過上麵2個方法都會得到一個i，這個i就是在數組中的位置，這裏比較巧妙的設計就是indexFor(hash,table.length)這個方法：
static int indexFor(int h, int length) {
return h & (length-1);
}
這個方法裏麵的任意h與(length-1)做位運算之後得到的值始終都是在length之內的，也就是在數組table之內，因為拿任意一個數來和另一個數來做與運算，結果肯定是小於等於較小的哪一個數，我以前第一次看到這就比較震驚，為什麼那些人能想出這麼巧妙的計算在table中的位置的方法。與此同時，既然字符串調用hashCode()會得到一個值，那麼就會出現不相同的字符串調用hashCode方法之後得到的值是一樣的，這種可能性是存在的，而且幾乎肯定是存在的。這時候就需要在數組的某個位置增加一個鏈表結構，用戶存儲相同的hashCode的字符串，而這個時候HashMap的size同樣也會自增1，盡管這2個字符串隻有一個存在於數組中。HashMap中的size變量有兩個作用，第一是通過調用size()方法來返回map的長度，
public int size() {
return size;
}
第二個作用相當重要，就是解決hash算法的核心力量，解決衝突。在HashMap的構造方法中可以看出，hashmap的長度和底層數組table都是capacity，但是還有一個變量叫做threshold，極限值，閾值的意思，默認情況的構造方法：
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
這個閾值就是數組長度和加載因子的乘積，這東西有什麼用呢，假設都按照默認情況來看，默認構造方法構造出來的hashmap長度為16，底層數組長度也為16，而閾值
threshold長度為12，因為默認加載因子是0.75。也就是說當箱map中存放12個元素是，map的結構沒什麼變化，但是當存儲第13個的時候，table就需要擴容了，擴大為原來的2倍。這時候是什麼結局呢，如果加載因子是1，那麼map中存放16個的時候他是不會擴容的，table.length = 16,而為0.75的時候存放16個數據的時候table.length = 32。那麼同樣是存放16個數據，分別在長度為16的數組和32的數組中存放，出現衝突的幾率一般來說16的數組要大一些，那為什麼會大一些呢，因為某個數據存放進入數組的位置是根據
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
這兩個方法算出來的，其中就包括table.length，換句話說，位置i跟hash和table.length是相關的，也就是說位置i與table.length是聯動的，換個角度，存放的16個數據假設是固定的，而得出hashCode的算法也是固定的，那麼位置i就隻跟length的大小有關聯了，一般來說length越大，數據的衝突幾率就低一些，在map.getValue(key)的時候需要在鏈表中比較的次數就少一些，性能就高一些。這就是Java中hashmap的性能因素，一般來說加載因子factor大，同樣個數的數據所占用空間就越小，table.length就越小，衝突幾率就越大，反之空間利用率低，性能高，類比一下，比如你地上放了10個碗，你手裏麵握了10顆大米，你撒下去，前提是必須10顆米都要撒進碗裏，你是不是會發現有些碗裏麵裝了兩顆三顆，而有些碗是空的，接下來，你在地上擺20個碗，還是撒10顆米下去，依然是所有的米都要進碗，依然還是會出現有些晚是空的，有些是一顆兩顆三顆這種現象，但是很明顯一般來講20個碗的時候每個碗裏麵裝不止一顆的情況要比10個碗的情況要少，當然也不一定完全是這樣，但是一般來說是這樣，這就是hash算法，如果設計的好的情況下我們希望每個碗裏麵都最多放一顆進去，但是這種情況比較少見，但不管怎麼說，按照普遍情況來看，20個碗的裝多顆的情況是比10個碗裝多顆的情況要少一點。從數據結構的角度來說叫做用空間換時間的策略，以空間換時間何止hash算法，雙向鏈表也是用空間換時間的策略。至於說為什麼默認是0.75，我估計這個是前輩們和科學家們總結出來的一個這種的辦法，空間利用率比較不錯的同時性能比較令人接受吧。
順便說一下啊，當我們不斷的往一個hashmap裏麵添加數據的時候，如果超過某個閾值，他就會擴容，擴容的同時會讓之前的所有元素重新生成地址，並且把原來的數組裏麵的數據遷移到新的數組中(新的數組容量是原來的兩倍長度)。順便說下，這個數據遷移其實對性能損耗還是相當大的，畢竟你是要複製數組，同時要重新構建每個元素的在table中的位置，因此我們可以在使用hashMap之前大概的估算一下這個hashMap裏麵大概會存多少個元素，這樣就可以在new hashmap的時候就給定他的容量，這樣數據遷移的次數相對就少一些，性能就更好一點。
接下來從JDK的源碼來看看HashMap。
1.構造出一個空的HashMap。默認長度16，底層Entry數組也是16的默認長度。默認加載因子default_factor為0.75。閾值16*0.75=12。key和value都存在與Entry這個類型裏麵。
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
2.調用put方法。
| public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); 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; } } |
首先是判斷key是否為空，如果為空，那麼調用下麵這個方法，這個方法說明，HashMap的null的key始終是存放在table的table[0]位置的，不管table[0]位置有沒有衝突都是這樣。
| private V putForNullKey(V value) { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); return null; } |
如果不為空，那麼繼續，這裏，如果算出來的位置i出已經有元素了，說明衝突了，那麼遍曆衝突鏈表，如果發現key相等，那麼直接用新的value替換掉就的value並且返回舊的value。這裏隻判斷相等的情況而不判斷不相等的情況，也就是這裏不做添加操作。
| int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); 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; } } |
接下來，上麵的步驟說明，新添加的數據在位置i處不是key相等的情況，就真正的添加數據了。調用addEntry(hash, key, value, i)方法。
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
此時把新的添加進table[i]位置，而原來的數據(可能是null也可能是一個鏈表)的引用直接存放進新的數據的next中。形成新的鏈表。
接下來就是調用map的get(key)方法了。這個過程和put方法是逆向的。
| 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; } |
首先判斷key == null， 如過為true，那麼調用getForNullKey()方法。遍曆table[0]出的鏈表，因為空key是存在table[0]處的。前麵說到。
private V getForNullKey() {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
如果key == null 為false，那麼上麵get方法的下半部分，通過hashCode算出hash，通過hash和table.length算出位置i，遍曆table[i]處的鏈表，ken相等，取出數據。
| 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; |
這裏還有一個Java裏麵的規定，就是2個對象的equals相等，那麼hashCode也必須相等。但是hashCode相等equals不一定相等。這是hashmap存在於Java裏麵的依據，同時這就是為什麼會有衝突的原因了，兩個不一樣的對象計算出來的hashCode相等的原因。如果2個對象equals相等，但是hashcode不想等，那就說明這2個元素都能存進hashmap，但是很明顯hashmap裏麵的key是唯一的，直接就推翻了hashmap。
寫得比較粗糙，HashMap裏麵的很多細節都沒寫，主要是因為一來我們隻需要用HashMap就行了，二來是細節源碼裏麵都有，看一下就知道了。
最後更新：2017-07-18 20:34:21