Java中map內(nèi)部存儲(chǔ)方式解析

Map，即映射，也稱為 鍵值對(duì)，有一個(gè) Key， 一個(gè) Value 。

比如 Groovy 語言中，  def  map = ['name' : 'liudehua', 'age' : 50 ] ，則 map[ 'name' ]  的值是 'liudehua'。
那么 Map 內(nèi)部存儲(chǔ)是怎么實(shí)現(xiàn)的呢？   下面慢慢講解.

一、 使用 拉鏈?zhǔn)酱鎯?chǔ)

這個(gè)以 Java 中的 HashMap 為例進(jìn)行講解。   HashMap 的內(nèi)部有個(gè)數(shù)組 Entry[]  table， 這個(gè)數(shù)組就是存放數(shù)據(jù)的。

Entry 類的定義大致是 :

class Entry {
Object key
Object value
Entry next;
}

所以， Entry[]  table  的每個(gè)元素都是一個(gè)鏈表，即 HashMap 的內(nèi)部存儲(chǔ)是 數(shù)組 + 鏈表，即拉鏈?zhǔn)酱鎯?chǔ)。

當(dāng)往 HaspMap 中 put(key,  value) 數(shù)據(jù)時(shí)，先進(jìn)行  key.hashCode()  &  (table.length() - 1) ，得到一個(gè)小于 table.length() 的值， 稱為 index， 則這個(gè)新的 Entry 就屬于 table[index] 這個(gè)鏈表了 ( 如果鏈表還不存在，則把這個(gè)新的 Entry 作為鏈表的頭部了 )；  然后開始從前往后遍歷  table[index] 這個(gè)鏈表，如果 key.equals( entry.key )， 那么表示這個(gè) key 已經(jīng)有了舊值，則替換 value 的值即可；

否則，把這個(gè)新的 Entry 插入到 table[index] 鏈表的最前面.

以上就是 HashMap 的存儲(chǔ)方式介紹了， 而且可以知道，作為 HashMap 的 Key， 它的 hashCode() 和 equals() 方法都被使用了

二、數(shù)組存儲(chǔ)

1.分散的數(shù)組存儲(chǔ)

這個(gè)以 ThreadLocal  和 ThreadLocal.Values  類為例進(jìn)行講解。 Values 類里面有兩個(gè)變量， Object[]  table, 和 mask ， table 就是存儲(chǔ)數(shù)據(jù)的數(shù)組了，table 的長度是 2 的倍數(shù) ，  mask 的值就是  table.length - 1 ;  這一點(diǎn)和 HashMap 的內(nèi)部存儲(chǔ)很像。  不過 table 中的每個(gè)元素就不是鏈表了。

當(dāng)往  Values 中進(jìn)行 put(key, value) 時(shí)，先進(jìn)行 key.hashCode & mask ，得到一個(gè)小于 table.length 的值，稱為 index (與上面的 HashMap 好像，哈哈), 然后去檢查 table[index] 的值，如果不存在，則在 table[index] 處放入 key， table[index + 1] 處放入 value; 如果已經(jīng)存在了，且 key.equals( oldKey ) 不成立，即發(fā)生了沖突，那么 index = index + 2 ( 此處是 + 2，因?yàn)?key ，value 兩個(gè)是挨著放的，一個(gè)元素占倆坑 ) ; 往下一地方找找，如果再?zèng)_突，再找，直到找到一個(gè)可插入的地方，把 table[index] = key, table[index + 1] = value; 

有兩處需要注意:

key.hashCode() 必須是 2 的倍數(shù), 否則 index 的值有可能為奇數(shù)，如此就可能發(fā)生沖突了.  可參考 ThreadLocal.hash 這個(gè)成員變量

table 內(nèi)部的數(shù)據(jù)是分散著存儲(chǔ)的.

2.連續(xù)的數(shù)組存儲(chǔ)

這個(gè)以 Android 中新增的 ArrayMap 為例進(jìn)行分析( 據(jù)說沒 ArrayMap 是用來替換 HashMap 的哈 ),  ArrayMap 中有兩個(gè)主要變量， int[]  mHashes, Object[]  mArrays.

mHashes 主要是存放 key 的 hash 值的， mArrays 是用來存放數(shù)據(jù)的，它也是奇數(shù)存放 key ，偶數(shù)存放 value ， key 和 value 順序排列( 這個(gè)和 TheadLocal.value 中的 table 存儲(chǔ)方式很像 )。  mArrays 的長度是 mHashes 的 2 倍，畢竟 mArrays 是 key, value 都要存嘛~

mHashes 中存放 key 的 hash 值，是從小到大排列的，如果有多個(gè) key 的 hash 值有一樣的，那么就挨著排列

當(dāng)往 ArrayMap 中進(jìn)行 put(key, value) 時(shí)，先 int hash = key.hashCode, 然后通過二分查找在 mHashes 中查找 hash 的位置( 如果里面有，就返回，如果無，就先找到最接近的位置，然后進(jìn)行取反操作并返回 )  index，如果 index > 0 ，那么再去 mArrays 中 2 * index 處獲取 key 值，比對(duì)兩個(gè) key 是否 equals(), 如果不相等，那么再分別向上、向下查找附近相同 hash 值的 key ，看是否有 equals() 的 key, 若有，則替換，若無，則插入;    如果 index < 0 ，表示之前沒有相等 hash 的 key 插入過，那么 index = ~index( 再次取反，就是個(gè)正數(shù)了，代辦要插入的位置)， 再在 mHashes 的 index 處插入 hash， 在 mArrays 的 2 * index 處插入 key, 在 (2 * index ) + 1 處，插入 value .

注意：

mHashes 和 mArrays 在插入新數(shù)據(jù)時(shí)，都需要把插入位置后面的數(shù)據(jù)向后移動(dòng)一個(gè)單位，這個(gè)對(duì)于頻繁插入、刪除的動(dòng)作來說消耗比較大.

key 的 hash 大小決定了插入的順序

3.以數(shù)字為 key 的數(shù)組存儲(chǔ)

這類的 map 比較特殊，key 是數(shù)字類型。  這個(gè)以 Android 中新增的 SparseArray 進(jìn)行分析。 SparseArray 中有兩個(gè)主要變量， int[]  mKeys  和  Object[]  mValues ， mKeys 是存放 key 的，是個(gè)有序數(shù)組，從小到大排列；  mValues 是與 mKeys 一一對(duì)應(yīng)的 value 值集合.   mKeys 和 mValues 的長度是相等的。

當(dāng)往  SparseArray 中 put(key, value) 時(shí)，先用二分查找在 mKeys 中查找 key 所在的位置 (如果找到，返回； 如果沒有找到，則找到它應(yīng)該插入的位置，取反并返回) ，記為 index， index > 0 ，則直接在 mValues[index] 處替換 value; 如果 index < 0 ，則 index = ~index， 即取反， 然后在 mKeys 的 index 處插入 key ， 在 mValues[index] 處插入 value ，之前的數(shù)據(jù)自 index 處后移一個(gè)單位。

注意:

mKeys 和 mArrays 的數(shù)據(jù)插入時(shí)，都是要進(jìn)行數(shù)據(jù)移動(dòng)的，對(duì)頻繁插入、刪除的 map 來說消耗很大.
最后了，對(duì)它們的優(yōu)缺點(diǎn)做些對(duì)比。

HashMap : 內(nèi)存占用較大，增、刪的效率較高，改、查的效率一般

ThreadLocal.Values :  內(nèi)存占用一般，當(dāng)數(shù)據(jù)量比較小時(shí)，增刪改查的效率高；數(shù)據(jù)量大時(shí)，增刪改查效率一般

ArrayMap: 內(nèi)存占用較小，改、查的效率高，增、刪的效率較低

SparseArray : 內(nèi)存占用較小，改、查的效率高，增、刪的效率低，且主鍵是數(shù)字

總結(jié)

我們不評(píng)判哪種存儲(chǔ)方式好，一切都要以實(shí)際情況實(shí)際分析，找出最符合的那種存儲(chǔ)，哈哈~。希望對(duì)大家有所幫助。感興趣的朋友可以參閱：Javabean和map相互轉(zhuǎn)化方法代碼示例  淺談對(duì)象與Map相互轉(zhuǎn)化  Struts2 使用OGNL遍歷map方法詳解等。感謝大家對(duì)本站的支持。