HashMap的存儲原理

 HashMap是java中相當重要的資料結構，使用HashMap的場景非常之多，是以，了解HashMap實作的過程和原理，是非常有必要的，在一些面試中也會經常被問到。好了，我們趕緊來研究java内部是怎麼實作HashMap的吧！

  首先，我們都知道，數組的元素查找的效率是不錯的，但是涉及到插入操作和删除操作，效率低下，因為可能會涉及到後續元素位置的遷移。而另外一個資料結構連結清單則很好的解決了這個問題，插入和删除操作都隻需要改變節點的指針就行，但是連結清單的檢索的效率就很低了，試想一下，要檢索的元素在連結清單的末尾，而我們隻能從連結清單頭開始走完整個連結清單，才能檢索到這個元素。而Hash表能給我們帶來高效查詢，插入和删除。它是怎麼做到的呢？

  Hash表的實質是構造記錄的存儲位置和其對應的關鍵字之間的映射函數f，關于Hash函數的構造方法，主要有如下幾種：

    （1）直接定址法，取關鍵字的某個線性函數作為Hash函數即Hash(key) = a*key+b。這種方法很少使用，雖然不會發生沖突，但是當key非常多的時候，整張Hash表也會非常大，畢竟是一一映射的。

    （2）平方取中法，将key的平方的中間幾位數作為得到的Hash位址。

    （3）除留餘數法，将key除以某個數，得到的餘數作為Hash位址。

還有一些方法我們在此就不說了。當多個關鍵字經過這個Hash函數的映射而得到同一個值的時候，就發生了Hash沖突。解決Hash沖突主要有兩種方法：

    （1）開放定址法：

             其中i=1，2，3。。。。，k(k<=m-1),H(key)為哈希函數，m為哈希表表長，di為增量序列，可能有下列2種情況：

             當 di=1,2,3....,m-1時,稱線性探測在散列；

             當    時，稱為二次探測再散列。

    （2）鍊位址法：

             即将所有關鍵字為同義詞的記錄存儲在同一線性表中。假設某哈希函數産生的哈希位址在區間[0,m-1]上，則設立一個指針型向量 ChainHash[m];

             其每個分量的初始狀态都是空指針。凡是哈希位址為i的記錄都插入到頭指針為ChainHash[i]的連結清單中。在清單中的插入位置可以在表頭或表尾；也可以在中間，以保持同義詞在同一線性表中按關鍵字有序。

             例如：已知一組關鍵字為（19，14，23，01，68，20，84，27，55，11，10，79），則按哈希函數H(key)=key MOD 13 和鍊位址法處理沖突構造所得的哈希表，如下圖所示：

Java中的HashMap的基本結構就如上圖所示，豎着看是一個數組，橫着看就是多個連結清單。當建立一個HashMap的時候，就初始化了一個數組：

關于transient關鍵字，是為了使其修飾的對象不參與序列化，也就是說，這個對象無法被持久化，這裡用這個關鍵字是有原因的，由于HashCode()方法是一個本地方法(由java調用本地的外部函數執行)，是以不同的虛拟機，對于相同的hashCode 産生的 Code 值可能是不一樣的，如果你使用預設的序列化，那麼反序列化後，元素的位置和之前的是保持一緻的，可是由于 hashCode 的值不一樣了，那麼定位函數 indexOf()傳回的元素下标就會不同，這樣不是我們所想要的結果.舉個網上大神的例子：

        向HashMap存一個entry, key為 字元串"STRING", 在第一個java程式裡, "STRING"的hashcode()為1, 存入第1号bucket; 在第二個java程式裡, "STRING"的hashcode()有可能就是2, 存入第2号bucket. 如果用預設的串行化(Entry[] table不用transient), 那麼這個HashMap從第一個java程式裡通過串行化導入第二個java程式後, 其記憶體分布是一樣的，那麼我取1号bucket能拿到“STRING”這個key,取2号bucket也能拿到相同的key，這是不合理的。

是以，HashMap這個entry數組是不可以串行化的。是以，HashMap自己實作了readObject和writeObject，在其中它隻儲存了bucket size，entry count（這兩個其實不是必需的，但有助于提高效率）和所有的key/value（這個才是必須的）。

這就是數組内的連結清單：

 下面讓我們來看看Hash在put新元素時所做的操作：

怎麼新加傳進來的entry呢：

 原來新加的entry都是加在了連結清單的頭端。

在取Entry的時候就非常簡單了，如果key等于null，直接取數組的第一個元素，如果不是，先計算出key的hashcode找到下标，再用key的equals方法判斷是否相等，如果相等，則傳回對應的entry，如果不相等，則傳回null：

本文轉自xsster51CTO部落格，原文連結：http://blog.51cto.com/12945177/1948532 ，如需轉載請自行聯系原作者