一乡话、當兩個對象的 hashCode 相同會發(fā)生什么荞估？

因為 hashCode 相同貌笨，不一定就是相等的(equals方法比較)弱判，所以兩個對象所在數組的下標相同，"碰撞"就此發(fā)生锥惋。又因為 HashMap 使用鏈表存儲對象昌腰，這個 Node 會存儲到鏈表中。

二膀跌、說說 hash 的實現遭商。為什么要這樣實現？

JDK 1.8 中捅伤，是通過 hashCode() 的高 16 位異或低 16 位實現的：(h = k.hashCode()) ^ (h >>> 16)劫流。主要是從速度、功效和質量來考慮的，減少系統(tǒng)的開銷祠汇，也不會造成因為高位沒有參與下標的計算仍秤，從而引起的碰撞。

三可很、為什么要用異或運算符诗力？

保證了對象的 hashCode 的 32 位值只要有一位發(fā)生改變，整個 hash() 返回值就會改變我抠。盡可能的減少碰撞姜骡。

四、HashMap 的 table 的容量如何確定屿良？loadFactor 是什么？該容量如何變化惫周？這種變化會帶來什么問題尘惧？

①table 數組大小是由 capacity 這個參數確定的，默認是16递递，也可以構造時傳入喷橙，最大限制是1<<30；
②loadFactor 是裝載因子登舞，主要目的是用來確認table 數組是否需要動態(tài)擴展贰逾，默認值是0.75，比如table 數組大小為 16菠秒，裝載因子為 0.75 時疙剑，threshold 就是12，當 table 的實際大小超過 12 時践叠，table就需要動態(tài)擴容言缤；
③擴容時，調用 resize()禁灼，將 table 長度變?yōu)樵瓉淼膬杀?注意是 table 長度管挟，而不是 threshold)
④如果數據很大的情況下，擴展時將會帶來性能的損失弄捕，在性能要求很高的地方僻孝，這種損失很可能很致命。

五守谓、HashMap中put()的過程穿铆？

①調用哈希函數獲取Key對應的hash值，再計算其數組下標分飞；
②如果沒有出現哈希沖突悴务，則直接放入數組；如果出現哈希沖突，則以鏈表的方式放在鏈表后面讯檐；
③如果鏈表長度超過閥值( TREEIFY THRESHOLD==8)羡疗，就把鏈表轉成紅黑樹，鏈表長度低于6别洪，就把紅黑樹轉回鏈表;
④如果結點的key已經存在叨恨，則替換其value即可；
⑤如果集合中的鍵值對大于12挖垛，調用resize()進行數組擴容痒钝。”

六痢毒、數組擴容的過程送矩？

創(chuàng)建一個新的數組，其容量為舊數組的兩倍哪替，并重新計算舊數組中結點的存儲位置栋荸。結點在新數組中的位置只有兩種，原下標位置或原下標+舊數組的大小凭舶。

七晌块、拉鏈法導致的鏈表過深問題為什么不用二叉查找樹代替，而選擇紅黑樹帅霜？為什么不一直使用紅黑樹匆背？

之所以選擇紅黑樹是為了解決二叉查找樹的缺陷，二叉查找樹在特殊情況下會變成一條線性結構(這就跟原來使用鏈表結構一樣了身冀，造成很深的問題)钝尸，遍歷查找會非常慢。而紅黑樹在插入新數據后可能需要通過左旋搂根，右旋蝶怔、變色這些操作來保持平衡，引入紅黑樹就是為了查找數據快兄墅，解決鏈表查詢深度的問題踢星，我們知道紅黑樹屬于平衡二叉樹，但是為了保持“平衡”是需要付出代價的隙咸，但是該代價所損耗的資源要比遍歷線性鏈表要少沐悦，所以當長度大于8的時候，會使用紅黑樹五督，如果鏈表長度很短的話藏否，根本不需要引入紅黑樹，引入反而會慢充包。

八副签、說說對紅黑樹的見解遥椿？

①每個節(jié)點非紅即黑
②根節(jié)點總是黑色的
③如果節(jié)點是紅色的，則它的子節(jié)點必須是黑色的(反之不一定)
④每個葉子節(jié)點都是黑色的空節(jié)點(NIL節(jié)點)
⑤從根節(jié)點到葉節(jié)點或空子節(jié)點的每條路徑淆储，必須包含相同數目的黑色節(jié)點(即相同的黑色高度)

九冠场、jdk8中對HashMap做了哪些改變？

①在java 1.8中本砰，如果鏈表的長度超過了8碴裙，那么鏈表將轉換為紅黑樹。(桶的數量必須大于64点额，小于64的時候只會擴容)舔株。
②發(fā)生hash碰撞時，java 1.7 會在鏈表的頭部插入还棱，而java 1.8會在鏈表的尾部插入载慈。
③在java 1.8中，Entry被Node替代(換了一個馬甲)珍手。

十娃肿、LinkedHashMap，TreeMap 有什么區(qū)別珠十？

LinkedHashMap 保存了記錄的插入順序，在用 Iterator 遍歷時凭豪，先取到的記錄肯定是先插入的焙蹭；遍歷比 HashMap 慢；
TreeMap 實現 SortMap 接口嫂伞，能夠把它保存的記錄根據鍵排序(默認按鍵值升序排序孔厉，也可以指定排序的比較器)

十一、HashMap & TreeMap & LinkedHashMap 使用場景帖努？

一般情況下撰豺，使用最多的是 HashMap。
HashMap：在 Map 中插入拼余、刪除和定位元素時污桦；
TreeMap：在需要按自然順序或自定義順序遍歷鍵的情況下；
LinkedHashMap：在需要輸出的順序和輸入的順序相同的情況下匙监。

十二凡橱、HashMap 和 HashTable 有什么區(qū)別？

①HashMap 是線程不安全的亭姥，HashTable 是線程安全的稼钩；
②由于線程安全，所以 HashTable 的效率比不上 HashMap达罗；
③HashMap 最多只允許一條記錄的鍵為null坝撑，允許多條記錄的值為null，而 HashTable不允許；
④HashMap 默認初始化數組的大小為16巡李，擴容時擴大兩倍抚笔。HashTable 為 11，擴容時擴大兩倍+1击儡；
⑤HashMap 需要重新計算 hash 值塔沃，而 HashTable 直接使用對象的 hashCode。

十三阳谍、同樣是線程安全蛀柴，ConcurrentHashMap 與 HashTable 在線程同步上有何不同？

ConcurrentHashMap 類是 Java并發(fā)包 java.util.concurrent 中提供的一個線程安全且高效的 HashMap 實現矫夯。在 JDK 1.7 中采用分段鎖的方式鸽疾；JDK 1.8 中直接采用了CAS(無鎖算法)+ synchronized。
HashTable 是使用 synchronized 關鍵字加鎖的原理(就是對對象加鎖)训貌。

十四制肮、HashMap 和 ConcurrentHashMap 的區(qū)別

在JDK1.7中ConcurrentHashMap底層采用分段數組+鏈表的方式實現。在JDK1.8中ConcurrentHashMap與JDK1.8中的HashMap底層數據結構一樣递沪，都是采用數組+鏈表或者數組+紅黑樹的方式實現豺鼻。這二者底層數據結構都是以數組為主體的。線程安全：HashMap是線程不安全的款慨，ConcurrentHashMap是線程安全的儒飒。另外，HashMap 的鍵值對允許有null檩奠，但是ConCurrentHashMap 都不允許桩了。

十五、針對 ConcurrentHashMap 鎖機制具體分析(JDK 1.7和JDK 1.8)埠戳？

JDK 1.7 中井誉，采用分段鎖的機制，實現并發(fā)的更新操作整胃，底層采用數組+鏈表的存儲結構颗圣，包括兩個核心靜態(tài)內部類 Segment 和 HashEntry。
①Segment 繼承 ReentrantLock(可重入鎖) 用來充當鎖的角色屁使，每個 Segment 對象守護每個散列映射表的若干個桶欠啤；
②HashEntry 用來封裝映射表的鍵-值對；
③每個桶是由若干個 HashEntry 對象鏈接起來的鏈表屋灌。

JDK 1.8 中洁段，采用Node + CAS + Synchronized來保證并發(fā)安全。取消類 Segment共郭，直接用 table 數組存儲鍵值對祠丝；當 HashEntry 對象組成的鏈表長度超過 TREEIFY_THRESHOLD 時疾呻，鏈表轉換為紅黑樹，提升性能写半。底層變更為數組 + 鏈表 + 紅黑樹岸蜗。

十六、JDK 1.8的ConcurrentHashMap叠蝇，為什么要使用內置鎖 synchronized 來代替重入鎖 ReentrantLock璃岳？

①粒度降低了；
② 官方對synchronized進行了優(yōu)化和升級悔捶，使得synchronized不那么“重”了铃慷，而且基于 JVM 的 synchronized 優(yōu)化空間更大，更加自然蜕该。
③在大量的數據操作下犁柜，對于 JVM 的內存壓力，基于 API 的 ReentrantLock 會開銷更多的內存堂淡。

十七馋缅、ConcurrentHashMap 簡單介紹以及put()和get()的工作流程是怎樣的？

?1??重要的常量：
private transient volatile int sizeCtl;
當為負數時绢淀，-1 表示正在初始化萤悴，-N 表示 N - 1 個線程正在進行擴容；
當為 0 時皆的，表示 table 還沒有初始化覆履；
當為其他正數時，表示初始化或者下一次進行擴容的大小祭务。

2??數據結構：
Node 是存儲結構的基本單元，繼承 HashMap 中的 Entry怪嫌，用于存儲數據义锥；
TreeNode 繼承 Node，但是數據結構換成了二叉樹結構岩灭，是紅黑樹的存儲結構拌倍，用于紅黑樹中存儲數據；
TreeBin 是封裝 TreeNode 的容器噪径，提供轉換紅黑樹的一些條件和鎖的控制柱恤。

3??存儲對象時(put方法)：

如果沒有初始化，就調用 initTable() 來進行初始化找爱。
如果沒有 hash 沖突就直接 CAS 無鎖插入梗顺。
如果需要擴容，就先進行擴容车摄，擴容為原來的兩倍寺谤。
如果存在 hash 沖突仑鸥，就加鎖來保證線程安全，兩種情況：一種是鏈表形式就直接遍歷到尾端插入变屁，一種是紅黑樹就按照紅黑樹結構插入眼俊。
如果該鏈表的數量大于閥值 8，就要先轉換成紅黑樹的結構粟关，break 再一次進入循環(huán)疮胖。
如果添加成功就調用 addCount() 統(tǒng)計 size，并且檢查是否需要擴容闷板。
注意：在并發(fā)情況下ConcurrentHashMap會調用多個工作線程一起幫助擴容澎灸，這樣效率會更高。

4??擴容方法 transfer()：默認容量為 16蛔垢，擴容時击孩，容量變?yōu)樵瓉淼膬杀丁?br> helpTransfer()：調用多個工作線程一起幫助進行擴容，這樣的效率就會更高鹏漆。

5??獲取對象時(get方法)：

計算 hash 值巩梢，定位到該 table 索引位置，如果頭節(jié)點符合條件則直接返回key對應的value艺玲。
2.如果遇到擴容時括蝠，會調用標記正在擴容結點 ForwardingNode.find()，查找該結點饭聚，匹配就返回忌警；
3.以上都不符合的話，就往下遍歷結點秒梳，匹配就返回法绵，否則最后就返回 null。
注意：其實get()的流程跟HashMap基本是一樣的酪碘。put()的流程只是比HashMap多了一些保證線程安全的操作而已朋譬。

十八、ConcurrentHashMap 的并發(fā)度是什么兴垦？

程序運行時能夠同時更新 ConccurentHashMap 且不產生鎖競爭的最大線程數徙赢。默認為 16，且可以在構造函數中設置探越。當用戶設置并發(fā)度時狡赐，ConcurrentHashMap 會使用大于等于該值的最小2冪指數作為實際并發(fā)度(假如用戶設置并發(fā)度為17，實際并發(fā)度則為32)

十九钦幔、為什么 ConcurrentHashMap 比 HashTable 效率要高枕屉？

ConcurrentHashMap的效率要高于HashTable，因為HashTable是使用一把鎖鎖住整個鏈表結構從而實現線程安全鲤氢，多個線程競爭一把鎖搀庶，容易阻塞拐纱。而ConcurrentHashMap的鎖粒度更低：
①JDK 1.7 中使用分段鎖(ReentrantLock + Segment + HashEntry)，相當于把一個 HashMap 分成多個段哥倔，每段分配一把鎖秸架，這樣支持多線程訪問。鎖粒度：基于 Segment咆蒿，包含多個 HashEntry东抹。
②JDK 1.8 中使用 CAS(無鎖算法) + synchronized + Node + 紅黑樹。鎖粒度：Node(首結點)(實現 Map.Entry<K,V>)沃测。鎖粒度降低了缭黔。

二十、HashTable和ConcurrentHashMap的鎖機制(重點)

1??HashTable中的鎖機制

HashTab是使用Synchronized來實現線程安全的蒂破，是使用一把鎖鎖住整個鏈表結構馏谨，效率非常低。當有一個線程訪問同步方法的時候附迷，其他線程是訪問不了的惧互，其他線程可能會被阻塞或者進入輪詢狀態(tài)。如果有一個線程正在執(zhí)行put()操作的時候喇伯，其他線程是不可以進行put()操作的喊儡，也不可以進行get()操作，并發(fā)線程越多稻据，競爭越激烈艾猜，效率越低下。

2??ConcurrentHashMap中的鎖機制
①ConcurrentHashMap在JDK1.7中的分段鎖機制：
對整個數組進行分段(每段都是由若干個hashEntry對象組成的鏈表)捻悯，每個分段都有一個Segment分段鎖(繼承ReentrantLock分段鎖)匆赃，每個Segment分段鎖只會鎖住它鎖守護的那一段數據，多線程訪問不同數據段的數據今缚，就不會存在競爭算柳，從而提高了并發(fā)的訪問率。

②ConcurrentHashMap在JDK1.8中的鎖機制：
ConcurrentHashMap在JDK1.8中采用Node+CAS+Synchronized實現線程安全荚斯，取消了segment分段鎖埠居，直接使用Table數組存儲鍵值對（與1.8中的HashMap一樣）查牌，主要是使用Synchronized+CAS的方法來進行并發(fā)控制事期。在put()的時候如果CAS失敗就說明存在競爭，會進行自旋纸颜。

二十一兽泣、ConcurrentHashMap的get()需要加鎖嗎？

不需要胁孙，get操作可以無鎖是由于Node的元素val和指針next是用volatile修飾的唠倦，在多線程環(huán)境下線程A修改結點的val或者新增節(jié)點的時候是對線程B可見的称鳞。

二十二、ConcurrentHashMap中的key和value可以為null嗎稠鼻？為什么冈止？

不可以，因為源碼中進行put()操作的時候候齿，如果key為null或者value為null熙暴，會拋出NullPointerException空指針異常。為什么這樣設計呢慌盯？

如果ConcurrentHashMap中存在一個key對應的value是null周霉，那么當調用map.get(key)的時候，必然會返回null亚皂，那么這個null就有兩個意思：
① 這個key從來沒有在map中映射過俱箱，也就是不存在這個key
②這個key是真實存在的，只是在設置key的value值的時候灭必，設置為null了

這個二義性在非線程安全的HashMap中可以通過map.containsKey(key)來判斷狞谱，如果返回true，說明key存在只是對應的value值為空厂财。如果返回false芋簿，說明這個key沒有在map中映射過。這樣是為什么HashMap可以允許鍵值為null的原因璃饱，但是ConcurrentHashMap只用這個判斷是判斷不了二義性的与斤。為什么ConcurrentHashMap判斷不了呢？

此時如果有A荚恶、B兩個線程撩穿，A線程調用ConcurrentHashMap.get(key)返回null，但是不知道這個null是因為key沒有在map中映射還是本身存的value值就是null谒撼。假設有一個key沒有在map中映射過食寡，也就是map中不存在這個key，此時調用ConcurrentHashMap.containsKey(key)去做一個判斷廓潜，期望的返回結果是false抵皱。但是恰好在A線程get(key)之后，調用constainsKey(key)之前B線程執(zhí)行了ConcurrentHashMap.put(key,null)辩蛋，那么當A線程執(zhí)行完containsKey(key)之后得到的結果是true呻畸，與預期的結果就不相符了。

至于ConcurrentHashMap中的key為什么也不能為null的問題悼院，ConcurrentHashMap的作者Doug Lea認為map中允許鍵值為null是一種不合理的設計伤为，HashMap雖然可以判斷二義性，但是Doug Lea仍然覺得這樣設計是不合理的据途。

二十三绞愚、只有 HashMap 可操作 null

import java.util.HashMap;
import java.util.Hashtable;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public class mapDemo {
    public static void main(String[] args) {
        HashMap map = new HashMap();
        map.put(null, null);
        map.get(null);
        map.remove(null);
        Map table = new Hashtable();
//        table.put(null, "value");//NPE
//        table.put("key",null);//NPE
//        table.get(null);//NPE
//        table.remove(null);//NPE
        ConcurrentHashMap cm = new ConcurrentHashMap();
//        cm.put(null, "value");//NPE
//        cm.put("key", null);//NPE
//        cm.get(null);//NPE
//        cm.remove(null);//NPE
    }
}

Map 面試