Map接口的實(shí)現(xiàn)類有HashMap，TreeMap的猛，HashTable安皱，ConcurrentHashMap
1.HashMap：
首先是HashMap的實(shí)現(xiàn)原理，我是參考的這兩篇博客：深入Java集合學(xué)習(xí)系列：HashMap的實(shí)現(xiàn)原理认然，Jdk1.8中的HashMap實(shí)現(xiàn)原理
下面來記述一下HashMap中的重點(diǎn)：
1.在jdk1.8之前采用數(shù)組+鏈表的方式實(shí)現(xiàn)补憾，1.8之后采用數(shù)組+鏈表+紅黑樹(鏈表長(zhǎng)度大于8時(shí))實(shí)現(xiàn)
2.HashMap中的參數(shù)：threshold(最多能容納的鍵值對(duì)數(shù)量)，loadFactory(閥值,threshold=length*loadfactory)卷员，modcount(記錄HashMap內(nèi)部結(jié)構(gòu)發(fā)生變化的次數(shù))盈匾，size(實(shí)際存在的鍵值對(duì)數(shù)量)
3.HashMap的工作原理？答：通過hash的方法毕骡，通過put和get獲取和存儲(chǔ)對(duì)象削饵。在存儲(chǔ)對(duì)象時(shí)岩瘦，將鍵值對(duì)傳給put方法，它調(diào)用hashCode計(jì)算hash值從而得到bucket位置窿撬，進(jìn)一步存儲(chǔ)启昧。獲取對(duì)象時(shí)，將key傳給get方法劈伴，它調(diào)用hashCode計(jì)算hash值從而得到bucket位置箫津，當(dāng)hashCode相同即發(fā)生沖突時(shí)，進(jìn)一步調(diào)用equals方法來確定鍵值對(duì)(如果hashCode相對(duì)宰啦，equals不一定相等苏遥；equals相等hashCode一定相等)
4.你知道get和put的原理嗎？equals()和hashCode()的都有什么作用赡模？答：通過key的hashCode進(jìn)行hash田炭，并計(jì)算下標(biāo)(n-1 & hash)，從而獲得bucket的位置漓柑，如果產(chǎn)生碰撞教硫，則利用key.equals方法去鏈表或樹中查找對(duì)應(yīng)的節(jié)點(diǎn)
5.你知道hash的實(shí)現(xiàn)嗎？為什么要這樣實(shí)現(xiàn)辆布？答：在java1.8中瞬矩，通過hashCode的高16位異或低16位來實(shí)現(xiàn)的，為什么要這么設(shè)計(jì)呢锋玲？這樣可以做到在bucket的n比較小的時(shí)候也能保證高低bit能參與到hash計(jì)算中景用。
6.如果HashMap的大小超過了負(fù)載因子(load factor)定義的容量，怎么辦惭蹂？答：如果超過了負(fù)載因子(0.75)伞插，則會(huì)resize一個(gè)原來兩倍長(zhǎng)度的hashMap，并重新進(jìn)行hash計(jì)算盾碗。
7.你了解重新調(diào)整HashMap大小存在什么問題嗎媚污？答：當(dāng)重新調(diào)整hash的時(shí)候確實(shí)存在條件競(jìng)爭(zhēng)，如果兩個(gè)線程都發(fā)現(xiàn)hashMap需要調(diào)整大小廷雅，他們會(huì)同時(shí)試著調(diào)整大小耗美，就會(huì)發(fā)生沖突，所以在多線程環(huán)境下使用currentHashMap來代替hashMap
8.為什么String, Interger這樣的wrapper類適合作為鍵航缀？答：因?yàn)镾tring是final類型的商架，是不可變的，其他包裝類也有這樣的特點(diǎn)谬盐。為了要計(jì)算hashCode甸私，就要防止鍵值改變诚些，如果鍵值在放入時(shí)和獲取時(shí)返回不同hashCode的話就不能從hashMap中找到你想要的對(duì)象飞傀，不可變性還有其他優(yōu)點(diǎn)如線程安全皇型。
9.hashMap的長(zhǎng)度為什么是2的冪次方？答：一：通過將key的hash值和length-1進(jìn)行與運(yùn)算砸烦，實(shí)現(xiàn)了key的定位弃鸦，如果長(zhǎng)度為2的冪次方，那么length-1轉(zhuǎn)化為二進(jìn)制必定為11111....的形式幢痘，和h的二進(jìn)制與操作效率會(huì)非常高并且不會(huì)造成空間浪費(fèi)唬格。如果不是2的冪次方，例如length為15颜说，則length-1就是14购岗，二進(jìn)制位1110，再和h與操作最后一位都是0门粪，而0001,0011,0101等二進(jìn)制最后一位為1的情況就不能放置元素喊积，空間浪費(fèi)很大。
10.為什么JDK1.8之后采用紅黑樹而不是鏈表來處理沖突玄妈？答：遍歷鏈表的時(shí)間復(fù)雜度為O(n)乾吻，在JDK1.8之后引入紅黑樹，查找的時(shí)間復(fù)雜度為O(logn)
11.開放地址法：
基本思想：當(dāng)?shù)刂钒l(fā)生沖突時(shí)拟蜻，繼續(xù)探測(cè)散列表的其他存儲(chǔ)單元绎签，直到找到空位置為止
12.拉鏈法的優(yōu)勢(shì)與缺點(diǎn)：
優(yōu)勢(shì)：
1. 拉鏈法處理沖突簡(jiǎn)單，無堆積現(xiàn)象酝锅，即非同義詞絕不會(huì)發(fā)生沖突诡必，因此平均查找長(zhǎng)度較短
2. 由于拉鏈法中各鏈表上的節(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的，故它更適合于造表前無法確定表長(zhǎng)的情況
3. 在拉鏈法構(gòu)造的散列表中搔扁，刪除節(jié)點(diǎn)的操作易于實(shí)現(xiàn)擒权，只要簡(jiǎn)單的刪去鏈表上相應(yīng)的節(jié)點(diǎn)即可
缺點(diǎn)：
1. 指針需要額外的空間(相對(duì)于開放地址法而言，因?yàn)殚_放地址法中不需要使用鏈表)
2.HashTable:
hashTable主要看的這篇文章：【源碼】Hashtable源碼剖析
1.HashTable如何保證線程安全阁谆？答：HashTable底層使用synchronized來實(shí)現(xiàn)線程安全碳抄，所以hashTable在線程競(jìng)爭(zhēng)激烈的情況下效率會(huì)非常低。
2.hashMap與hashTable的區(qū)別场绿？答：一：hashTable使用synchronized方法來實(shí)現(xiàn)同步剖效，線程安全；hashMap未使用同步線程不安全焰盗。二：hashTable不允許null值璧尸，hashMap允許null值。三：hashtable數(shù)組長(zhǎng)度默認(rèn)為11熬拒，增長(zhǎng)方式為2*old+2爷光，hashMap數(shù)組默認(rèn)長(zhǎng)度為16，增長(zhǎng)方式為2*old澎粟。四：hash值的使用方式不同蛀序，hashTable是直接使用對(duì)象的hashCode欢瞪，hashMap是重新計(jì)算hash值在進(jìn)行與操作。
3.ConcurrentHashMap：
1.ConcurrentHashMap的具體實(shí)現(xiàn)知道嗎徐裸？答：一：該類包含兩個(gè)靜態(tài)內(nèi)部?jī)?nèi)HashEntry和Segment遣鼓；前者用來封裝映射表的鍵值對(duì)，后者用來充當(dāng)鎖的角色重贺。二：Segemnt是一種可重入鎖骑祟，每個(gè)Segment守護(hù)一個(gè)hashEntry數(shù)組中的元素，當(dāng)對(duì)hashEntry中的元素進(jìn)行修改時(shí)必須先獲得對(duì)應(yīng)的Segment鎖气笙。
2.ConcurrentHashMap如何保證線程安全次企？答：HashTable在多線程激烈環(huán)境下效率低下的原因就是它對(duì)所有的數(shù)據(jù)都加了鎖，所有線程競(jìng)爭(zhēng)用一把鎖潜圃。ConcurrentHashMap使用分段鎖技術(shù)抒巢，將數(shù)據(jù)分成一段一段存儲(chǔ)，然后給每一段數(shù)據(jù)分配一把鎖秉犹，當(dāng)一個(gè)線程占用鎖訪問其中一段數(shù)據(jù)時(shí)蛉谜，其他段的數(shù)據(jù)也能被其他線程訪問。
3.ConcurrentHashMap與hashTable的區(qū)別崇堵？答：ConcurrentHashMap 結(jié)合了 HashMap 和 HashTable 二者的優(yōu)勢(shì)型诚。HashMap 沒有考慮同步，hashtable 考慮了同步的問題鸳劳。但是 hashtable 在每次同步執(zhí)行時(shí)都要鎖住整個(gè)結(jié)構(gòu)狰贯。 ConcurrentHashMap 鎖的方式是稍微細(xì)粒度的。 ConcurrentHashMap 將 hash 表分為 16 個(gè)桶（默認(rèn)值）赏廓，諸如 get,put,remove 等常用操作只鎖當(dāng)前需要用到的桶涵紊。
4.ConcurrentHashMap如何做到Get方法不用加鎖的(HashTable的Get方法需要加鎖)？答：原因是get方法里使用的變量是volatile類型幔摸，能夠在線程之間保持可見性摸柄，線程不會(huì)讀到過期的值，但是只能被單線程寫既忆。之所以不會(huì)讀到過期的值是因?yàn)閖ava內(nèi)存模型的happen-before原則驱负，讀volatile字段的寫操作優(yōu)于讀操作，即使兩個(gè)線程同時(shí)修改和讀取同一變量也會(huì)拿到最新的值患雇。
5.ConcurrentHashMap的put操作跃脊？答：put方法里需要對(duì)共享變量進(jìn)行寫入操作，所以為了線程安全苛吱，在操作共享變量時(shí)必須得加鎖酪术。Put方法首先定位到Segment，然后在Segment里進(jìn)行插入操作翠储。插入操作需要經(jīng)歷兩個(gè)步驟绘雁，第一步判斷是否需要對(duì)Segment里的HashEntry數(shù)組進(jìn)行擴(kuò)容橡疼，第二步定位添加元素的位置然后放在HashEntry數(shù)組里。
4.其他的關(guān)于集合的一些知識(shí)點(diǎn)：
1.ArrayList VS Vector：
ArrayList和Vector都實(shí)現(xiàn)了list接口咧七，都是數(shù)組實(shí)現(xiàn)衰齐，Vector線程安全任斋，arrayList線程不安全
Arraylist初始容量為10继阻，加載因子為0.5，擴(kuò)容增量：原容量的0.5倍+1废酷；Vector初始容量為10瘟檩，加載因子為1，擴(kuò)容增量：原容量的1倍澈蟆。
2.ArrayList VS LinkedList：
ArrayList底層是數(shù)組實(shí)現(xiàn)墨辛，適合查找和在末尾插入刪除；LinkedList底層使用雙向鏈表實(shí)現(xiàn)趴俘，適合中間插入和刪除睹簇。
3.集合中常見的接口：總共有兩大接口，Collection和Map寥闪，一個(gè)元素集合太惠，一個(gè)是鍵值對(duì)集合；其中List和Set實(shí)現(xiàn)了Collection接口疲憋，一個(gè)是有序元素集合凿渊，一個(gè)是無序元素集合；而ArrayList和LinkedList實(shí)現(xiàn)了List接口缚柳；HashMap和HashTable實(shí)現(xiàn)了Map接口埃脏，HashTable是線程安全的，HashMap不是線程安全的秋忙。
