1：hashmap簡介（如下凿跳，數(shù)組-鏈表形式）
HashMap的存儲(chǔ)結(jié)構(gòu)
圖中，紫色部分即代表哈希表晋控，也稱為哈希數(shù)組（默認(rèn)數(shù)組大小是16峡谊，每對(duì)key-value鍵值對(duì)其實(shí)是存在map的內(nèi)部類entry里的）茫虽，數(shù)組的每個(gè)元素都是一個(gè)單鏈表的頭節(jié)點(diǎn)，跟著的綠色鏈表是用來解決沖突的既们，如果不同的key映射到了數(shù)組的同一位置處濒析，就將其放入單鏈表中。
2：hashmap原理（即put和get原理）
2.1 put原理
1.根據(jù)key獲取對(duì)應(yīng)hash值：int hash = hash（key.hash.hashcode（））
2.根據(jù)hash值和數(shù)組長度確定對(duì)應(yīng)數(shù)組引int i = indexFor(hash, table.length); 簡單理解就是i = hash值%模以 數(shù)組長度（其實(shí)是按位與運(yùn)算）啥纸。如果不同的key都映射到了數(shù)組的同一位置處号杏，就將其放入單鏈表中。且新來的是放在頭節(jié)點(diǎn)斯棒。
2.2 get原理
1.通過hash獲得對(duì)應(yīng)數(shù)組位置盾致，遍歷該數(shù)組所在鏈表（key.equals（））
3：hashcode相同，沖突怎么辦荣暮？
“頭插法”绰上，放到對(duì)應(yīng)的鏈表的頭部。
3.1：為什么是頭插法（其設(shè)計(jì)原理是什么）渠驼？
因?yàn)镠ashMap的發(fā)明者認(rèn)為，后插入的Entry被查找的可能性更大（因?yàn)間et查詢的時(shí)候會(huì)遍歷整個(gè)鏈表）鉴腻。
4.hashmap的默認(rèn)數(shù)組長度是多少迷扇？
默認(rèn)為16
4.1 為什么？
之所以選擇16爽哎，是為了服務(wù)于從key映射到index的hash算法（看下面）蜓席。
5：hashmap達(dá)到默認(rèn)負(fù)載因子（0.75）怎么辦？
自動(dòng)雙倍擴(kuò)容课锌，擴(kuò)容后重新計(jì)算每個(gè)鍵值對(duì)位置厨内。且長度必須為16或者2的冪次
5.1為啥要16或者2的冪次祈秕？
- 若不是16或者2的冪次，位運(yùn)算的結(jié)果不夠均勻分布雏胃，顯然不符合Hash算法均勻分布的原則请毛。
- 反觀長度16或者其他2的冪，Length-1的值是所有二進(jìn)制位全為1瞭亮，這種情況下方仿，index的結(jié)果等同于HashCode后幾位的值。只要輸入的HashCode本身分布均勻统翩，Hash算法的結(jié)果就是均勻的仙蚜。
6：hashmap是線程安全的嗎？
不是厂汗。
6.2 為什么委粉？
因?yàn)闆]加鎖
6.3 那在并發(fā)時(shí)會(huì)導(dǎo)致什么問題？
hashmap在接近臨界點(diǎn)時(shí)娶桦，若此時(shí)兩個(gè)或者多個(gè)線程進(jìn)行put操作贾节，都會(huì)進(jìn)行resize（擴(kuò)容）和ReHash（為key重新計(jì)算所在位置），而ReHash在并發(fā)的情況下可能會(huì)形成鏈表環(huán)趟紊。
6.4 如何判斷有環(huán)形表氮双？
最優(yōu)：首先創(chuàng)建兩個(gè)指針A和B（在java里就是兩個(gè)對(duì)象引用），同時(shí)指向這個(gè)鏈表的頭節(jié)點(diǎn)霎匈。然后開始一個(gè)大循環(huán)戴差，在循環(huán)體中，讓指針A每次向下移動(dòng)一個(gè)節(jié)點(diǎn)铛嘱，讓指針B每次向下移動(dòng)兩個(gè)節(jié)點(diǎn)暖释，然后比較兩個(gè)指針指向的節(jié)點(diǎn)是否相同。如果相同墨吓，則判斷出鏈表有環(huán)球匕，如果不同，則繼續(xù)下一次循環(huán)帖烘。
理解：此方法也可以用一個(gè)更生動(dòng)的例子來形容：在一個(gè)環(huán)形跑道上亮曹，兩個(gè)運(yùn)動(dòng)員在同一地點(diǎn)起跑，一個(gè)運(yùn)動(dòng)員速度快秘症，一個(gè)運(yùn)動(dòng)員速度慢照卦。當(dāng)兩人跑了一段時(shí)間，速度快的運(yùn)動(dòng)員必然會(huì)從速度慢的運(yùn)動(dòng)員身后再次追上并超過乡摹，原因很簡單役耕，因?yàn)榕艿朗黔h(huán)形的。
7： hashmap 和 hashtable 區(qū)別瞬痘？
線程： 不安全 安全（synchronized修飾）
效率： 更高 略低
數(shù)組默認(rèn)值： 16 11
null值: key-value都允許 不允許（拋異常）
其中key為null的map對(duì)象就在索引為0的位置上
8：那hashmap不安全故慈，hashtable性能又低，怎么辦框全？
用concurrenthashmap察绷，即保證安全，性能又可以保障
8.1 那concurrenthashmap究竟是什么竣况？
整個(gè)ConcurrentHashMap的結(jié)構(gòu)如下：
理解：hashmap是有entry數(shù)組組成，而concurrenthashmap則是Segment數(shù)組丹泉。那Segment是什么呢情萤？Segment本身就相當(dāng)于一個(gè)HashMap對(duì)象。同HashMap一樣摹恨，Segment包含一個(gè)HashEntry數(shù)組筋岛，數(shù)組中的每一個(gè)HashEntry既是一個(gè)鍵值對(duì)，也是一個(gè)鏈表的頭節(jié)點(diǎn)晒哄。
單一的Segment結(jié)構(gòu)如下（是不是看著就是hashmap）：
像這樣的Segment對(duì)象，在ConcurrentHashMap集合中有多少個(gè)呢寝凌？有2的N次方個(gè)柒傻，共同保存在一個(gè)名為segments的數(shù)組當(dāng)中。
可以說较木，ConcurrentHashMap是一個(gè)二級(jí)哈希表红符。在一個(gè)總的哈希表下面，有若干個(gè)子哈希表伐债。（這樣類比理解hashmap）
8.2：那他的put和get方法呢（對(duì)比hashmap的普通和get方法）预侯？
Put方法：
- 1.為輸入的Key做Hash運(yùn)算，得到hash值峰锁。
- 2.通過hash值萎馅，定位到對(duì)應(yīng)的Segment對(duì)象
- 3.獲取可重入鎖
- 4.再次通過hash值，定位到Segment當(dāng)中數(shù)組的具體位置虹蒋。
- 5.插入或覆蓋HashEntry對(duì)象糜芳。
-
6.釋放鎖。
image.png
Get方法：
- 1.為輸入的Key做Hash運(yùn)算魄衅，得到hash值峭竣。
- 2.通過hash值，定位到對(duì)應(yīng)的Segment對(duì)象
- 3.再次通過hash值徐绑，定位到Segment當(dāng)中數(shù)組的具體位置。
由此可見莫辨，和hashmap相比傲茄，ConcurrentHashMap在讀寫的時(shí)候都需要進(jìn)行二次定位毅访。先定位到Segment，再定位到Segment內(nèi)的具體數(shù)組下標(biāo)盘榨。
9： hashmap 和 concurrenthashmap區(qū)別喻粹？
線程： 不安全 安全
10：為啥concurrenthashmap和hashtable都是線程安全，但是前者性能更高
因?yàn)榍罢呤怯玫姆侄捂i草巡，根據(jù)hash值鎖住對(duì)應(yīng)鏈表守呜，當(dāng)hash值不同時(shí)，使其能實(shí)現(xiàn)并行插入山憨，效率更高查乒，而hashtable會(huì)鎖住整個(gè)map
當(dāng)需要put元素的時(shí)候，并不是對(duì)整個(gè)hashmap進(jìn)行加鎖郁竟，而是先通過hashcode來知道他要放在那一個(gè)分段中玛迄，然后對(duì)這個(gè)分段進(jìn)行加鎖，所以當(dāng)多線程put的時(shí)候棚亩，只要不是放在同一個(gè)分段中蓖议，就實(shí)現(xiàn)了真正的并行的插入。
但是讥蟆，在統(tǒng)計(jì)size的時(shí)候勒虾，就是獲取hashmap全局信息的時(shí)候，就需要獲取所有的分段鎖才能統(tǒng)計(jì)瘸彤。
分段鎖的設(shè)計(jì)目的是細(xì)化鎖的粒度修然，當(dāng)操作不需要更新整個(gè)數(shù)組的時(shí)候，就僅僅針對(duì)數(shù)組中的一部分行加鎖操作钧栖。
11.java7的hashmap和java8的hashmap的區(qū)別（1.8做了哪些優(yōu)化）低零？
為了加快查詢效率（因?yàn)間et（）需要遍歷整張鏈表），java8的hashmap引入了紅黑樹結(jié)構(gòu)拯杠，當(dāng)某一鏈表的元素>8時(shí)掏婶，該鏈表就會(huì)轉(zhuǎn)成紅黑樹結(jié)構(gòu)，查詢效率更高
