IdentityHashMap 從它的名字上可以看出來用於表示唯一的 HashMap,但是分析了其源碼,發現其數據結構與 HashMap 使用的數據結構完全不同。
01、摘要
在集合系列的第一章,咱們瞭解到,Map 的實現類有 HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties 等等。
應該有很多人不知道 IdentityHashMap 的存在,其中不乏工作很多年的 Java 開發者,本文主要從數據結構和算法層面,探討 IdentityHashMap 的實現。
02、簡介
IdentityHashMap 的數據結構很簡單,底層實際就是一個 Object 數組,但是在存儲上並沒有使用鏈表來存儲,而是將 K 和 V 都存放在 Object 數組上。
當添加元素的時候,會根據 Key 計算得到散列位置,如果發現該位置上已經有改元素,直接進行新值替換;如果沒有,直接進行存放。當元素個數達到一定閾值時,Object 數組會自動進行擴容處理。
打開 IdentityHashMap 的源碼,可以看到 IdentityHashMap 繼承了 AbstractMap 抽象類,實現了 Map 接口、可序列化接口、可克隆接口。
<code>public class IdentityHashMapextends AbstractMap /<code>implements Map , java.io.Serializable, Cloneable{ /**默認容量大小*/ private static final int DEFAULT_CAPACITY = 32; /**最小容量*/ private static final int MINIMUM_CAPACITY = 4; /**最大容量*/ private static final int MAXIMUM_CAPACITY = 1 << 29; /**用於存儲實際元素的表*/ transient Object[] table; /**數組大小*/ int size; /**對Map進行結構性修改的次數*/ transient int modCount; /**key為null所對應的值*/ static final Object NULL_KEY = new Object(); ......}
可以看到類的底層,使用了一個 Object 數組來存放元素;在對象初始化時,IdentityHashMap 容量大小為64;
<code>public IdentityHashMap() { //調用初始化方法 init(DEFAULT_CAPACITY);}/<code>
<code>private void init(int initCapacity) { //數組大小默認為初始化容量的2倍 table = new Object[2 * initCapacity];}/<code>
03、常用方法介紹
3.1、put方法
put 方法是將指定的 key, value 對添加到 map 裡。該方法首先會對map做一次查找,通過==判斷是否存在key,如果有,則將舊value返回,將新value覆蓋舊value;如果沒有,直接插入,數組長度+1,返回null。
源碼如下:
<code>public V put(K key, V value) { //判斷key是否為空,如果為空,初始化一個Object為key final Object k = maskNull(key); retryAfterResize: for (;;) { final Object[] tab = table; final int len = tab.length; //通過key、length獲取數組小編 int i = hash(k, len); //循環遍歷是否存在指定的key for (Object item; (item = tab[i]) != null; i = nextKeyIndex(i, len)) { //通過==判斷,是否數組中是否存在key if (item == k) { V oldValue = (V) tab[i + 1]; //新value覆蓋舊value tab[i + 1] = value; //返回舊value return oldValue; } } //數組長度 +1 final int s = size + 1; //判斷是否需要擴容 if (s + (s << 1) > len && resize(len)) continue retryAfterResize; //更新修改次數 modCount++; //將k加入數組 tab[i] = k; //將value加入數組 tab[i + 1] = value; size = s; return null; }}/<code>
maskNull 函數,判斷 key 是否為空
<code>private static Object maskNull(Object key) { return (key == null ? NULL_KEY : key);}/<code>
hash 函數,通過 key 獲取 hash 值,結合數組長度通過位運算獲取數組散列下標
<code>private static int hash(Object x, int length) { int h = System.identityHashCode(x); // Multiply by -127, and left-shift to use least bit as part of hash return ((h << 1) - (h << 8)) & (length - 1);}/<code>
nextKeyIndex 函數,通過 hash 函數計算得到的數組散列下標,進行加2;因為一個 key、value 都存放在數組中,所以一個 map 對象佔用兩個數組下標,所以加2。
<code>private static int nextKeyIndex(int i, int len) { return (i + 2 < len ? i + 2 : 0);}/<code>
resize 函數,通過數組長度,進行擴容處理,擴容之後的長度為當前長度的2倍
<code>private boolean resize(int newCapacity) { //擴容後的數組長度,為當前數組長度的2倍 int newLength = newCapacity * 2; Object[] oldTable = table; int oldLength = oldTable.length; if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further if (size == MAXIMUM_CAPACITY - 1) throw new IllegalStateException("Capacity exhausted."); return false; } if (oldLength >= newLength) return false; Object[] newTable = new Object[newLength]; //將舊數組內容轉移到新數組 for (int j = 0; j < oldLength; j += 2) { Object key = oldTable[j]; if (key != null) { Object value = oldTable[j+1]; oldTable[j] = null; oldTable[j+1] = null; int i = hash(key, newLength); while (newTable[i] != null) i = nextKeyIndex(i, newLength); newTable[i] = key; newTable[i + 1] = value; } } table = newTable; return true;}/<code>
3.2、get方法
get 方法根據指定的 key 值返回對應的 value。同樣的,該方法會循環遍歷數組,通過==判斷是否存在key,如果有,直接返回value,因為 key、value 是相鄰的存儲在數組中,所以直接在當前數組下標+1,即可獲取 value;如果沒有找到,直接返回null。
值得注意的地方是,在循環遍歷中,是通過==判斷當前元素是否與key相同,如果相同,則返回value。咱們都知道,在 java 中,==對於對象類型參數,判斷的是引用地址,確切的說,是堆內存地址,所以,這裡判斷的是key的引用地址是否相同,如果相同,則返回對應的 value;如果不相同,則返回null。
源碼如下:
<code>public V get(Object key) { Object k = maskNull(key); Object[] tab = table; int len = tab.length; int i = hash(k, len); //循環遍歷數組,直到找到key或者,數組為空為值 while (true) { Object item = tab[i]; //通過==判斷,當前數組元素與key相同 if (item == k) return (V) tab[i + 1]; //數組為空 if (item == null) return null; i = nextKeyIndex(i, len); }}/<code>
3.3、remove方法
remove 的作用是通過 key 刪除對應的元素。該方法會循環遍歷數組,通過==判斷是否存在key,如果有,直接將key、value設置為null,對數組進行重新排列,返回舊 value。
源碼如下:
<code>public V remove(Object key) { Object k = maskNull(key); Object[] tab = table; int len = tab.length; int i = hash(k, len); while (true) { Object item = tab[i]; if (item == k) { modCount++; //數組長度減1 size--; V oldValue = (V) tab[i + 1]; //將key、value設置為null tab[i + 1] = null; tab[i] = null; //刪除該元素後,需要把原來有衝突往後移的元素移到前面來 closeDeletion(i); return oldValue; } if (item == null) return null; i = nextKeyIndex(i, len); }}/<code>
closeDeletion 函數,刪除該元素後,需要把原來有衝突往後移的元素移到前面來,對數組進行重寫排列;
<code>private void closeDeletion(int d) { // Adapted from Knuth Section 6.4 Algorithm R Object[] tab = table; int len = tab.length; Object item; for (int i = nextKeyIndex(d, len); (item = tab[i]) != null; i = nextKeyIndex(i, len) ) { int r = hash(item, len); if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) { tab[d] = item; tab[d + 1] = tab[i + 1]; tab[i] = null; tab[i + 1] = null; d = i; } }}/<code>
04、總結
- IdentityHashMap 的實現不同於HashMap,雖然也是數組,不過IdentityHashMap中沒有用到鏈表,解決衝突的方式是計算下一個有效索引,並且將數據key和value緊挨著存在map中,即table[i]=key、table[i+1]=value;
- IdentityHashMap 允許key、value都為null,當key為null的時候,默認會初始化一個Object對象作為key;
- IdentityHashMap在保存、刪除、查詢數據的時候,以key為索引,通過==來判斷數組中元素是否與key相同,本質判斷的是對象的引用地址,如果引用地址相同,那麼在插入的時候,會將value值進行替換;
IdentityHashMap 測試例子:
<code>public static void main(String[] args) { Map<string> identityMaps = new IdentityHashMap<string>(); identityMaps.put(new String("aa"), "aa"); identityMaps.put(new String("aa"), "bb"); identityMaps.put(new String("aa"), "cc"); identityMaps.put(new String("aa"), "cc"); //輸出添加的元素 System.out.println("數組長度:"+identityMaps.size() + ",輸出結果:" + identityMaps);}/<string>/<string>/<code>
輸出結果:
<code>數組長度:4,輸出結果:{aa=aa, aa=cc, aa=bb, aa=cc}/<code>
儘管key的內容是一樣的,但是key的堆地址都不一樣,所以在插入的時候,插入了4條記錄。
05、參考
1、JDK1.7&JDK1.8 源碼
2、簡書 - 騎著烏龜去看海 - IdentityHashMap源碼解析
3、博客園 - leesf - IdentityHashMap源碼解析
閱讀更多 科技伍小黑 的文章