本文轉(zhuǎn)自公眾號(hào) 碼農(nóng)田小齊（ID：NYCSDE）

如若轉(zhuǎn)載請(qǐng)聯(lián)系原公眾號(hào)

本文共6666字 | 閱讀需12分鐘

前言

HashMap 是無(wú)論在工作還是面試中都非常常見常考的數(shù)據(jù)結(jié)構(gòu)。

比如 Leetcode 第一題 Two Sum 的某種變種的最優(yōu)解就是需要用到 HashMap 的，高頻考題 LRU Cache 是需要用到 LinkedHashMap 的。

HashMap 用起來(lái)很簡(jiǎn)單，底層實(shí)現(xiàn)也不復(fù)雜，先來(lái)看幾道常見的面試題吧。相信大家多多少少都能回答上來(lái)一點(diǎn)，不清楚的地方就仔細(xì)閱讀本文啦～這篇文章帶你深挖到 HashMap 的老祖宗，保證吊打面試官

• == 和 equals() 的區(qū)別？

• 為什么重寫 equals() 就必須要重寫 hashCode()？

• Hashtable, HashSet 和 HashMap 的區(qū)別和聯(lián)系

• 處理 hash 沖突有哪些方法？Java 中用的哪一種？為什么？另一種方法你在工作中用過嗎？在什么情況下用得多？

• 徒手實(shí)現(xiàn)一個(gè) HashMap 吧

本文分以下章節(jié)：

• Set 和 Map 家族簡(jiǎn)介

• HashMap 實(shí)現(xiàn)原理

• 關(guān)于 hashCode() 和 equals()

• 哈希沖突詳解

• HashMap 基本操作

• 高頻面試考題分析

Set 家族

在講 Map 之前，我們先來(lái)看看 Set。

集合的概念我們初中數(shù)學(xué)就學(xué)過了，就是里面不能有重復(fù)元素，這里也是一樣。

Set 在 Java 中是一個(gè)接口，可以看到它是 java.util 包中的一個(gè)集合框架類，具體的實(shí)現(xiàn)類有很多：

其中比較常用的有三種：

HashSet: 采用 Hashmap 的 key 來(lái)儲(chǔ)存元素，主要特點(diǎn)是無(wú)序的，基本操作都是 O(1) 的時(shí)間復(fù)雜度，很快。

LinkedHashSet: 這個(gè)是一個(gè) HashSet + LinkedList 的結(jié)構(gòu)，特點(diǎn)就是既擁有了 O(1) 的時(shí)間復(fù)雜度，又能夠保留插入的順序。

TreeSet: 采用紅黑樹結(jié)構(gòu)，特點(diǎn)是可以有序，可以用自然排序或者自定義比較器來(lái)排序；缺點(diǎn)就是查詢速度沒有 HashSet 快。

Map 家族

Map 是一個(gè)鍵值對(duì) (Key - Value pairs)，其中 key 是不可以重復(fù)的，畢竟 set 中的 key 要存在這里面。

那么與 Set 相對(duì)應(yīng)的，Map 也有這三個(gè)實(shí)現(xiàn)類：

HashMap: 與 HashSet 對(duì)應(yīng)，也是無(wú)序的，O(1)。

LinkedHashMap: 這是一個(gè)「HashMap + 雙向鏈表」的結(jié)構(gòu)，落腳點(diǎn)是 HashMap，所以既擁有 HashMap 的所有特性還能有順序。

TreeMap: 是有序的，本質(zhì)是用二叉搜索樹來(lái)實(shí)現(xiàn)的。

HashMap 實(shí)現(xiàn)原理

對(duì)于 HashMap 中的每個(gè) key，首先通過 hash function 計(jì)算出一個(gè) hash 值，這個(gè)hash值就代表了在 buckets 里的編號(hào)，而 buckets 實(shí)際上是用數(shù)組來(lái)實(shí)現(xiàn)的，所以把這個(gè)數(shù)值模上數(shù)組的長(zhǎng)度得到它在數(shù)組的 index，就這樣把它放在了數(shù)組里。

那么這里有幾個(gè)問題：

如果不同的元素算出了相同的哈希值，那么該怎么存放呢？

答：這就是哈希碰撞，即多個(gè) key 對(duì)應(yīng)了同一個(gè)桶。

HashMap 中是如何保證元素的唯一性的呢？即相同的元素會(huì)不會(huì)算出不同的哈希值呢？

答：通過 hashCode() 和 equals() 方法來(lái)保證元素的唯一性。

如果 pairs 太多，buckets 太少怎么破？

答：Rehasing. 也就是碰撞太多的時(shí)候，會(huì)把數(shù)組擴(kuò)容至兩倍（默認(rèn)）。所以這樣雖然 hash 值沒有變，但是因?yàn)閿?shù)組的長(zhǎng)度變了，所以算出來(lái)的 index 就變了，就會(huì)被分配到不同的位置上了，就不用擠在一起了，小伙伴們我們江湖再見～

那什么時(shí)候會(huì) rehashing 呢？也就是怎么衡量桶里是不是足夠擁擠要擴(kuò)容了呢？

答：load factor. 即用 pair 的數(shù)量除以 buckets 的數(shù)量，也就是平均每個(gè)桶里裝幾對(duì)。Java 中默認(rèn)值是 0.75f，如果超過了這個(gè)值就會(huì) rehashing.

關(guān)于 hashCode() 和 equals()

如果 key 的 hashCode() 值相同，那么有可能是要發(fā)生 hash collision 了，也有可能是真的遇到了另一個(gè)自己。那么如何判斷呢？繼續(xù)用 equals() 來(lái)比較。

也就是說(shuō)，

hashCode() 決定了 key 放在這個(gè)桶里的編號(hào)，也就是在數(shù)組里的 index；

equals() 是用來(lái)比較兩個(gè) object 是否相同的。

那么該如何回答這道經(jīng)典面試題：

為什么重寫 equals() 方法，一定要重寫 hashCode() 呢？

答：首先我們有一個(gè)假設(shè)：任何兩個(gè) object 的 hashCode 都是不同的。

那么在這個(gè)條件下，有兩個(gè) object 是相等的，那如果不重寫 hashCode()，算出來(lái)的哈希值都不一樣，就會(huì)去到不同的 buckets 了，就迷失在茫茫人海中了，再也無(wú)法相認(rèn)，就和 equals() 條件矛盾了，證畢。

撒花～～