如果任何人讓我描述一下HashMap的工作機制的話，我就簡單的回答：“基于Hash的規則”。這句話非常簡單，但是要理解這句話之前，首先我們得了解什么是哈希，不是么？
什么是哈希
哈希簡單的說就是對變量/對象的屬性應用某種算法后得到的一個唯一的串，用這個串來確定變量/對象的唯一性。一個正確的哈希函數必須遵守這個準則。
當哈希函數應用在相同的對象或者equal的對象的時候，每次執行都應該返回相同的值。換句話說，兩個相等的對象應該有相同的hashcode。
注：所有Java對象都從Object類繼承了一個默認的hashCode()方法。這個方法將對象在內存中的地址作為整數返回，這是一個很好的hash實現，他確保了不同的對象擁有不同的hashcode。
關于Entry類的一點介紹
一個map的定義是：一個映射鍵（key）到值（value）的對象。非常簡單對吧。
所以，在HashMap中一定有一定的機制來存儲這些鍵值對。使得，HashMap有一個 內部類Entry，看起來像這樣。
|
1
2
3
4
5
6
7
8
9
10
|
static class Entry<K,V> implements Map.Entry<K,V>{ final K key; V value; Entry<K,V> next; final int hash; ...//More code goes here} |
當然，Entry類有屬性用來存儲鍵值對映射。key被final標記，除了key和value ，我們還能看到兩個變量next和hash。接下來我們試著理解這些變量的含義。
put()方法實際上做了什么
再進一步看put方法的實現之前，我們有必要看一看Entry實例在數組中的存儲， HashMap中是這樣定義的：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
/** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry[] table;現在再來看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) {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;}} modCount++;addEntry(hash, key, value, i);return null;} |
讓我們一步一步的看
首先，檢查key是否為null，如果key是null值被存在table[0]的位置，因為null 的hashcode始終為0
接下來，通過key的hashCode()方法計算了這個key的hash值，這個hash值被用來 計算存儲Entry對象的數組中的位置。JDK的設計者假設會有一些人可能寫出非常差的hashCode()方法，會出現一些 非常大或者非常小的hash值。為了解決這個問題，他們引入了另外一個hash函數，接受對象的hashCode()，并轉換 到適合數組的容量大小。
接著是indexFor(hash,table,length)方法，這個方法計算了entry對象存儲 的準確位置。
接下來就是主要的部分，我們都知道兩個不相等的對象可能擁有過相同的 hashCode值，兩個不同的對象是怎么存儲在相同的位置[叫做bucket]呢？
答案是LinkedList。如果你記得，Entry類有一個next變量，這個變量總是指向 鏈中的下一個變量，這完全符合鏈表的特點。
所以，在發生碰撞的時候，entry對象會被以鏈表的形式存儲起來，當一個Entry 對象需要被存儲的時候，hashmap檢查該位置是否已近有了一個entry對象，如果沒有就存在那里，如果有了就檢查 她的next屬性，如果是空，當前的entry對象就作為已經存儲的entry對象的下一個節點，依次類推。
如果我們給已經存在的key存入另一個value會怎么樣的？邏輯上，舊的值將被替 換掉。在檢測了Entry對象的存儲位置后，hashmap將會遍歷那個位置的entry鏈表，對每一個entry調用equals方法 ，這個鏈表中的所有對象都具有相同的hashCode()而equals方法都不等。如果發現equals方法有相等的就執行替換 。
在這種方式下HashMap就能保證key的唯一性。
get方法的工作機制
現在我們已經了解了HashMap中存儲鍵值對的機制。下一個問題是：怎樣從一個 HashMap中查詢結果。
其實邏輯跟put是一樣的，如果傳入的key有匹配就將該位置的value返回，如果 沒有就返回null.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
/*** 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();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;} |
上面的代碼看起來跟put()方法很像，除了if (e.hash == hash && ((k = e.key) == key || key.equals(k)))。
注意點
- 存儲Entry對象的數據結構是一個叫做Entry類型的table數組。
- 數組中一個特定的索引位置稱為bucket,因為它可以容納一個LinkedList 的第一個元素的對象。
- Key對象的hashCode()需要用來計算Entry對象的存儲位置。
- Key對象的equals()方法需要用來維持Map中對象的唯一性。
- get()和put()方法跟Value對象的hashCode和equals方法無關。
- null的hashCode總是0，這樣的Entry對象總是被存儲在數組的第一個位置
