Java8 IdentityHashMap 源码分析
在講這個數(shù)據(jù)結(jié)構(gòu)之前，我們先來看一段代碼：
public static void main(String[] args) {IdentityHashMap<String, Integer> map = new IdentityHashMap<>();map.put("Hello " + "World", 1);map.put("Hello World", 2);map.put(new String("Hello World"), 3);System.out.println(map);}沒有仔細了解過 IdentityHashMap 話，很多人應該都認為會輸出 {Hello World=3}，但實際上輸出的是 {Hello World=3, Hello World=2}。原因在于這個類是通過對象引用來判斷 key 是否相同的。我們以添加鍵值對為例，對判斷鍵是否存在的情況拿出來對比下大家就知道為什么了：
- IdentityHashMap：item == k
- HashMap：p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
一、IdentityHashMap 概述
上面我們說了 IdentityHashMap 是通過引用相等判斷是否為同一個 key 的，除了這個區(qū)別外，IdentityHashMap 與 HashMap 最大的一個區(qū)別在于其內(nèi)部數(shù)據(jù)結(jié)構(gòu)，IdentityHashMap 底層實現(xiàn)是一個數(shù)組，意味著 key 與 value 都存儲在數(shù)組中，因為其實現(xiàn)沒有鏈表，因此是通過線性探測的方式來解決哈希沖突。
下面是一個其內(nèi)部原理圖：
因為它本身還是一個存儲鍵值對的數(shù)據(jù)結(jié)構(gòu)，那知識點無外乎就是哈希函數(shù)，哈希沖突，擴容等知識點，下面我們就針對這些問題來分析一下內(nèi)部源碼。
二、IdentityHashMap 源碼分析
2.1 內(nèi)部屬性
// 存儲鍵值對的哈希表數(shù)組transient Object[] table;// 存儲的鍵值對個數(shù)int size;// 擴容閾值private transient int threshold;與 HashMap 不同的是 IdentityHashMap 并沒有加載因子這個概念，因為這個加載因子是固定值，下面我們在構(gòu)造函數(shù)中會看到。
2.2 構(gòu)造函數(shù)
默認的構(gòu)造函數(shù)：
public IdentityHashMap() {init(DEFAULT_CAPACITY);}DEFAULT_CAPACITY 表示默認情況下的數(shù)組初始化大小，這個值是 32。默認的構(gòu)造函數(shù)中調(diào)用了一個 init 方法，我們接著看這個方法。
private void init(int initCapacity) {// 指定擴容閾值為初始化容量的 2/3threshold = (initCapacity * 2)/3;// 初始化哈希表數(shù)組為指定容量的 2 倍，一般空間存儲 key 一半空間存儲 valuetable = new Object[2 * initCapacity];}init 方法中初始化了擴容閾值與哈希表大小，在計算初始值的時候都會先 * 2，就是因為它本身特殊的數(shù)組結(jié)構(gòu)導致的。
IdentityHashMap 還提供了一個可以指定默認初始化大小的構(gòu)造函數(shù)，我們知道 HashMap 在指定默認初始化大小時會取大于等于當前初始化大小的第一個 2 的冪作為哈希表大小。
但是 IdentityHashMap 內(nèi)部并不是這樣，IdentityHashMap 在計算哈希表容量時，計算出的值也是 2 的冪，但是這個值并不是嚴格意義上為第一個大于等于初始值的 2 的冪，有時候會大于這個值，為什么會這樣呢？其實這還是和它的底層數(shù)據(jù)結(jié)構(gòu)有關，因為 key 與 value 都公用一個數(shù)組，為了能存儲更多的鍵值對，往往會把哈希表容量計算的大一些。有興趣的可以看一下，這里就不貼出來了。
2.3 hash 方法
我們來想一個問題：因為 key 與 value 都存在一個數(shù)組中，那么 key 與 value 的位置要怎么存儲呢，奇數(shù)位置可以放 key 嗎？答案是不能的，如果奇數(shù)位置上放 key 的話，那 0 位置上放的就是 value，這樣做是不合理的。為了保證正確性，偶數(shù)位置上放的一定是 key 然后奇數(shù)位置上放 value。下面我們就來看一下是不是這樣的。
private static int hash(Object x, int length) {// 此方法不管你是否重寫了 hashCode 方法都會返回對象默認的哈希值// 即使重寫了 hashCode 也不會調(diào)用重寫的 hashCode 方法int h = System.identityHashCode(x);// Multiply by -127, and left-shift to use least bit as part of hashreturn ((h << 1) - (h << 8)) & (length - 1);}我們來分析一下 ((h << 1) - (h << 8)) & (length - 1) 的運算，首先哈希值左移一位，保證是一個偶數(shù)，減去一個左移八位的值也是一個偶數(shù)，然后與上全 1 的二進制，計算出的還是一個偶數(shù)，這樣就能保證每個 key 計算出的索引一定是個偶數(shù)，然后 value 放在索引值下一個位置上就可以了。
2.4 put 方法
public V put(K key, V value) {// key == null ? new Object() : key// 如果 key 為 null 那么用一個內(nèi)部的 Object 對象來代替 nullObject k = maskNull(key);// 獲取哈希表與哈希表大小Object[] tab = table;int len = tab.length;// 計算哈希值，len 用于計算在數(shù)組中的索引int i = hash(k, len);Object item;// 這里分為兩種情況，哈希沖突與非沖突，當沖突時會線性探測尋找下一個可用的位置while ((item = tab[i]) != null) {// key 引用相同，值覆蓋，返回老得值if (item == k) {// 獲取老的 valueV oldValue = (V) tab[i + 1];// 更新值tab[i + 1] = value;return oldValue;}// 哈希沖突，計算下一個 key 角標i = nextKeyIndex(i, len);}modCount++;// 設置 key 與 valuetab[i] = k;tab[i + 1] = value;// 判斷是否需要擴容，此時的 len 的大小為 capacity 的兩倍，可以在構(gòu)造函數(shù)中查看if (++size >= threshold)resize(len);return null;}添加過程還是比較簡單的，根據(jù) key 的哈希值計算在數(shù)組中的索引（一定是個偶數(shù)），然后判斷當前數(shù)組位置上是否已經(jīng)存在了 key，當然存在也分為兩種情況，一種是 key 引用相同，另外一種情況是 key 引用不同，不同時意味著哈希沖突，因此就要找下一個可用的位置來存儲鍵值對，最后添加鍵值對后判斷是否需要擴容。
當哈希沖突時調(diào)用了 nextKeyIndex 方法來尋找下一個可用的位置，下面我們接著看下這個方法。
private static int nextKeyIndex(int i, int len) {return (i + 2 < len ? i + 2 : 0);}為什么 i 要加 2 呢，其實還是為了保證 key 在偶數(shù)索引上，如果一直找到數(shù)組尾部還沒有找到可用的位置，那么會從頭開始繼續(xù)尋找，可以理解為一個環(huán)狀的數(shù)組，這點和 ThreadLocalMap 有點相似，有興趣的可以自己看下 ThreadLocal 的源碼。
2.5 resize 方法
在添加鍵值對過后會判斷當前數(shù)組中的鍵值對個數(shù)是否大于等于擴容的閾值，如果大于等于那么久對數(shù)組進行擴容，下面是擴容的方法。
private void resize(int newCapacity) {// 新數(shù)組容量為原來的 2 倍int newLength = newCapacity * 2;Object[] oldTable = table;int oldLength = oldTable.length;// 判斷不能無限擴容if (oldLength == 2*MAXIMUM_CAPACITY) { // can't expand any furtherif (threshold == MAXIMUM_CAPACITY-1)throw new IllegalStateException("Capacity exhausted.");threshold = MAXIMUM_CAPACITY-1; // Gigantic map!return;}if (oldLength >= newLength)return;Object[] newTable = new Object[newLength];/** newLength / 3 = （newCapacity * 2）/3* 只不過換了種表現(xiàn)形式*/threshold = newLength / 3;// 鍵值對 rehashfor (int j = 0; j < oldLength; j += 2) {Object key = oldTable[j];if (key != null) {Object value = oldTable[j+1];// 下次 GC 回收oldTable[j] = null;oldTable[j+1] = null;// 根據(jù) key 計算桶位置int i = hash(key, newLength);// 從當前桶位置向后遍歷，找出空位置，存放當前鍵值對while (newTable[i] != null)i = nextKeyIndex(i, newLength);// key value 賦值newTable[i] = key;newTable[i + 1] = value;}}// 重置 tabletable = newTable;}擴容的過程并不復雜，首先對哈希表數(shù)據(jù)進行擴容，然后重置擴容閾值，接著對元素 rehash，rehash 的過程也要考慮哈希沖突的情況，最后重置哈希表數(shù)組就結(jié)束了。
2.6 get 方法
public V get(Object key) {// 鍵判斷Object k = maskNull(key);Object[] tab = table;int len = tab.length;// 根據(jù) key 計算角標int i = hash(k, len);while (true) {Object item = tab[i];// key 相同返回 valueif (item == k)return (V) tab[i + 1];// 如果找不到會一直向后查找，直到數(shù)組索引位置上沒有 key 時停止// 為什么 key 為 null 時停止查找呢，原因是，如果沒有出現(xiàn)哈希沖突，那么根據(jù) key 的哈希值一次就可以定位到要返回的 value// 如果出現(xiàn)了哈希沖突，那么該鍵值與前面沖突的鍵值對之間一定是連續(xù)的if (item == null)return null;// 計算鍵位置，跳過 value，接著查找i = nextKeyIndex(i, len);}}如果我們不看源碼的話，讓大家猜一下這個查找的過程是怎么樣的，大家能猜到嗎？相對來說查找就比較簡單一些了，先根據(jù) key 計算出對應的數(shù)組索引位置，判斷 key 是否是同一個，如果是直接返回，如果不是意味著可能出現(xiàn)哈希沖突，當然也可能是不存在該 key，為了保證正確性，還會向后面查找，當出現(xiàn) null 時即結(jié)束查找，原因上面作了解釋。
2.7 remove 方法
下面我們來看一下 remove 方法，變相來說刪除其實也就是查找，只不過多了一個刪除動作，查找過程與 get 方法類似，多了一個重要的操作，把刪除的鍵值對置 null 后需要從當前位置開始調(diào)整哈希表，調(diào)整哈希表是為了糾正因為哈希沖突導致的不正確性。
public V remove(Object key) {Object k = maskNull(key);Object[] tab = table;int len = tab.length;// 根據(jù) key 的哈希值計算索引int i = hash(k, len);// 這個過程與 get 方法類似while (true) {Object item = tab[i];if (item == k) {modCount++;size--;@SuppressWarnings("unchecked")V oldValue = (V) tab[i + 1];// 下次 GC 回收tab[i + 1] = null;tab[i] = null;// 刪除鍵值對后需要調(diào)整哈希表數(shù)組// 為什么要調(diào)整哈希表數(shù)組呢，原因是因為后面鍵值對可能是因為哈希沖突添加進去的，// 如果當前鍵值對移除了，那么后面因為哈希沖突添加的鍵值對就不能通過 get 方法獲取了closeDeletion(i);return oldValue;}if (item == null)return null;i = nextKeyIndex(i, len);}}上面的源碼中我們對調(diào)整哈希表做了分析，下面就來看下具體是怎么做的。
private void closeDeletion(int d) {// Adapted from Knuth Section 6.4 Algorithm RObject[] tab = table;int len = tab.length;Object item;/*** 因為移除的鍵值對的索引并不一定是其哈希值算出的桶位置*（線性探測，向后移動或從 0 開始） ，所以需要對哈希表進行調(diào)整** 結(jié)束循環(huán)的條件是 key 為 null*/for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;i = nextKeyIndex(i, len) ) {// 當前桶位置計算出 key 的哈希值，這個哈希值并不一定等于 iint r = hash(item, len);/*** d：當前 key 所在的索引位置* r：下一個 key 本來應該存放的位置* i：下一個 key 實際存放位置（可能移動，它的位置被占，只能向后移動，甚至可能移動到最前面）*/if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {// 把后面的鍵值對移動到前面去，因為是一個環(huán)操作，當然也可能是把前面的鍵值對給移到后面去tab[d] = item;tab[d + 1] = tab[i + 1];// 移動后置 nulltab[i] = null;tab[i + 1] = null;// 重置 d，以便處理后續(xù)的鍵值對d = i;}}}調(diào)整的過程其實就是鍵值對向前移動，當然數(shù)組頭位置的元素也可能移動到數(shù)組尾部，結(jié)束調(diào)整循環(huán)的條件是 key 為 null，我想到這里大家應該都知道了為什么要以 key 為 null 作為結(jié)束條件了。
jdk1.8 源碼閱讀：https://github.com/zchen96/jdk1.8-source-code-read
總結(jié)
以上是生活随笔為你收集整理的Java8 IdentityHashMap 源码分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
