HashMap是java中相當(dāng)重要的數(shù)據(jù)結(jié)構(gòu)，使用HashMap的場(chǎng)景非常之多，因此，了解HashMap實(shí)現(xiàn)的過(guò)程和原理，是非常有必要的，在一些面試中也會(huì)經(jīng)常被問(wèn)到。好了，我們趕緊來(lái)研究java內(nèi)部是怎么實(shí)現(xiàn)HashMap的吧！

  首先，我們都知道，數(shù)組的元素查找的效率是不錯(cuò)的，但是涉及到插入操作和刪除操作，效率低下，因?yàn)榭赡軙?huì)涉及到后續(xù)元素位置的遷移。而另外一個(gè)數(shù)據(jù)結(jié)構(gòu)鏈表則很好的解決了這個(gè)問(wèn)題，插入和刪除操作都只需要改變節(jié)點(diǎn)的指針就行，但是鏈表的檢索的效率就很低了，試想一下，要檢索的元素在鏈表的末尾，而我們只能從鏈表頭開始走完整個(gè)鏈表，才能檢索到這個(gè)元素。而Hash表能給我們帶來(lái)高效查詢，插入和刪除。它是怎么做到的呢？

  Hash表的實(shí)質(zhì)是構(gòu)造記錄的存儲(chǔ)位置和其對(duì)應(yīng)的關(guān)鍵字之間的映射函數(shù)f，關(guān)于Hash函數(shù)的構(gòu)造方法，主要有如下幾種：

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

    （2）平方取中法，將key的平方的中間幾位數(shù)作為得到的Hash地址。

    （3）除留余數(shù)法，將key除以某個(gè)數(shù)，得到的余數(shù)作為Hash地址。

還有一些方法我們?cè)诖司筒徽f(shuō)了。當(dāng)多個(gè)關(guān)鍵字經(jīng)過(guò)這個(gè)Hash函數(shù)的映射而得到同一個(gè)值的時(shí)候，就發(fā)生了Hash沖突。解決Hash沖突主要有兩種方法：

    （1）開放定址法：

                            

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

             當(dāng) di=1,2,3....,m-1時(shí),稱線性探測(cè)在散列；

             當(dāng)    時(shí)，稱為二次探測(cè)再散列。

    （2）鏈地址法：

             即將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一線性表中。假設(shè)某哈希函數(shù)產(chǎn)生的哈希地址在區(qū)間[0,m-1]上，則設(shè)立一個(gè)指針型向量 ChainHash[m];

             其每個(gè)分量的初始狀態(tài)都是空指針。凡是哈希地址為i的記錄都插入到頭指針為ChainHash[i]的鏈表中。在列表中的插入位置可以在表頭或表尾；也可以在中間，以保持同義詞在同一線性表中按關(guān)鍵字有序。

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

                           

Java中的HashMap的基本結(jié)構(gòu)就如上圖所示，豎著看是一個(gè)數(shù)組，橫著看就是多個(gè)鏈表。當(dāng)新建一個(gè)HashMap的時(shí)候，就初始化了一個(gè)數(shù)組：

1 /** 2  * The table, resized as necessary. Length MUST Always be a power of two. 
3  */  4 5 transient Entry[] table;

關(guān)于transient關(guān)鍵字，是為了使其修飾的對(duì)象不參與序列化，也就是說(shuō)，這個(gè)對(duì)象無(wú)法被持久化，這里用這個(gè)關(guān)鍵字是有原因的，由于HashCode()方法是一個(gè)本地方法(由java調(diào)用本地的外部函數(shù)執(zhí)行)，所以不同的虛擬機(jī)，對(duì)于相同的hashCode 產(chǎn)生的 Code 值可能是不一樣的，如果你使用默認(rèn)的序列化，那么反序列化后，元素的位置和之前的是保持一致的，可是由于 hashCode 的值不一樣了，那么定位函數(shù) indexOf()返回的元素下標(biāo)就會(huì)不同，這樣不是我們所想要的結(jié)果.舉個(gè)網(wǎng)上大神的例子：

        向HashMap存一個(gè)entry, key為 字符串"STRING", 在第一個(gè)java程序里, "STRING"的hashcode()為1, 存入第1號(hào)bucket; 在第二個(gè)java程序里, "STRING"的hashcode()有可能就是2, 存入第2號(hào)bucket. 如果用默認(rèn)的串行化(Entry[] table不用transient), 那么這個(gè)HashMap從第一個(gè)java程序里通過(guò)串行化導(dǎo)入第二個(gè)java程序后, 其內(nèi)存分布是一樣的，那么我取1號(hào)bucket能拿到“STRING”這個(gè)key,取2號(hào)bucket也能拿到相同的key，這是不合理的。

因此，HashMap這個(gè)entry數(shù)組是不可以串行化的。因此，HashMap自己實(shí)現(xiàn)了readObject和writeObject，在其中它只保存了bucket size，entry count（這兩個(gè)其實(shí)不是必需的，但有助于提高效率）和所有的key/value（這個(gè)才是必須的）。

這就是數(shù)組內(nèi)的鏈表：

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

1 static class Node<K,V> implements Map.Entry<K,V> {2         final int hash;3         final K key;4         V value;5         Node<K,V> next;   //持有的一個(gè)指向下一個(gè)元素的引用，構(gòu)成鏈表。6        ....7 }

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

 下面讓我們來(lái)看看Hash在put新元素時(shí)所做的操作：

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

 1 public V put(K key, V value) {   // HashMap允許存放null鍵和null值， 當(dāng)key為null時(shí)，調(diào)用putForNullKey方法，將value放置在數(shù)組第一個(gè)位置。   2     if (key == null)  
 3         return putForNullKey(value);   //null key 存放的總是數(shù)組的第一個(gè)元素中 4         int hash = hash(key.hashCode());   // 根據(jù)key的HashCode重新計(jì)算hash值 5     int i = indexFor(hash, table.length);  //通過(guò)hash值算出在對(duì)應(yīng)table中的索引（下標(biāo)）。  6     for (Entry<K,V> e = table[i]; e != null; e = e.next) {   // 如果 i 索引處的 Entry 不為 null，通過(guò)循環(huán)不斷遍歷 e 元素的下一個(gè)元素   7         Object k;  
 8         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {   //如果存在key相等的情形時(shí)，則用新的value值覆蓋老的value的值 9             V oldValue = e.value;  
10             e.value = value;  
11             e.recordAccess(this);  
12             return oldValue;  
13         }  
14     }  
15     modCount++;  // 如果i索引處的Entry為null，表明此處還沒(méi)有Entry。  16     addEntry(hash, key, value, i);   // 將key、value添加到i索引處。17     return null;  
18 }

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

怎么新加傳進(jìn)來(lái)的entry呢：

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

  addEntry( hash, K key, V value,  bucketIndex) {        Entry<K,V> e = table[bucketIndex];       table[bucketIndex] =  Entry<K,V>(hash, key, value, e);   //     (size++ >= threshold)      resize(2 *    }

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

 原來(lái)新加的entry都是加在了鏈表的頭端。

在取Entry的時(shí)候就非常簡(jiǎn)單了，如果key等于null，直接取數(shù)組的第一個(gè)元素，如果不是，先計(jì)算出key的hashcode找到下標(biāo)，再用key的equals方法判斷是否相等，如果相等，則返回對(duì)應(yīng)的entry，如果不相等，則返回null：

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

 1 public V get(Object key) {  
 2     if (key == null)  
 3         return getForNullKey();  
 4     int hash = hash(key.hashCode());  
 5     for (Entry<K,V> e = table[indexFor(hash, table.length)];  
 6         e != null;  
 7         e = e.next) {  
 8         Object k;  
 9         if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
10             return e.value;  
11     }  
12     return null;  
13 }

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

 關(guān)于HashMap的存儲(chǔ)原理就說(shuō)到這里啦，有什么錯(cuò)誤，請(qǐng)歡迎指正。

參考資料：http://zhangshixi.iteye.com/blog/672697

 HashMap是java中相當(dāng)重要的數(shù)據(jù)結(jié)構(gòu)，使用HashMap的場(chǎng)景非常之多，因此，了解HashMap實(shí)現(xiàn)的過(guò)程和原理，是非常有必要的，在一些面試中也會(huì)經(jīng)常被問(wèn)到。好了，我們趕緊來(lái)研究java內(nèi)部是怎么實(shí)現(xiàn)HashMap的吧！

  首先，我們都知道，數(shù)組的元素查找的效率是不錯(cuò)的，但是涉及到插入操作和刪除操作，效率低下，因?yàn)榭赡軙?huì)涉及到后續(xù)元素位置的遷移。而另外一個(gè)數(shù)據(jù)結(jié)構(gòu)鏈表則很好的解決了這個(gè)問(wèn)題，插入和刪除操作都只需要改變節(jié)點(diǎn)的指針就行，但是鏈表的檢索的效率就很低了，試想一下，要檢索的元素在鏈表的末尾，而我們只能從鏈表頭開始走完整個(gè)鏈表，才能檢索到這個(gè)元素。而Hash表能給我們帶來(lái)高效查詢，插入和刪除。它是怎么做到的呢？

  Hash表的實(shí)質(zhì)是構(gòu)造記錄的存儲(chǔ)位置和其對(duì)應(yīng)的關(guān)鍵字之間的映射函數(shù)f，關(guān)于Hash函數(shù)的構(gòu)造方法，主要有如下幾種：

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

    （2）平方取中法，將key的平方的中間幾位數(shù)作為得到的Hash地址。

    （3）除留余數(shù)法，將key除以某個(gè)數(shù)，得到的余數(shù)作為Hash地址。

還有一些方法我們?cè)诖司筒徽f(shuō)了。當(dāng)多個(gè)關(guān)鍵字經(jīng)過(guò)這個(gè)Hash函數(shù)的映射而得到同一個(gè)值的時(shí)候，就發(fā)生了Hash沖突。解決Hash沖突主要有兩種方法：

    （1）開放定址法：

                            

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

             當(dāng) di=1,2,3....,m-1時(shí),稱線性探測(cè)在散列；

             當(dāng)    時(shí)，稱為二次探測(cè)再散列。

    （2）鏈地址法：

             即將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一線性表中。假設(shè)某哈希函數(shù)產(chǎn)生的哈希地址在區(qū)間[0,m-1]上，則設(shè)立一個(gè)指針型向量 ChainHash[m];

             其每個(gè)分量的初始狀態(tài)都是空指針。凡是哈希地址為i的記錄都插入到頭指針為ChainHash[i]的鏈表中。在列表中的插入位置可以在表頭或表尾；也可以在中間，以保持同義詞在同一線性表中按關(guān)鍵字有序。

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

                           

Java中的HashMap的基本結(jié)構(gòu)就如上圖所示，豎著看是一個(gè)數(shù)組，橫著看就是多個(gè)鏈表。當(dāng)新建一個(gè)HashMap的時(shí)候，就初始化了一個(gè)數(shù)組：

1 /** 2  * The table, resized as necessary. Length MUST Always be a power of two. 
3  */  4 5 transient Entry[] table;

關(guān)于transient關(guān)鍵字，是為了使其修飾的對(duì)象不參與序列化，也就是說(shuō)，這個(gè)對(duì)象無(wú)法被持久化，這里用這個(gè)關(guān)鍵字是有原因的，由于HashCode()方法是一個(gè)本地方法(由java調(diào)用本地的外部函數(shù)執(zhí)行)，所以不同的虛擬機(jī)，對(duì)于相同的hashCode 產(chǎn)生的 Code 值可能是不一樣的，如果你使用默認(rèn)的序列化，那么反序列化后，元素的位置和之前的是保持一致的，可是由于 hashCode 的值不一樣了，那么定位函數(shù) indexOf()返回的元素下標(biāo)就會(huì)不同，這樣不是我們所想要的結(jié)果.舉個(gè)網(wǎng)上大神的例子：

        向HashMap存一個(gè)entry, key為 字符串"STRING", 在第一個(gè)java程序里, "STRING"的hashcode()為1, 存入第1號(hào)bucket; 在第二個(gè)java程序里, "STRING"的hashcode()有可能就是2, 存入第2號(hào)bucket. 如果用默認(rèn)的串行化(Entry[] table不用transient), 那么這個(gè)HashMap從第一個(gè)java程序里通過(guò)串行化導(dǎo)入第二個(gè)java程序后, 其內(nèi)存分布是一樣的，那么我取1號(hào)bucket能拿到“STRING”這個(gè)key,取2號(hào)bucket也能拿到相同的key，這是不合理的。

因此，HashMap這個(gè)entry數(shù)組是不可以串行化的。因此，HashMap自己實(shí)現(xiàn)了readObject和writeObject，在其中它只保存了bucket size，entry count（這兩個(gè)其實(shí)不是必需的，但有助于提高效率）和所有的key/value（這個(gè)才是必須的）。

這就是數(shù)組內(nèi)的鏈表：

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

1 static class Node<K,V> implements Map.Entry<K,V> {2         final int hash;3         final K key;4         V value;5         Node<K,V> next;   //持有的一個(gè)指向下一個(gè)元素的引用，構(gòu)成鏈表。6        ....7 }

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

 下面讓我們來(lái)看看Hash在put新元素時(shí)所做的操作：

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

 1 public V put(K key, V value) {   // HashMap允許存放null鍵和null值， 當(dāng)key為null時(shí)，調(diào)用putForNullKey方法，將value放置在數(shù)組第一個(gè)位置。   2     if (key == null)  
 3         return putForNullKey(value);   //null key 存放的總是數(shù)組的第一個(gè)元素中 4         int hash = hash(key.hashCode());   // 根據(jù)key的HashCode重新計(jì)算hash值 5     int i = indexFor(hash, table.length);  //通過(guò)hash值算出在對(duì)應(yīng)table中的索引（下標(biāo)）。  6     for (Entry<K,V> e = table[i]; e != null; e = e.next) {   // 如果 i 索引處的 Entry 不為 null，通過(guò)循環(huán)不斷遍歷 e 元素的下一個(gè)元素   7         Object k;  
 8         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {   //如果存在key相等的情形時(shí)，則用新的value值覆蓋老的value的值 9             V oldValue = e.value;  
10             e.value = value;  
11             e.recordAccess(this);  
12             return oldValue;  
13         }  
14     }  
15     modCount++;  // 如果i索引處的Entry為null，表明此處還沒(méi)有Entry。  16     addEntry(hash, key, value, i);   // 將key、value添加到i索引處。17     return null;  
18 }

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

怎么新加傳進(jìn)來(lái)的entry呢：

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

  addEntry( hash, K key, V value,  bucketIndex) {        Entry<K,V> e = table[bucketIndex];       table[bucketIndex] =  Entry<K,V>(hash, key, value, e);   //     (size++ >= threshold)      resize(2 *    }

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

 原來(lái)新加的entry都是加在了鏈表的頭端。

在取Entry的時(shí)候就非常簡(jiǎn)單了，如果key等于null，直接取數(shù)組的第一個(gè)元素，如果不是，先計(jì)算出key的hashcode找到下標(biāo)，再用key的equals方法判斷是否相等，如果相等，則返回對(duì)應(yīng)的entry，如果不相等，則返回null：

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

 1 public V get(Object key) {  
 2     if (key == null)  
 3         return getForNullKey();  
 4     int hash = hash(key.hashCode());  
 5     for (Entry<K,V> e = table[indexFor(hash, table.length)];  
 6         e != null;  
 7         e = e.next) {  
 8         Object k;  
 9         if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
10             return e.value;  
11     }  
12     return null;  
13 }

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

 關(guān)于HashMap的存儲(chǔ)原理就說(shuō)到這里啦，有什么錯(cuò)誤，請(qǐng)歡迎指正。

參考資料：http://zhangshixi.iteye.com/blog/672697

http://www.cnblogs.com/jy107600/p/7003777.html