App下載

給面試官講解hashmap底層原理后,他表示很看好我

猿友 2020-08-20 17:40:03 瀏覽數(shù) (4140)
反饋

作為一名程序員,你面試的時(shí)候肯定被問(wèn)過(guò)HashMap這個(gè)知識(shí)點(diǎn),它的基本實(shí)現(xiàn)原理是每個(gè)面試者都該掌握的,當(dāng)我們熟練的掌握了HashMap 的內(nèi)部實(shí)現(xiàn)原理。面對(duì)面試官的詢問(wèn),就能應(yīng)答自如,接下來(lái)小編將帶大家了解 JDK7 版本的 HashMap基礎(chǔ)及其實(shí)現(xiàn)原理。

一、 HashMap介紹

HashMap簡(jiǎn)介: HashMap 是一個(gè)散列表,它存儲(chǔ)的內(nèi)容是鍵值對(duì)(key-value)映射。 HashMap 繼承于AbstractMap,實(shí)現(xiàn)了Map、Cloneable、java.io.Serializable接口。 HashMap 的實(shí)現(xiàn)不是同步的,這意味著它不是線程安全的。它的key、value都可以為null。此外,HashMap中的映射不是有序的。 HashMap 的實(shí)例有兩個(gè)參數(shù)影響其性能:“初始容量” 和 “加載因子”。容量 是哈希表中桶的數(shù)量,初始容量 只是哈希表在創(chuàng)建時(shí)的容量。加載因子 是哈希表在其容量自動(dòng)增加之前可以達(dá)到多滿的一種尺度。當(dāng)哈希表中的條目數(shù)超出了加載因子與當(dāng)前容量的乘積時(shí),則要對(duì)該哈希表進(jìn)行rehash操作(即重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)),從而哈希表將具有大約兩倍的桶數(shù)。 通常,默認(rèn)加載因子是 0.75, 這是在時(shí)間和空間成本上尋求一種折衷。加載因子過(guò)高雖然減少了空間開銷,但同時(shí)也增加了查詢成本(在大多數(shù) HashMap 類的操作中,包括 getput 操作,都反映了這一點(diǎn))。在設(shè)置初始容量時(shí)應(yīng)該考慮到映射中所需的條目數(shù)及其加載因子,以便最大限度地減少 rehash 操作次數(shù)。如果初始容量大于最大條目數(shù)除以加載因子,則不會(huì)發(fā)生 rehash 操作。

HashMap的繼承關(guān)系:

HashMap的繼承關(guān)系

HashMap與Map關(guān)系如下圖

HashMap與Map關(guān)系

HashMap的構(gòu)造函數(shù)

HashMap共有4個(gè)構(gòu)造函數(shù),如下:

// 默認(rèn)構(gòu)造函數(shù)。
HashMap()
// 指定“容量大小”的構(gòu)造函數(shù)
HashMap(int capacity)
// 指定“容量大小”和“加載因子”的構(gòu)造函數(shù)
HashMap(int capacity, float loadFactor)
// 包含“子Map”的構(gòu)造函數(shù)
HashMap(Map<? extends K, ? extends V> map)

二、JDK7 中 HashMap 底層原理

HashMapJDK7 或者 JDK8 中采用的基本存儲(chǔ)結(jié)構(gòu)都是數(shù)組+鏈表形式。本節(jié)主要是研究 HashMapJDK7 中的底層實(shí)現(xiàn),其基本結(jié)構(gòu)圖如下所示:

HashMap基本結(jié)構(gòu)圖

上圖中左邊橙色區(qū)域是哈希表,右邊藍(lán)色區(qū)域?yàn)殒湵?,鏈表中的元素類型?Entry,它包含四個(gè)屬性分別是:

  • K key
  • V value
  • int hash
  • Entry next

那么為什么會(huì)出現(xiàn)數(shù)組+鏈表形式的存儲(chǔ)結(jié)構(gòu)呢?這里簡(jiǎn)單地闡述一下,后續(xù)將以源碼的形式詳細(xì)介紹。 我們?cè)谑褂?HashMap.put("Key", "Value")方法存儲(chǔ)數(shù)據(jù)的時(shí)候,底層實(shí)際是將keyvalueEntry的形式存儲(chǔ)到哈希表中,哈希表是一個(gè)數(shù)組,那么它是如何將一個(gè) Entry 對(duì)象存儲(chǔ)到數(shù)組中呢?是如何確定當(dāng)前 keyvalue 組成的 Entry 該存到數(shù)組的哪個(gè)位置上,換句話說(shuō)是如何確定 Entry 對(duì)象在數(shù)組中的索引的呢?通常情況下,我們?cè)诖_定數(shù)組的時(shí)候,都是在數(shù)組中挨個(gè)存儲(chǔ)數(shù)據(jù),直到數(shù)組全滿,然后考慮數(shù)組的擴(kuò)容,而 HashMap 并不是這么操作的。在 Java 及大多數(shù)面向?qū)ο蟮木幊陶Z(yǔ)言中,每個(gè)對(duì)象都有一個(gè)整型變量 hashcode,這個(gè) hashcode 是一個(gè)很重要的標(biāo)識(shí),它標(biāo)識(shí)著不同的對(duì)象,有了這個(gè) hashcode,那么就很容易確定 Entry 對(duì)象的下標(biāo)索引了,在 Java 語(yǔ)言中,可以理解 hashcode 轉(zhuǎn)化為數(shù)組下標(biāo)是按照數(shù)組長(zhǎng)度取模運(yùn)算的,基本公式如下所示:

int index = HashCode(key) % Array.length

實(shí)際上,在 JDK 中哈希函數(shù)并沒(méi)有直接采取取模運(yùn)算,而是利用了位運(yùn)算的方式來(lái)提高性能,在這里我們理解為簡(jiǎn)單的取模運(yùn)算。 我們知道了對(duì) Key 進(jìn)行哈希運(yùn)算然后對(duì)數(shù)組長(zhǎng)度進(jìn)行取模就可以得到當(dāng)前 Entry 對(duì)象在數(shù)組中的下標(biāo),那么我們可以一直調(diào)用 HashMapput 方法持續(xù)存儲(chǔ)數(shù)據(jù)到數(shù)組中。但是存在一種現(xiàn)象,那就是根據(jù)不同的 Key 計(jì)算出來(lái)的結(jié)果有可能會(huì)完全相同,這種現(xiàn)象叫作“哈希沖突”。既然出現(xiàn)了哈希沖突,那么發(fā)生沖突的這個(gè)數(shù)據(jù)該如何存儲(chǔ)呢?哈希沖突其實(shí)是無(wú)法避免的一個(gè)事實(shí),既然無(wú)法避免,那么就應(yīng)該想辦法來(lái)解決這個(gè)問(wèn)題,目前常用的方法主要是兩種,一種是開放尋址法,另外一種是鏈表法。 開放尋址法是原理比較簡(jiǎn)單,就是在數(shù)組里面“另謀高就”,嘗試尋找下一個(gè)空檔位置。而鏈表法則不是尋找下一個(gè)空檔位置,而是繼續(xù)在當(dāng)前沖突的地方存儲(chǔ),與現(xiàn)有的數(shù)據(jù)組成鏈表,以鏈表的形式進(jìn)行存儲(chǔ)。HashMap 的存儲(chǔ)形式是數(shù)組+鏈表就是采用的鏈表法來(lái)解決哈希沖突問(wèn)題的。具體的詳細(xì)說(shuō)明請(qǐng)繼續(xù)往下看。 在日常開發(fā)中,開發(fā)者對(duì)于 HashMap 使用的最多的就是它的構(gòu)造方法、put 方法以及get 方法了,下面就開始詳細(xì)地從這三個(gè)方法出發(fā),深入理解HashMap 的實(shí)現(xiàn)原理。

三、HashMap put、get 方法流程圖

這里提供一個(gè) HashMapput 方法存儲(chǔ)數(shù)據(jù)的流程圖供讀者參考:

put 方法存儲(chǔ)數(shù)據(jù)的流程圖

這里提供一個(gè) HashMapget 方法獲取數(shù)據(jù)的流程圖供讀者參考:

 get 方法獲取數(shù)據(jù)的流程圖

上面中 get 流程圖畫得稍微比正常的要復(fù)雜一些,只是為了描述流程更加清晰。

四、常見的 HashMap 的迭代方式

在實(shí)際開發(fā)過(guò)程中,我們對(duì)于 HashMap 的迭代遍歷也是常見的操作,HashMap 的迭代遍歷常用方式有如下幾種:

  • 方式一:迭代器模式

Map<String, String> map = new HashMap<>(16);
Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, String> next = iterator.next();
    System.out.println(next.getKey() + ":" + next.getValue());
}

  • 方式二:遍歷 Set>方式

Map<String, String> map = new HashMap<>(16);
for (Map.Entry<String, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ":" + entry.getValue());
}

  • 方式三:forEach 方式(JDK8 特性,lambda)

Map<String, String> map = new HashMap<>(16);
map.forEach((key, value) -> System.out.println(key + ":" + value));

  • 方式四:keySet 方式

Map<String, String> map = new HashMap<>(16);
Iterator<String> keyIterator = map.keySet().iterator();
while (keyIterator.hasNext()) {
    String key = keyIterator.next();
    System.out.println(key + ":" + map.get(key));
}

(推薦微課:Java微課

把這四種方式進(jìn)行比較,前三種其實(shí)屬于同一種,都是迭代器遍歷方式,如果要同時(shí)使用到 keyvalue,推薦使用前三種方式,如果僅僅使用到 key,那么推薦使用第四種。

文章來(lái)源:www.toutiao.com/a6862688709423137294/

以上就是W3Cschool編程獅關(guān)于hashmap底層原理的相關(guān)介紹了,希望對(duì)大家有所幫助。

0 人點(diǎn)贊