HashMap的面試題整理小結(jié)

發(fā)布時(shí)間：2020-02-17 15:10:19 作者：虛無V旋渦

HashMap存儲(chǔ)鍵值對實(shí)現(xiàn)快速存取，允許為null。key值不可重復(fù)，若key值重復(fù)則覆蓋。本文給大家分享HashMap的面試題，非常不錯(cuò)是小編日常收集整理，具有一定的參考借鑒價(jià)值，需要的朋友參考下吧

HashMap的特性

1.HashMap存儲(chǔ)鍵值對實(shí)現(xiàn)快速存取，允許為null。key值不可重復(fù)，若key值重復(fù)則覆蓋。

2.非同步，線程不安全。

3.底層是hash表，不保證有序(比如插入的順序)

1.HashMap的底層原理是什么？

HashMap基于hashing的原理，jdk8后采用數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)。我們通過put和get存儲(chǔ)和獲取對象。當(dāng)我們給put()方法傳遞鍵和值時(shí)，先對鍵做一個(gè)hashCode()的計(jì)算來得到它在

bucket數(shù)組中的位置來存儲(chǔ)Entry對象。當(dāng)獲取對象時(shí)，通過get獲取到bucket的位置，再通過鍵對象的equals()方法找到正確的鍵值對，然后在返回值對象。

2.hashMap中put是如何實(shí)現(xiàn)的？

1.計(jì)算關(guān)于key的hashcode值（與Key.hashCode的高16位做異或運(yùn)算）

2.如果散列表為空時(shí)，調(diào)用resize()初始化散列表

3.如果沒有發(fā)生碰撞，直接添加元素到散列表中去

4.如果發(fā)生了碰撞(hashCode值相同)，進(jìn)行三種判斷

4.1:若key地址相同或者equals后內(nèi)容相同，則替換舊值

4.2:如果是紅黑樹結(jié)構(gòu)，就調(diào)用樹的插入方法

4.3：鏈表結(jié)構(gòu)，循環(huán)遍歷直到鏈表中某個(gè)節(jié)點(diǎn)為空，尾插法進(jìn)行插入，插入之后判斷鏈表個(gè)數(shù)是否到達(dá)變成紅黑樹的闕值8；也可以遍歷到有節(jié)點(diǎn)與插入元素的哈希值和內(nèi)容相同，進(jìn)行覆蓋。

5.如果桶滿了大于閥值，則resize進(jìn)行擴(kuò)容

3.hashMap中g(shù)et是如何實(shí)現(xiàn)的？

對key的hashCode進(jìn)行hashing，與運(yùn)算計(jì)算下標(biāo)獲取bucket位置，如果在桶的首位上就可以找到就直接返回，否則在樹中找或者鏈表中遍歷找，如果有hash沖突，則利用equals方法去遍歷鏈表查找節(jié)點(diǎn)。

4.當(dāng)兩個(gè)對象的hashcode相同會(huì)發(fā)生什么？

會(huì)產(chǎn)生哈希碰撞，若key值相同則替換舊值，不然鏈接到鏈表后面，鏈表長度超過闕值8就轉(zhuǎn)為紅黑樹存儲(chǔ). HashCode相同，通過equals比較內(nèi)容獲取值對象

5.HashMap和HashTable的區(qū)別

相同點(diǎn)：都是存儲(chǔ)key-value鍵值對的

不同點(diǎn)：

HashMap允許Key-value為null，hashTable不允許； hashMap沒有考慮同步，是線程不安全的。hashTable是線程安全的，給api套上了一層synchronized修飾; HashMap繼承于AbstractMap類，hashTable繼承與Dictionary類。迭代器(Iterator)。HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以當(dāng)有其它線程改變了HashMap的結(jié)構(gòu)（增加或者移除元素），將會(huì)拋出ConcurrentModificationException。容量的初始值和增加方式都不一樣：HashMap默認(rèn)的容量大小是16；增加容量時(shí)，每次將容量變?yōu)?quot;原始容量x2"。Hashtable默認(rèn)的容量大小是11；增加容量時(shí)，每次將容量變?yōu)?quot;原始容量x2 + 1"；添加key-value時(shí)的hash值算法不同：HashMap添加元素時(shí)，是使用自定義的哈希算法。Hashtable沒有自定義哈希算法，而直接采用的key的hashCode()。

6.什么是HashSet？

HashSet實(shí)現(xiàn)了Set接口，它不允許集合中有重復(fù)的值，當(dāng)我們提到HashSet時(shí)，第一件事情就是在將對象存儲(chǔ)在HashSet之前，要先確保對象重寫equals()和hashCode()方法，這樣才能比較對象的值是否相等，以確保set中沒有儲(chǔ)存相等的對象。如果我們沒有重寫這兩個(gè)方法，將會(huì)使用這個(gè)方法的默認(rèn)實(shí)現(xiàn)。public boolean add(Object o)方法用來在Set中添加元素，當(dāng)元素值重復(fù)時(shí)則會(huì)立即返回false，如果成功添加的話會(huì)返回true。

7.HashSet與HashMap的區(qū)別？

在這里插入圖片描述

8.傳統(tǒng)hashMap的缺點(diǎn)(為什么引入紅黑樹？

JDK 1.8 以前 HashMap 的實(shí)現(xiàn)是數(shù)組+鏈表，即使哈希函數(shù)取得再好，也很難達(dá)到元素百分百均勻分布。當(dāng) HashMap 中有大量的元素都存放到同一個(gè)桶中時(shí)，這個(gè)桶下有一條長長的鏈表，這個(gè)時(shí)候 HashMap 就相當(dāng)于一個(gè)單鏈表，假如單鏈表有 n 個(gè)元素，遍歷的時(shí)間復(fù)雜度就是 O(n)，完全失去了它的優(yōu)勢。針對這種情況，JDK 1.8 中引入了紅黑樹（查找時(shí)間復(fù)雜度為 O(logn)）來優(yōu)化這個(gè)問題

9.平時(shí)在使用HashMap時(shí)一般使用什么類型的元素作為Key？

選擇Integer，String這種不可變的類型，像對String的一切操作都是新建一個(gè)String對象，對新的對象進(jìn)行拼接分割等，這些類已經(jīng)很規(guī)范的覆寫了hashCode()以及equals()方法。作為不可變類天生是線程安全的，

10.如果HashMap的大小超過了負(fù)載因子(load factor)定義的容量，怎么辦？

超過闕值會(huì)進(jìn)行擴(kuò)容操作，概括的講就是擴(kuò)容后的數(shù)組大小是原數(shù)組的2倍，將原來的元素重新hashing放入到新的散列表中去。

總結(jié)

以上所述是小編給大家介紹的HashMap的面試題整理，希望對大家有所幫助，也非常感謝大家對腳本之家網(wǎng)站的支持！