圖解HashMap和HashSet的內部工作機制

HashMap 和 HashSet 內部是如何工作的？散列函數（hashing function）是什么？

HashMap不僅是一個常用的數據結構，在面試中也是熱門話題。

Q1. HashMap 如何存儲數據？

A1. 以鍵／值對（key/value）形式存儲。你可以使用鍵（key）來存、取值。

Q2. HashMap 查詢時間的復雜度是怎樣的？

A2. 是O( n ) = O(k * n)。如果 hashCode() 方法能向下面討論的那樣把數據分散到桶（bucket）中，那么平均是O(1)。

Q3. HashMap 內部是如何存儲數據的？

A3. HashMap 使用后臺數組（backing array）作為桶，并使用鏈表（linked list）存儲鍵／值對。

桶的后臺數組：如下所示

1）使用鍵（key）和值（value）將一個對象放入 map 中時，會隱式調用 hashCode() 方法，返回哈希值（hash code value），比如 123。兩個不同的鍵能夠返回一樣的哈希值。良好的哈希算法（hashing algorithm）能夠將數值分散開。在上面的例子中，我們假設 (“John”,01/01/1956) 的鍵和 (“Peter”, 01/01/1995) 的鍵返回相同的哈希值，都是  123 。

2）當返回一個 hashCode，例如是 123，初始的 HashMap 容量為 10，它如何知道存儲到后臺數組（backing array）的哪個索引（index）呢？HashMap 內部會調用 hash(int ) 和 indexFor(int h, int length) 方法。這被稱為 哈希 函數（hashing function）。

簡要解釋下這個函數：

hashCode() % capacity

123 % 10 = 3
456 % 10 = 6

這表示，“hashCode = 123”存儲在備份數組的索引3上。

容量為 10 的情況下，你可能得到的數字在 0 到 9 之間。

一旦 HashMap 達到容量的 75%，也就是哈希因子(hash factor)默認值 0.75，后臺數組（backing array）的容量就會加倍，發生 重散列 （rehashing）為新的 20 的容量重新分配桶。

hashCode() % capacity

123 % 20 = 3
456 % 20 = 16

上面重散列的取模方法有一個缺陷。如果 hashCode 是負數會怎樣？負索引可不是你想要的。因此，一個改進的哈希公式會移出符號位，然后再用取模（即 %）運算符計算剩余部分。

(123  & 0x7FFFFFFF) % 20 = 3
(456 & 0x7FFFFFFF) % 20 = 16

這確保你得到的索引值為正數。如果你查看 Java 8 的 HashMap 源碼，它的實現使用以下方法：

a).通過只抽取重要的低位，來防止不良離散值（poorer hashes）。

static int hash(int h) {
     // This function ensures that hashCodes that differ only by
     // constant multiples at each bit position have a bounded
     // number of collisions (approximately 8 at default load factor).
     h ^= (h >>> 20) ^ (h >>> 12);
     return h ^ (h >>> 7) ^ (h >>> 4);
}

b).根據 哈希碼 （ hashCode ）和 容量 （ capacity ），來決定索引（index）。

static int indexFor(int h, int length) {
     return h & (length-1);
}

實際的名稱值對（name value pairs）作為一個鍵／值對存儲在 LinkedList 中。

如上圖所示，鍵／值對以鏈表形式存儲。兩個不同的鍵可以產生一樣的 hashCode，例如123，并存儲在同一個 bucket 中，理解這點至關重要。例如，上面例子中的 “John, 01/01/1956” 和 “Peter, 01/01/1995“ 。你如何只檢索 “John, 01/01/1956” 呢？此時你的 key 所屬類的 equals() 方法會被調用。它遍歷 bucket 為 “123” 的 LinkedList 中的每個條目，使用 equals() 方法找到并檢索出鍵為 “John, 01/01/1956” 的條目。這就是在你的類中實現 hashCode() 和 equals() 方法重要性的原因。如果你使用一個現有的包裝類，如 Integer 或 String 作為鍵，它們已經實現了這兩個方法。如果你使用自己寫的類作為鍵，如 “John, 01/01/1956” 這樣含有名字和出生日期屬性的“MyKey”，你有責任正確地實現這些方法。

Q5. 為什么恰當地設置 HashMap 的初始容量（initial capacity）是最佳實踐？

A5. 這樣可以減少 重散列 的發生。

Q6. HashSet 內部如何存儲數據？

A6. HashSet 內部使用 HashMap 。它將元素存儲為鍵和值。（譯者注：HashSet 把存儲的值作為 key）

Q7. 為 Object 實現了一個糟糕的 hashcode() 會有什么影響？

A7. 不同的對象調用 hashCode() 方法應該返回不同的值。如果不同的對象返回相同的值，會導致更多的鍵／值對存儲在同一個 bucket 中。這會 降低 HashMap 和 HashSet 的 性能 。

 

來自：http://www.importnew.com/21841.html