集合詳解之Map+面試題

文檔來源網(wǎng)絡侵權聯(lián)系刪除PAGEPAGE1僅供參考集合詳解之Map+面試題集合有兩個大接口：Collection和Map，本文重點來講解集合中另一個常用的集合類型Map。以下是Map的繼承關系圖：11Map簡介Map常用的實現(xiàn)類如下：Hashtable：Java早期提供的一個哈希表實現(xiàn)，它是線程安全的，不支持null鍵和值，因為它的性能不如ConcurrentHashMap，所以很少被推薦使用。HashMap：最常用的哈希表實現(xiàn)，如果程序中沒有多線程的需求，HashMap是一個很好的選擇，支持null鍵和值，如果在多線程中可用ConcurrentHashMap替代。TreeMap：基于紅黑樹的一種提供順序訪問的Map，自身實現(xiàn)了key的自然排序，也可以指定Comparator來自定義排序。LinkedHashMap：HashMap的一個子類，保存了記錄的插入順序，可在遍歷時保持與插入一樣的順序。Map常用方法常用方法包括：put、remove、get、size等，所有方法如下圖：enterimagedescriptionhere使用示例，請參考以下代碼：MaphashMap=newHashMap();

//增加元素

hashMap.put("name","老王");

hashMap.put("age","30");

hashMap.put("sex","你猜");

//刪除元素

hashMap.remove("age");

//查找單個元素

System.out.println(hashMap.get("age"));

//循環(huán)所有的key

for(Objectk:hashMap.keySet()){

System.out.println(k);

}

//循環(huán)所有的值

for(Objectv:hashMap.values()){

System.out.println(v);

}以上為HashMap的使用示例，其他類的使用也是類似。HashMap數(shù)據(jù)結構HashMap底層的數(shù)據(jù)是數(shù)組被成為哈希桶，每個桶存放的是鏈表，鏈表中的每個節(jié)點，就是HashMap中的每個元素。在JDK8當鏈表長度大于等于8時，就會轉成紅黑樹的數(shù)據(jù)結構，以提升查詢和插入的效率。HashMap數(shù)據(jù)結構，如下圖：enterimagedescriptionhereHashMap重要方法1）添加方法：put(Objectkey,Objectvalue)執(zhí)行流程如下：對key進行hash操作，計算存儲index；判斷是否有哈希碰撞，如果沒碰撞直接放到哈希桶里，如果有碰撞則以鏈表的形式存儲；判斷已有元素的類型，決定是追加樹還是追加鏈表，當鏈表大于等于8時，把鏈表轉換成紅黑樹；如果節(jié)點已經(jīng)存在就替換舊值；判斷是否超過閥值，如果超過就要擴容。源碼及說明：publicVput(Kkey,Vvalue){

//對key進行hash()

returnputVal(hash(key),key,value,false,true);

}

staticfinalinthash(Objectkey){

inth;

//對key進行hash()的具體實現(xiàn)

return(key==null)?0:(h=key.hashCode())^(h>>>16);

}

finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,

booleanevict){

Node<K,V>[]tab;Node<K,V>p;intn,i;

//tab為空則創(chuàng)建

if((tab=table)==null||(n=tab.length)==0)

n=(tab=resize()).length;

//計算index，并對null做處理

if((p=tab[i=(n-1)&hash])==null)

tab[i]=newNode(hash,key,value,null);

else{

Node<K,V>e;Kk;

//節(jié)點存在

if(p.hash==hash&&

((k=p.key)==key||(key!=null&&key.equals(k))))

e=p;

//該鏈為樹

elseif(pinstanceofTreeNode)

e=((TreeNode<K,V>)p).putTreeVal(this,tab,hash,key,value);

//該鏈為鏈表

else{

for(intbinCount=0;;++binCount){

if((e=p.next)==null){

p.next=newNode(hash,key,value,null);

if(binCount>=TREEIFY_THRESHOLD-1)//-1for1st

treeifyBin(tab,hash);

break;

}

if(e.hash==hash&&

((k=e.key)==key||(key!=null&&key.equals(k))))

break;

p=e;

}

}

//寫入

if(e!=null){//existingmappingforkey

VoldValue=e.value;

if(!onlyIfAbsent||oldValue==null)

e.value=value;

afterNodeAccess(e);

returnoldValue;

}

}

++modCount;

//超過loadfactor*currentcapacity，resize

if(++size>threshold)

resize();

afterNodeInsertion(evict);

returnnull;

}put()執(zhí)行流程圖如下：enterimagedescriptionhere2）獲取方法：get(Objectkey)執(zhí)行流程如下：首先比對首節(jié)點，如果首節(jié)點的hash值和key的hash值相同，并且首節(jié)點的鍵對象和key相同（地址相同或equals相等），則返回該節(jié)點；如果首節(jié)點比對不相同、那么看看是否存在下一個節(jié)點，如果存在的話，可以繼續(xù)比對，如果不存在就意味著key沒有匹配的鍵值對。源碼及說明：publicVget(Objectkey){

Node<K,V>e;

return(e=getNode(hash(key),key))==null?null:e.value;

}

/**

*該方法是Map.get方法的具體實現(xiàn)

*接收兩個參數(shù)

*@paramhashkey的hash值，根據(jù)hash值在節(jié)點數(shù)組中尋址，該hash值是通過hash(key)得到的

*@paramkeykey對象，當存在hash碰撞時，要逐個比對是否相等

*@return查找到則返回鍵值對節(jié)點對象，否則返回null

*/

finalNode<K,V>getNode(inthash,Objectkey){

Node<K,V>[]tab;Node<K,V>first,e;intn;Kk;//聲明節(jié)點數(shù)組對象、鏈表的第一個節(jié)點對象、循環(huán)遍歷時的當前節(jié)點對象、數(shù)組長度、節(jié)點的鍵對象

//節(jié)點數(shù)組賦值、數(shù)組長度賦值、通過位運算得到求模結果確定鏈表的首節(jié)點

if((tab=table)!=null&&(n=tab.length)>0&&

(first=tab[(n-1)&hash])!=null){

if(first.hash==hash&&//首先比對首節(jié)點，如果首節(jié)點的hash值和key的hash值相同，并且首節(jié)點的鍵對象和key相同（地址相同或equals相等），則返回該節(jié)點

((k=first.key)==key||(key!=null&&key.equals(k))))

returnfirst;//返回首節(jié)點

//如果首節(jié)點比對不相同、那么看看是否存在下一個節(jié)點，如果存在的話，可以繼續(xù)比對，如果不存在就意味著key沒有匹配的鍵值對

if((e=first.next)!=null){

//如果存在下一個節(jié)點e，那么先看看這個首節(jié)點是否是個樹節(jié)點

if(firstinstanceofTreeNode)

//如果是首節(jié)點是樹節(jié)點，那么遍歷樹來查找

return((TreeNode<K,V>)first).getTreeNode(hash,key);

//如果首節(jié)點不是樹節(jié)點，就說明還是個普通的鏈表，那么逐個遍歷比對即可

do{

if(e.hash==hash&&

((k=e.key)==key||(key!=null&&key.equals(k))))//比對時還是先看hash值是否相同、再看地址或equals

returne;//如果當前節(jié)點e的鍵對象和key相同，那么返回e

}while((e=e.next)!=null);//看看是否還有下一個節(jié)點，如果有，繼續(xù)下一輪比對，否則跳出循環(huán)

}

}

returnnull;//在比對完了應該比對的樹節(jié)點或者全部的鏈表節(jié)點都沒能匹配到key，那么就返回null相關面試題1.Map常見實現(xiàn)類有哪些？答：Map的常見實現(xiàn)類如下列表：Hashtable：Java早期提供的一個哈希表實現(xiàn)，它是線程安全的，不支持null鍵和值，因為它的性能不如ConcurrentHashMap，所以很少被推薦使用；HashMap：最常用的哈希表實現(xiàn)，如果程序中沒有多線程的需求，HashMap是一個很好的選擇，支持null鍵和值，如果在多線程中可用ConcurrentHashMap替代；TreeMap：基于紅黑樹的一種提供順序訪問的Map，自身實現(xiàn)了key的自然排序，也可以指定的Comparator來自定義排序；LinkedHashMap：HashMap的一個子類，保存了記錄的插入順序，可在遍歷時保持與插入一樣的順序。2.使用HashMap可能會遇到什么問題？如何避免？答：HashMap在并發(fā)場景中可能出現(xiàn)死循環(huán)的問題，這是因為HashMap在擴容的時候會對鏈表進行一次倒序處理，假設兩個線程同時執(zhí)行擴容操作，第一個線程正在執(zhí)行B→A的時候，第二個線程又執(zhí)行了A→B，這個時候就會出現(xiàn)B→A→B的問題，造成死循環(huán)。

解決的方法：升級JDK版本，在JDK8之后擴容不會再進行倒序，因此死循環(huán)的問題得到了極大的改善，但這不是終極的方案，因為HashMap本來就不是用在多線程版本下的，如果是多線程可使用ConcurrentHashMap替代HashMap。3.以下說法正確的是？A：Hashtable和HashMap都是非線程安全的

B：ConcurrentHashMap允許null作為key

C：HashMap允許null作為key

D：Hashtable允許null作為key

答：C

題目解析：Hashtable是線程安全的，ConcurrentHashMap和Hashtable是不允許null作為鍵和值的。4.TreeMap怎么實現(xiàn)根據(jù)value值倒序？答：使用Collections.sort(list,newComparator<Map.Entry<String,String>>()自定義比較器實現(xiàn)，先把TreeMap轉換為ArrayList，在使用Collections.sort()根據(jù)value進行倒序，完整的實現(xiàn)代碼如下。TreeMap<String,String>treeMap=newTreeMap();

treeMap.put("dog","dog");

treeMap.put("camel","camel");

treeMap.put("cat","cat");

treeMap.put("ant","ant");

//map.entrySet()轉成List

List<Map.Entry<String,String>>list=newArrayList<>(treeMap.entrySet());

//通過比較器實現(xiàn)比較排序

Collections.sort(list,newComparator<Map.Entry<String,String>>(){

publicintcompare(Map.Entry<String,String>m1,Map.Entry<String,String>m2){

returnm2.getValue().compareTo(m1.getValue());

}

});

//打印結果

for(Map.Entry<String,String>item:list){

System.out.println(item.getKey()+":"+item.getValue());

}程序執(zhí)行結果：dog:dog

cat:cat

camel:camel

ant:ant5.以下哪個Set實現(xiàn)了自動排序？A：LinedHashSet

B：HashSet

C：TreeSet

D：AbstractSet答：C6.以下程序運行的結果是什么？Hashtablehashtable=newHashtable();

hashtable.put("table",null);

System.out.println(hashtable.get("table"));答：程序執(zhí)行報錯：java.lang.NullPointerException。Hashtable不允許null鍵和值。7.HashMap有哪些重要的參數(shù)？用途分別是什么？答：HashMap有兩個重要的參數(shù)：容量（Capacity）和負載因子（LoadFactor）。容量（Capacity）：是指HashMap中桶的數(shù)量，默認的初始值為16。負載因子（LoadFactor）：也被稱為裝載因子，LoadFactor是用來判定HashMap是否擴容的依據(jù)，默認值為0.75f，裝載因子的計算公式=HashMap存放的KV總和（size）/Capacity。8.HashMap和Hashtable有什么區(qū)別？答：HashMap和Hashtable區(qū)別如下：Hashtable使用了synchronized關鍵字來保障線程安全，而HashMap是非線程安全的；HashMap允許K/V都為null，而HashtableK/V都不允許null；HashMap繼承自AbstractMap類；而Hashtable繼承自Dictionary類。9.什么是哈希沖突？答：當輸入兩個不同值，根據(jù)同一散列函數(shù)計算出相同的散列值的現(xiàn)象，我們就把它叫做碰撞（哈希碰撞）。10.有哪些方法可以解決哈希沖突？答：哈希沖突的常用解決方案有以下4種。開放定址法：當關鍵字的哈希地址p=H（key）出現(xiàn)沖突時，以p為基礎，產(chǎn)生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎，產(chǎn)生另一個哈希地址p2，循環(huán)此過程直到找出一個不沖突的哈希地址，將相應元素存入其中。再哈希法：這種方法是同時構造多個不同的哈希函數(shù)，當哈希地址Hi=RH1（key）發(fā)生沖突時，再計算Hi=RH2（key），循環(huán)此過程直到找到一個不沖突的哈希地址，這種方法唯一的缺點就是增加了計算時間。鏈地址法：這種方法的基本思想是將所有哈希地址為i的元素構成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除主要在同義詞鏈中進行。鏈地址法適用于經(jīng)常進行插入和刪除的情況。建立公共溢出區(qū)：將哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元素，一律填入溢出表。11.HashMap使用哪種方法來解決哈希沖突（哈希碰撞）？答：HashMap使用鏈表和紅黑樹來解決哈希沖突，詳見本文put()方法的執(zhí)行過程。12.HashMap的擴容為什么是2^n？答：這樣做的目的是為了讓散列更加均勻，從而減少哈希碰撞，以提供代碼的執(zhí)行效率。13.有哈希沖突的情況下HashMap如何取值？答：如果有哈希沖突，HashMap會循環(huán)鏈表中的每項key進行equals對比，返回對應的元素。相關源碼如下：do{

if(e.hash==hash&&

((k=e.key)==key||(key!=null&&key.equals(k))))//比對時還是先看hash值是否相同、再看地址或equals

returne;//如果當前節(jié)點e的鍵對象和key相同，那么返回e

}while((e=e.next)!=null);//看看是否還有下一個節(jié)點，如果有，繼續(xù)下一輪比對，否則跳出循環(huán)14.以下程序會輸出什么結果？classPerson{

privateIntegerage;

publicbooleanequals(Objecto){

if(o==null||!(oinstanceofPerson)){

returnfalse;

}else{

returnthis.getAge().equals(((Person)o).getAge());

}

}

publicinthashCode(){

returnage.hashCode();

}

publicPerson(intage){

this.age=age;

}

publicvoidsetAge(intage){

this.age=age;

}

publicIntegergetAge(){

returnage;

}

publicstaticvoidmain(String[]args){

HashMap<Person,Integer>hashMap=newHashMap<>();

Personperson=newPerson(18);

hashMap.put(person,1);

System.out.println(hashMap.get(newPerson(18)));

}

}答：1

題目解析：因為Person重寫了equals和hashCode方法，所有person對象和newPerson(18)的鍵值相同，所以結果就是1。15.為什么重寫equals()時一定要重寫hashCode()？答：因為Java規(guī)定，如果兩個對象equals比較相等（結果為true），那么調用hashCode也必須相等。如果重寫了equals()但沒有重寫hashCode()，就會與規(guī)定相違背，比如以下代碼（故意注釋掉hashCode方法）：classPerson{

privateIntegerage;

publicbooleanequals(Objecto){

if(o==null||!(oinstanceofPerson)){

returnfalse;

}else{

returnthis.getAge().equals(((Person)o).getAge());

}

}

//publicinthashCode(){

//returnage.hashCode();

//}

publicPerson(intage){

this.age=age;

}

publicvoidsetAge(intage){

this.age=age;

}

publicIntegergetAge(){

returnage;

}

publicstaticvoidmain(String[]args){

Personp1=newPerson(18);

Personp2=newPerson(18);

System.out.println(p1.equals(p2));

System.out.println(p1.hashCode()+":"+p2.hashCode());

}

}執(zhí)行的結果：true

21685669:2133927002如果重寫hashCode()之后，執(zhí)行的結果是：true

18:18這樣就符合了Java的規(guī)定，因此重寫equals()時一定要重寫hashCode()。16.HashMap在JDK7多線程中使用會導致什么問題？答：HashMap在JDK7中會導致死循環(huán)的問題。因為在JDK7中，多線程進行HashMap擴容時會導致鏈表的循環(huán)引用，這個時候使用get()獲取元素時就會導致死循環(huán)，造成CPU100%的情況。17.HashMap在JDK7和JDK8中有哪些不同？答：HashMap在JDK7和JDK8的主要區(qū)別如下。存儲結構：JDK7使用的是數(shù)組+鏈表；JDK8使用的是數(shù)組+鏈表+紅黑樹。存放數(shù)據(jù)的規(guī)則：JDK7無沖突時，存放數(shù)組；沖突時，存放鏈表；JDK8在沒有沖突的情況下直接存放數(shù)組，有沖突時，當鏈表長度小于8時，存放在單鏈表結構中，當鏈表長度大于8時，樹化并存放至紅黑樹的數(shù)據(jù)結構中。插入數(shù)據(jù)方式：JDK7使用的是頭插法（先將原位置的數(shù)據(jù)移到后1位，再插入數(shù)據(jù)到該位置）；JDK8使用的是尾插法（直接插入到鏈表尾部/紅黑樹）?？偨Y通過本文可以了解到：Map的常用實現(xiàn)類Hashtable是Java早期的線程安全的哈希表實現(xiàn)；HashMap是最常用的哈希表實現(xiàn)，但它是非線程安全的，可使用ConcurrentHashMap替代；TreeMap是基于紅黑樹的一種提供順序訪問的哈希表實現(xiàn)；LinkedHashMap是HashMap的一個子類，保存了記錄的插入順序，可在遍歷時保持與插入一樣的順序。HashMap在JDK7可能在擴容時會導致鏈表的循環(huán)引用而造成CPU100%，HashMap在JDK8時數(shù)據(jù)結構變更為：數(shù)組+鏈表+紅黑樹的存儲方式，在沒有沖突的情況下直接存放數(shù)組，有沖突，當鏈表長度小于8時，存放在單鏈表結構中，當鏈表長度大于8時，樹化并存放至紅黑樹的數(shù)據(jù)結構中。 如何輕松獲得Offer你好，我是王磊，某上市公司技術研發(fā)經(jīng)理，前奇虎360員工，有著10余年的編程工作經(jīng)驗，目前主要負責新員工技術面試和構建企業(yè)技術架構的相關事宜。隨著面試過的人數(shù)增加，我發(fā)現(xiàn)面試者們暴露出了技術方面的很多問題，為了讓更多面試者少走一些彎路，也為了讓企業(yè)能招到合適的技術人才，于是就誕生了這個專欄。為了寫好這個專欄內容，我先后拜訪了一二十家互聯(lián)網(wǎng)公司，與不同的面試官和面試者進行面對面探討，深入了解了企業(yè)對于面試者的要求和常見的Java面試題型。之后我花了大半年的時間，結合自己4年多作為面試官的經(jīng)歷，把這些內容整理成文，用大約10萬字的內容對Java的核心知識點和常見的500多道面試題，做了詳細的介紹，也就是本專欄中你所看到的全部內容，希望對你能有所幫助。為什么要學這個專欄內容？「因為它能為你贏得面試的主動權，讓你獲得更多的Offer。」從業(yè)十多年，我從面試者變成面試官，在Java面試上積累了比較豐富的經(jīng)驗。其實，很多面試者在搜集面試資料的時候都踩過一些“坑”，你是不是也遇到過：免費搜索的面試題，內容不全面，這就算了，有時候答案都不準確；很多培訓機構提供的面試寶典內容雖然不少，但深度不夠，且面試題過于老舊脫離了企業(yè)實際需要；還有很多付費的面試題存在濫竽充數(shù)，提供了很多沒有價值的面試題，錢花了，干貨沒學到；市面上大部分面試題只講了基礎概念，沒有提供題目解析和示例代碼，不利于讀者真正的掌握背后的原理，只能死記硬背，且容易忘記。為了規(guī)避這些“坑”，我跑了很多家互聯(lián)網(wǎng)公司，來確認Java面試中實際考察的高頻知識點和常見題型。可是有了第一手素材后，我要如何讓大家真正從我的講解中學到干貨、用到實處呢？經(jīng)過反復驗證，我才設計了如下的內容講述模式。第一，500+面試題詳解。如果你是還沒走入職場的新人，我會為你提供完整的Java技術棧講解，以及最新、最全、最實用的500多道Java面試題詳解。第二，10萬字Java核心知識點梳理。本專欄的每一篇內容，都采用的是「核心知識點+N道相關面試題」的模式，讓你不單能應付面試，還能學到更多的Java核心知識。第三，技術、面試搭配平衡，不但讓你學到心里，還助你展示出來。面對目前技術市場的相對冷淡和一個職位多個應聘者競爭的現(xiàn)狀，面試者們只有掌握更多Java核心技能和面試理論知識，才能在眾多面試者中脫穎而出。本專欄每篇文章大致分為兩個部分：Java核心點介紹+相關面試題詳解，這兩部分內容相輔相成，前面的核心知識點介紹讓后面的面試題更容易理解，后面的面試題加深了讀者對于Java核心點的掌握。如此一來，讓你所學及所用，不僅能夠應付面試，更能學習到更多有價值的Java技術點，讓你在面試中和工作中都能展示