HashMap面試會(huì)問(wèn)的題目有哪些

本篇內(nèi)容介紹了“HashMap面試會(huì)問(wèn)的題目有哪些”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

Set 家族

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

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

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

其中比較常用的有三種：

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: 采用紅黑樹(shù)結(jié)構(gòu)，特點(diǎn)是可以有序，可以用自然排序或者自定義比較器來(lái)排序；缺點(diǎn)就是查詢(xún)速度沒(méi)有 HashSet 快。

Map 家族

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

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

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

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

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

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

對(duì)于 HashMap 中的每個(gè) key，首先通過(guò) 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è)問(wèn)題：

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

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

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

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

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

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

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

答：load factor. 即用 pair 的數(shù)量除以 buckets 的數(shù)量，也就是平均每個(gè)桶里裝幾對(duì)。Java 中默認(rèn)值是 0.75f，如果超過(guò)了這個(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 是否相同的。

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

<span >為什么重寫(xiě) equals() 方法，一定要重寫(xiě) hashCode() 呢？

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

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

撒花～～????????????

接下來(lái)我們?cè)賹?duì)這兩個(gè)方法一探究竟：

其實(shí) hashCode() 和 equals() 方法都是在 Object class 這個(gè)老祖宗里定義的，Object 是所有 Java 中的 class 的鼻祖，默認(rèn)都是有的，甩不掉的。

那既然是白給的，我們先來(lái)看看大禮包里有什么，谷歌 Object 的 Oracle 文檔：

所以這些方法都是可以直接拿來(lái)用的呢～

回到 hashCode() 和 equals()，那么如果這個(gè)新的 class 里沒(méi)有重寫(xiě) (override) 這兩個(gè)方法，就是默認(rèn)繼承 Object class 里的定義了。

那我們點(diǎn)進(jìn)去來(lái)看看 equals() 是怎么定義的：

記筆記：

equals() 方法就是比較這兩個(gè) references 是否指向了同一個(gè) object.

嗯？？？你在逗我嗎？？那豈不是和 == 一樣了？？

補(bǔ)充：
我們常用的比較大小的符號(hào)之 ==
如果是 primitive type，那么 == 就是比較數(shù)值的大小；
如果是 reference type，那么就比較的是這兩個(gè) reference 是否指向了同一個(gè) object。

再補(bǔ)充：
Java 的數(shù)據(jù)類(lèi)型可以分為兩種：
Primitive type 有且僅有8種：byte, short, int, long, float, double, char, boolean.
其他都是 Reference type.
所以雖然 Java 聲稱(chēng) “Everything is object”，但是還是有非 object 數(shù)據(jù)類(lèi)型的存在的。

我不信，我要去源碼里看看它是怎么實(shí)現(xiàn)的。

哈，還真是的，繞了這么半天，equals() 就是用 == 來(lái)實(shí)現(xiàn)的！

那為什么還弄出來(lái)這么個(gè)方法呢？

<span >答：為了讓你 override～

比如一般來(lái)說(shuō)我們比較字符串就是想比較這兩個(gè)字符串的內(nèi)容的，那么：

str1 = “tianxiaoqi”;
str2 =  new String(“tianxiaoqi”);

str1 == str2; // return false
str1.equals(str2); // return true

因?yàn)?String 里是重寫(xiě)了 equals() 方法的：

老祖宗留給你就是讓你自己用的，如果你不用，那人家也提供了默認(rèn)的方法，也是夠意思了。

好了，我們?cè)偃タ?hashCode() 的介紹：

那至于 hashCode() 返回的究竟是什么，和本文關(guān)聯(lián)不太大，有興趣的同學(xué)可以看參考這篇文章，結(jié)論就是：

返回的并不一定是對(duì)象的（虛擬）內(nèi)存地址，具體取決于運(yùn)行時(shí)庫(kù)和JVM的具體實(shí)現(xiàn)。

但無(wú)論是怎么實(shí)現(xiàn)的，都需要遵循文檔上的約定，也就是對(duì)不同的 object 會(huì)返回唯一的哈希值。

哈希沖突詳解

一般來(lái)說(shuō)哈希沖突有兩大類(lèi)解決方式

1. Separate chaining

2. Open addressing

Java 中采用的是第一種 Separate chaining，即在發(fā)生碰撞的那個(gè)桶后面再加一條“鏈”來(lái)存儲(chǔ)，那么這個(gè)“鏈”使用的具體是什么數(shù)據(jù)結(jié)構(gòu)，不同的版本稍有不同：

在 JDK1.6 和 1.7 中，是用鏈表存儲(chǔ)的，這樣如果碰撞很多的話(huà)，就變成了在鏈表上的查找，worst case 就是 O(n)；

在 JDK 1.8 進(jìn)行了優(yōu)化，當(dāng)鏈表長(zhǎng)度較大時(shí)（超過(guò) 8），會(huì)采用紅黑樹(shù)來(lái)存儲(chǔ)，這樣大大提高了查找效率。

（話(huà)說(shuō)，這個(gè)還真的喜歡考，已經(jīng)在多次面試中被問(wèn)過(guò)了，還有面試官問(wèn)為什么是超過(guò)“8”才用紅黑樹(shù)????）

第二種方法 open addressing 也是非常重要的思想，因?yàn)樵谡鎸?shí)的分布式系統(tǒng)里，有很多地方會(huì)用到 hash 的思想但又不適合用 seprate chaining。

這種方法是順序查找，如果這個(gè)桶里已經(jīng)被占了，那就按照“某種方式”繼續(xù)找下一個(gè)沒(méi)有被占的桶，直到找到第一個(gè)的。

空的

如圖所示，John Smith 和 Sandra Dee 發(fā)生了哈希沖突，都被計(jì)算到 152 號(hào)桶，于是 Sandra 就去了下一個(gè)空位 - 153 號(hào)桶，當(dāng)然也會(huì)對(duì)之后的 key 發(fā)生影響：Ted Baker 計(jì)算結(jié)果本應(yīng)是放在 153 號(hào)的，但鑒于已經(jīng)被 Sandra 占了，就只能再去下一個(gè)空位了，所以到了 154 號(hào)。

這種方式叫做 Linear probing 線性探查，就像上圖所示，一個(gè)個(gè)的順著找下一個(gè)空位。當(dāng)然還有其他的方式，比如去找平方數(shù)，或者 Double hashing.

HashMap 基本操作

每種數(shù)據(jù)結(jié)構(gòu)的基本操作都無(wú)外乎<span >增刪改查</span>這四種，具體到 HashMap 來(lái)說(shuō)，

• 增：put(K key, V value)

• 刪：remove(Object key)

• 改：還是用的 put(K key, V value)

• 查：get(Object key) / containsKey(Object key)

細(xì)心的同學(xué)可能發(fā)現(xiàn)了，為什么有些 key 的類(lèi)型是 Object，有些是 K 呢？這還不是因?yàn)?equals()...

這是因?yàn)?，?get/remove 的時(shí)候，不一定是用的同一個(gè) object。

還記得那個(gè) str1 和 str2 都是田小齊的例子嗎？那比如我先 put(str1, value)，然后用 get(str2) 的時(shí)候，也是想要到 tianxiaoqi 對(duì)應(yīng)的 value 呀！不能因?yàn)槲覔Q了身衣服就不認(rèn)得我了呀！所以在 get/remove 的時(shí)候并沒(méi)有很限制 key 的類(lèi)型，方便另一個(gè)自己相認(rèn)。

其實(shí)這些 API 的操作流程大同小異，我們以最復(fù)雜的 put(K key, V value) 來(lái)講：

1. 首先要拿到 array 中要放的位置的 index

• 怎么找 index 呢，這里我們可以單獨(dú)用 getIndex() method 來(lái)做這件事；

• 具體怎么做，就是通過(guò) hash function 算出來(lái)的值，模上數(shù)組的長(zhǎng)度；

2. 那拿到了這個(gè)位置的 Node，我們開(kāi)始 traverse 這個(gè) LinkedList，這就是在鏈表上的操作了，

• 如果找的到，就更新一下 value；

• 如果沒(méi)找到，就把它放在鏈表上，可以放頭上，也可以放尾上，一般我喜歡放頭上，因?yàn)樾录尤氲脑赜玫降母怕士偸谴笠恍⒉挥绊憰r(shí)間復(fù)雜度。

代碼如下：

  public V put(K key, V value) {
	int index = getIndex(key);
	Node<K, V> node = array[index];
	Node<K, V> head = node; 
	while (node != null) {
		// 原來(lái)有這個(gè) key，僅更新值
		if (checkEquals(key, node)) {
			V preValue = node.value;
			node.value = value;
			return preValue;
		}
		node = node.next;
	}
	// 原來(lái)沒(méi)有這個(gè) key，新加這個(gè) node
	Node<K, V> newNode = new Node(key, value); 
	newNode.next = head;
	array[index] = newNode;
	return null;
}

與 Hashtable 的區(qū)別

這是一個(gè)年齡暴露貼，HashMap 與 Hashtable 的關(guān)系，就像 ArrayList 與 Vector，以及 StringBuilder 與 StringBuffer。

Hashtable 是早期 JDK 提供的接口，HashMap 是新版的； 它們之間最顯著的區(qū)別，就是 Hashtable 是線程安全的，HashMap 并非線程安全。

這是因?yàn)?Java 5.0 之后允許數(shù)據(jù)結(jié)構(gòu)不考慮線程安全的問(wèn)題，因?yàn)閷?shí)際工作中我們發(fā)現(xiàn)沒(méi)有必要在數(shù)據(jù)結(jié)構(gòu)的層面上上鎖，加鎖和放鎖在系統(tǒng)中是有開(kāi)銷(xiāo)的，內(nèi)部鎖有時(shí)候會(huì)成為程序的瓶頸。

所以 HashMap, ArrayList, StringBuilder 不再考慮線程安全的問(wèn)題，性能提升了很多，當(dāng)然，線程安全問(wèn)題也就轉(zhuǎn)移給我們程序員了。

另外一個(gè)區(qū)別就是：HashMap 允許 key 中有 null 值，Hashtable 是不允許的。這樣的好處就是可以給一個(gè)默認(rèn)值。

“HashMap面試會(huì)問(wèn)的題目有哪些”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！