深入理解Java中的HashMap的實現機制?

如果任何人讓我描述一下HashMap的工作機制的話，我就簡單的回答：“基於Hash的規則”。這句話非常簡單，但是要理解這句話之前，首先我們得了解什麼是雜湊，不是麼？

什麼是雜湊 雜湊簡單的說就是對變數/物件的屬性應用某種演算法後得到的一個唯一的串，用這個串來確定變數/物件的唯一性。一個正確的雜湊函式必須遵守這個準則。

當雜湊函式應用在相同的物件或者equal的物件的時候，每次執行都應該返回相同的值。換句話說，兩個相等的物件應該有相同的hashcode。

注：所有Java物件都從Object類繼承了一個預設的hashCode()方法。這個方法將物件在記憶體中的地址作為整數返回，這是一個很好的hash實現，他確保了不同的物件擁有不同的hashcode。

關於Entry類的一點介紹一個map的定義是：一個對映鍵（key）到值（value）的物件。非常簡單對吧。

所以，在HashMap中一定有一定的機制來儲存這些鍵值對。使得，HashMap有一個 內部類Entry，看起來像這樣。

工具/原料

Java

方法/步驟

static class Entry implements // www.jbyuan.comMap.Entry { final K key; V value; Entry next; final int hash; ...//More code goes here}

當然，Entry類有屬性用來儲存鍵值對對映。key被final標記，除了key和value ，我們還能看到兩個變數next和hash。接下來我們試著理解這些變數的含義。

put()方法實際上做了什麼再進一步看put方法的實現之前，我們有必要看一看Entry例項在陣列中的儲存， HashMap中是這樣定義的：

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 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.