HashMap的面試題整理小結

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

我要評論

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

HashMap的特性

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

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

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

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

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

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

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

1.計算關于key的hashcode值（與Key.hashCode的高16位做異或運算）

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

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

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

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

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

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

5.如果桶滿了大于閥值，則resize進行擴容

3.hashMap中get是如何實現(xiàn)的？

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

4.當兩個對象的hashcode相同會發(fā)生什么？

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

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

相同點：都是存儲key-value鍵值對的

不同點：

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

6.什么是HashSet？

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

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

在這里插入圖片描述

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

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

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

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

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

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

總結

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