基于鏈?zhǔn)酱鎯Φ臉涞墓?jié)點可定義如下：

3.1.2 二叉搜索樹BST

在二叉樹中，比較常見的二叉樹有：

• 滿二叉樹

• 完全二叉樹

• 二叉搜索樹

• 紅黑樹

我們重點講解二叉搜索樹和紅黑樹

（1）二叉搜索樹概述

（2）二叉搜索樹-時間復(fù)雜度分析

實際上由于二叉查找樹的形態(tài)各異，時間復(fù)雜度也不盡相同，我畫了幾棵樹我們來看一下插入，查找，刪除的時間復(fù)雜度

查找，的時間復(fù)雜度O(logn)；插入，刪除需要用到查找 所以也是O(logn)；

極端情況下二叉搜索的時間復(fù)雜度

3.1.3 紅黑樹

（1）概述

紅黑樹（Red Black Tree）：也是一種自平衡的二叉搜索樹(BST)，之前叫做平衡二叉B樹（Symmetric Binary B-Tree）

（2）紅黑樹的特質(zhì)

在添加或刪除節(jié)點的時候，如果不符合這些性質(zhì)會發(fā)生旋轉(zhuǎn)，以達到所有的性質(zhì)，保證紅黑樹的平衡

（3）紅黑樹的復(fù)雜度

• 查找：

• 紅黑樹也是一棵BST（二叉搜索樹）樹，查找操作的時間復(fù)雜度為：O(log n)

• 添加：

• 添加先要從根節(jié)點開始找到元素添加的位置，時間復(fù)雜度O(log n)

• 添加完成后涉及到復(fù)雜度為O(1)的旋轉(zhuǎn)調(diào)整操作

• 故整體復(fù)雜度為：O(log n)

• 刪除：

• 首先從根節(jié)點開始找到被刪除元素的位置，時間復(fù)雜度O(log n)

• 刪除完成后涉及到復(fù)雜度為O(1)的旋轉(zhuǎn)調(diào)整操作

• 故整體復(fù)雜度為：O(log n)

3.2 散列表

在HashMap中的最重要的一個數(shù)據(jù)結(jié)構(gòu)就是散列表，在散列表中又使用到了紅黑樹和鏈表

3.2.1 散列表（Hash Table）概述

散列表(Hash Table)又名哈希表/Hash表，是根據(jù)鍵（Key）直接訪問在內(nèi)存存儲位置值（Value）的數(shù)據(jù)結(jié)構(gòu)，它是由數(shù)組演化而來的，利用了數(shù)組支持按照下標(biāo)進行隨機訪問數(shù)據(jù)的特性

舉個例子：

假設(shè)有100個人參加馬拉松，編號是1-100，如果要編程實現(xiàn)根據(jù)選手的編號迅速找到選手信息？

可以把選手信息存入數(shù)組中，選手編號就是數(shù)組的下標(biāo)，數(shù)組的元素就是選手的信息。

當(dāng)我們查詢選手信息的時候，只需要根據(jù)選手的編號到數(shù)組中查詢對應(yīng)的元素就可以快速找到選手的信息，如下圖：

現(xiàn)在需求升級了：

我們目前是把選手的信息存入到數(shù)組中，不過選手的編號不能直接作為數(shù)組的下標(biāo)，不過，可以把選手的選號進行轉(zhuǎn)換，轉(zhuǎn)換為數(shù)值就可以繼續(xù)作為數(shù)組的下標(biāo)了？

轉(zhuǎn)換可以使用散列函數(shù)進行轉(zhuǎn)換

3.2.2 散列函數(shù)和散列沖突

將鍵(key)映射為數(shù)組下標(biāo)的函數(shù)叫做散列函數(shù)?？梢员硎緸?#xff1a;hashValue = hash(key)

散列函數(shù)的基本要求：

• 散列函數(shù)計算得到的散列值必須是≥0的正整數(shù)，因為hashValue需要作為數(shù)組的下標(biāo)。

• 如果key1==key2，那么經(jīng)過hash后得到的哈希值也必相同即：hash(key1) == hash(key2）

• 如果key1 != key2，那么經(jīng)過hash后得到的哈希值也必不相同即：hash(key1) != hash(key2)

實際的情況下想找一個散列函數(shù)能夠做到對于不同的key計算得到的散列值都不同幾乎是不可能的，即便像著名的MD5,SHA等哈希算法也無法避免這一情況，這就是散列沖突(或者哈希沖突，哈希碰撞，就是指多個key映射到同一個數(shù)組下標(biāo)位置)

3.2.3 散列沖突-鏈表法（拉鏈）

在散列表中，數(shù)組的每個下標(biāo)位置我們可以稱之為桶（bucket）或者槽（slot），每個桶(槽)會對應(yīng)一條鏈表，所有散列值相同的元素我們都放到相同槽位對應(yīng)的鏈表中。

簡單就是，如果有多個key最終的hash值是一樣的，就會存入數(shù)組的同一個下標(biāo)中，下標(biāo)中掛一個鏈表存入多個數(shù)據(jù)

3.2.4 時間復(fù)雜度-散列表

1，插入操作，通過散列函數(shù)計算出對應(yīng)的散列槽位，將其插入到對應(yīng)鏈表中即可，插入的時間復(fù)雜度是 O(1)

通過計算就可以找到元素

2，當(dāng)查找、刪除一個元素時，我們同樣通過散列函數(shù)計算出對應(yīng)的槽，然后遍歷鏈表查找或者刪除

• 平均情況下基于鏈表法解決沖突時查詢的時間復(fù)雜度是O(1)

• 散列表可能會退化為鏈表,查詢的時間復(fù)雜度就從 O(1) 退化為 O(n)

• 將鏈表法中的鏈表改造為其他高效的動態(tài)數(shù)據(jù)結(jié)構(gòu)，比如紅黑樹，查詢的時間復(fù)雜度是 O(logn)

將鏈表法中的鏈表改造紅黑樹還有一個非常重要的原因，可以防止DDos攻擊

DDos 攻擊:
分布式拒絕服務(wù)攻擊(英文意思是Distributed Denial of Service，簡稱DDoS）
指處于 不同位置的多個攻擊者同時向一個或數(shù)個目標(biāo)發(fā)動攻擊，或者 一個攻擊者控制了位于不同位置的多臺機器并利用這些機器對受害者同時實施攻擊。由于攻擊的發(fā)出點是分布在不同地方的，這類攻擊稱為分布式拒絕服務(wù)攻擊，其中的攻擊者可以有多個

3.3 面試題-說一下HashMap的實現(xiàn)原理？

面試官追問：HashMap的jdk1.7和jdk1.8有什么區(qū)別

3.4 面試題-HashMap的put方法的具體流程

3.4.1 hashMap常見屬性

3.4.2 源碼分析

• HashMap是懶惰加載，在創(chuàng)建對象時并沒有初始化數(shù)組

• 在無參的構(gòu)造函數(shù)中，設(shè)置了默認的加載因子DEFA..是0.75

添加數(shù)據(jù)流程圖

具體的jdk8源碼：

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;//判斷數(shù)組是否未初始化if ((tab = table) == null || (n = tab.length) == 0)//如果未初始化，調(diào)用resize方法 進行初始化n = (tab = resize()).length;//通過 & 運算求出該數(shù)據(jù)（key）的數(shù)組下標(biāo)并判斷該下標(biāo)位置是否有數(shù)據(jù)if ((p = tab[i = (n - 1) & hash]) == null)//如果沒有，直接將數(shù)據(jù)放在該下標(biāo)位置tab[i] = newNode(hash, key, value, null);//該數(shù)組下標(biāo)有數(shù)據(jù)的情況else {Node<K,V> e; K k;//判斷該位置數(shù)據(jù)的key和新來的數(shù)據(jù)是否一樣if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))//如果一樣，證明為修改操作，該節(jié)點的數(shù)據(jù)賦值給e,后邊會用到e = p;//判斷是不是紅黑樹else if (p instanceof TreeNode)//如果是紅黑樹的話，進行紅黑樹的操作e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//新數(shù)據(jù)和當(dāng)前數(shù)組既不相同，也不是紅黑樹節(jié)點，證明是鏈表else {//遍歷鏈表for (int binCount = 0; ; ++binCount) {//判斷next節(jié)點，如果為空的話，證明遍歷到鏈表尾部了if ((e = p.next) == null) {//把新值放入鏈表尾部p.next = newNode(hash, key, value, null);//因為新插入了一條數(shù)據(jù)，所以判斷鏈表長度是不是大于等于8if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st//如果是，進行轉(zhuǎn)換紅黑樹操作treeifyBin(tab, hash);break;}//判斷鏈表當(dāng)中有數(shù)據(jù)相同的值，如果一樣，證明為修改操作if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;//把下一個節(jié)點賦值為當(dāng)前節(jié)點p = e;}}//判斷e是否為空（e值為修改操作存放原數(shù)據(jù)的變量）if (e != null) { // existing mapping for key//不為空的話證明是修改操作，取出老值V oldValue = e.value;//一定會執(zhí)行  onlyIfAbsent傳進來的是falseif (!onlyIfAbsent || oldValue == null)//將新值賦值當(dāng)前節(jié)點e.value = value;afterNodeAccess(e);//返回老值return oldValue;}}//計數(shù)器，計算當(dāng)前節(jié)點的修改次數(shù)++modCount;//當(dāng)前數(shù)組中的數(shù)據(jù)數(shù)量如果大于擴容閾值if (++size > threshold)//進行擴容操作resize();//空方法afterNodeInsertion(evict);//添加操作時 返回空值return null;
}

HashMap的put方法的具體流程

1. 判斷鍵值對數(shù)組table是否為空或為null，否則執(zhí)行resize()進行擴容（初始化）

1. 根據(jù)鍵值key計算hash值得到數(shù)組索引

1. 判斷table[i]==null，條件成立，直接新建節(jié)點添加

1. 如果table[i]==null ,不成立

4.1 判斷table[i]的首個元素是否和key一樣，如果相同直接覆蓋value

4.2 判斷table[i] 是否為treeNode，即table[i 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對

4.3 遍歷table[i]，鏈表的尾部插入數(shù)據(jù)，然后判斷鏈表長度是否大于8，大于8的話把鏈表轉(zhuǎn)換為紅黑樹，在紅黑樹中執(zhí)行插入操 作，遍歷過程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value

1. 插入成功后，判斷實際存在的鍵值對數(shù)量size是否超過了最大容量threshold（數(shù)組長度*0.75），如果超過，進行擴容。

！3.5 面試題-講一講HashMap的擴容機制

擴容的流程：

源碼：

//擴容、初始化數(shù)組
final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;//如果當(dāng)前數(shù)組為null的時候，把oldCap老數(shù)組容量設(shè)置為0int oldCap = (oldTab == null) ? 0 : oldTab.length;//老的擴容閾值int oldThr = threshold;int newCap, newThr = 0;//判斷數(shù)組容量是否大于0，大于0說明數(shù)組已經(jīng)初始化if (oldCap > 0) {//判斷當(dāng)前數(shù)組長度是否大于最大數(shù)組長度if (oldCap >= MAXIMUM_CAPACITY) {//如果是，將擴容閾值直接設(shè)置為int類型的最大數(shù)值并直接返回threshold = Integer.MAX_VALUE;return oldTab;}//如果在最大長度范圍內(nèi)，則需要擴容  OldCap << 1等價于oldCap*2//運算過后判斷是不是最大值并且oldCap需要大于16else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold  等價于oldThr*2}//如果oldCap<0，但是已經(jīng)初始化了，像把元素刪除完之后的情況，那么它的臨界值肯定還存在，       			如果是首次初始化，它的臨界值則為0else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;//數(shù)組未初始化的情況，將閾值和擴容因子都設(shè)置為默認值else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//初始化容量小于16的時候，擴容閾值是沒有賦值的if (newThr == 0) {//創(chuàng)建閾值float ft = (float)newCap * loadFactor;//判斷新容量和新閾值是否大于最大容量newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}//計算出來的閾值賦值threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})//根據(jù)上邊計算得出的容量 創(chuàng)建新的數(shù)組       Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//賦值table = newTab;//擴容操作，判斷不為空證明不是初始化數(shù)組if (oldTab != null) {//遍歷數(shù)組for (int j = 0; j < oldCap; ++j) {Node<K,V> e;//判斷當(dāng)前下標(biāo)為j的數(shù)組如果不為空的話賦值個e，進行下一步操作if ((e = oldTab[j]) != null) {//將數(shù)組位置置空oldTab[j] = null;//判斷是否有下個節(jié)點if (e.next == null)//如果沒有，就重新計算在新數(shù)組中的下標(biāo)并放進去newTab[e.hash & (newCap - 1)] = e;//有下個節(jié)點的情況，并且判斷是否已經(jīng)樹化else if (e instanceof TreeNode)//進行紅黑樹的操作((TreeNode<K,V>)e).split(this, newTab, j, oldCap);//有下個節(jié)點的情況，并且沒有樹化（鏈表形式）else {//比如老數(shù)組容量是16，那下標(biāo)就為0-15//擴容操作*2，容量就變?yōu)?2，下標(biāo)為0-31//低位：0-15，高位16-31//定義了四個變量//        低位頭          低位尾Node<K,V> loHead = null, loTail = null;//        高位頭		   高位尾Node<K,V> hiHead = null, hiTail = null;//下個節(jié)點Node<K,V> next;//循環(huán)遍歷do {//取出next節(jié)點next = e.next;//通過 與操作 計算得出結(jié)果為0if ((e.hash & oldCap) == 0) {//如果低位尾為null，證明當(dāng)前數(shù)組位置為空，沒有任何數(shù)據(jù)if (loTail == null)//將e值放入低位頭loHead = e;//低位尾不為null，證明已經(jīng)有數(shù)據(jù)了else//將數(shù)據(jù)放入next節(jié)點loTail.next = e;//記錄低位尾數(shù)據(jù)loTail = e;}//通過 與操作 計算得出結(jié)果不為0else {//如果高位尾為null，證明當(dāng)前數(shù)組位置為空，沒有任何數(shù)據(jù)if (hiTail == null)//將e值放入高位頭hiHead = e;//高位尾不為null，證明已經(jīng)有數(shù)據(jù)了else//將數(shù)據(jù)放入next節(jié)點hiTail.next = e;//記錄高位尾數(shù)據(jù)hiTail = e;}} //如果e不為空，證明沒有到鏈表尾部，繼續(xù)執(zhí)行循環(huán)while ((e = next) != null);//低位尾如果記錄的有數(shù)據(jù)，是鏈表if (loTail != null) {//將下一個元素置空loTail.next = null;//將低位頭放入新數(shù)組的原下標(biāo)位置newTab[j] = loHead;}//高位尾如果記錄的有數(shù)據(jù)，是鏈表if (hiTail != null) {//將下一個元素置空hiTail.next = null;//將高位頭放入新數(shù)組的(原下標(biāo)+原數(shù)組容量)位置newTab[j + oldCap] = hiHead;}}}}}//返回新的數(shù)組對象return newTab;}

• 在添加元素或初始化的時候需要調(diào)用resize方法進行擴容，第一次添加數(shù)據(jù)初始化數(shù)組長度為16，以后每次每次擴容都是達到了擴容閾值（數(shù)組長度 * 0.75）

• 每次擴容的時候，都是擴容之前容量的2倍；

• 擴容之后，會新創(chuàng)建一個數(shù)組，需要把老數(shù)組中的數(shù)據(jù)挪動到新的數(shù)組中

• 沒有hash沖突的節(jié)點，則直接使用 e.hash & (newCap - 1) 計算新數(shù)組的索引位置

• 如果是紅黑樹，走紅黑樹的添加

• 如果是鏈表，則需要遍歷鏈表，可能需要拆分鏈表，判斷(e.hash & oldCap)是否為0，該元素的位置要么停留在原始位置，要么移動到原始位置+增加的數(shù)組大小這個位置上

3.6 面試題-hashMap的尋址算法

?

3.9 面試題-HashTable與HashMap的區(qū)別

難易程度：☆☆
出現(xiàn)頻率：☆☆

主要區(qū)別：

在實際開中不建議使用HashTable，在多線程環(huán)境下可以使用ConcurrentHashMap類

3 真實面試還原

3.1 Java常見的集合類

面試官：說一說Java提供的常見集合？（畫一下集合結(jié)構(gòu)圖）
候選人：
嗯~~，好的。
在java中提供了量大類的集合框架，主要分為兩類：
第一個是Collection 屬于單列集合，第二個是Map 屬于雙列集合
在Collection中有兩個子接口List和Set。在我們平常開發(fā)的過程中用的比較多像list接口中的實現(xiàn)類ArrarList和LinkedList。 在Set接口中有實現(xiàn)類HashSet和TreeSet。
在map接口中有很多的實現(xiàn)類，平時比較常見的是HashMap、TreeMap，還有一個線程安全的map:ConcurrentHashMap

3.2 List

面試官：ArrayList底層是如何實現(xiàn)的？
候選人：
嗯~，我閱讀過arraylist的源碼，我主要說一下add方法吧
第一：確保數(shù)組已使用長度（size）加1之后足夠存下下一個數(shù)據(jù)
第二：計算數(shù)組的容量，如果當(dāng)前數(shù)組已使用長度+1后的大于當(dāng)前的數(shù)組長度，則調(diào)用grow方法擴容（原來的1.5倍）
第三：確保新增的數(shù)據(jù)有地方存儲之后，則將新元素添加到位于size的位置上。
第四：返回添加成功布爾值。
面試官：ArrayList list=new ArrayList(10)中的list擴容幾次
候選人：
是new了一個ArrarList并且給了一個構(gòu)造參數(shù)10，對吧？(問題一定要問清楚再答)
面試官：是的
候選人：
好的，在ArrayList的源碼中提供了一個帶參數(shù)的構(gòu)造方法，這個參數(shù)就是指定的集合初始長度，所以給了一個10的參數(shù)，就是指定了集合的初始長度是10，這里面并沒有擴容。

面試官：如何實現(xiàn)數(shù)組和List之間的轉(zhuǎn)換
候選人：
嗯，這個在我們平時開發(fā)很常見
數(shù)組轉(zhuǎn)list，可以使用jdk自動的一個工具類Arrars，里面有一個asList方法可以轉(zhuǎn)換為數(shù)組
List 轉(zhuǎn)數(shù)組，可以直接調(diào)用list中的toArray方法，需要給一個參數(shù)，指定數(shù)組的類型，需要指定數(shù)組的長度。
面試官：用Arrays.asList轉(zhuǎn)List后，如果修改了數(shù)組內(nèi)容，list受影響嗎？List用toArray轉(zhuǎn)數(shù)組后，如果修改了List內(nèi)容，數(shù)組受影響嗎
候選人：
Arrays.asList轉(zhuǎn)換list之后，如果修改了數(shù)組的內(nèi)容，list會受影響，因為它的底層使用的Arrays類中的一個內(nèi)部類ArrayList來構(gòu)造的集合，在這個集合的構(gòu)造器中，把我們傳入的這個集合進行了包裝而已，最終指向的都是同一個內(nèi)存地址
list用了toArray轉(zhuǎn)數(shù)組后，如果修改了list內(nèi)容，數(shù)組不會影響，當(dāng)調(diào)用了toArray以后，在底層是它是進行了數(shù)組的拷貝，跟原來的元素就沒啥關(guān)系了，所以即使list修改了以后，數(shù)組也不受影響

面試官：ArrayList 和 LinkedList 的區(qū)別是什么？
候選人：
嗯，它們兩個主要是底層使用的數(shù)據(jù)結(jié)構(gòu)不一樣，ArrayList 是動態(tài)數(shù)組，LinkedList 是雙向鏈表，這也導(dǎo)致了它們很多不同的特點。
1，從操作數(shù)據(jù)效率來說
ArrayList按照下標(biāo)查詢的時間復(fù)雜度O(1)【內(nèi)存是連續(xù)的，根據(jù)尋址公式】， LinkedList不支持下標(biāo)查詢
查找（未知索引）： ArrayList需要遍歷，鏈表也需要鏈表，時間復(fù)雜度都是O(n)
新增和刪除
ArrayList尾部插入和刪除，時間復(fù)雜度是O(1)；其他部分增刪需要挪動數(shù)組，時間復(fù)雜度是O(n)
LinkedList頭尾節(jié)點增刪時間復(fù)雜度是O(1)，其他都需要遍歷鏈表，時間復(fù)雜度是O(n)
2，從內(nèi)存空間占用來說
ArrayList底層是數(shù)組，內(nèi)存連續(xù)，節(jié)省內(nèi)存
LinkedList 是雙向鏈表需要存儲數(shù)據(jù)，和兩個指針，更占用內(nèi)存
3，從線程安全來說，ArrayList和LinkedList都不是線程安全的
面試官：嗯，好的，剛才你說了ArrayList 和 LinkedList 不是線程安全的，你們在項目中是如何解決這個的線程安全問題的？
候選人：
嗯，是這樣的，主要有兩種解決方案：
第一：我們使用這個集合，優(yōu)先在方法內(nèi)使用，定義為局部變量，這樣的話，就不會出現(xiàn)線程安全問題。
第二：如果非要在成員變量中使用的話，可以使用線程安全的集合來替代
ArrayList可以通過Collections 的 synchronizedList 方法將 ArrayList 轉(zhuǎn)換成線程安全的容器后再使用。
LinkedList 換成ConcurrentLinkedQueue來使用

3.4 HashMap

面試官：說一下HashMap的實現(xiàn)原理？
候選人：
嗯。它主要分為了一下幾個部分：
1，底層使用hash表數(shù)據(jù)結(jié)構(gòu)，即數(shù)組+（鏈表 | 紅黑樹）
2，添加數(shù)據(jù)時，計算key的值確定元素在數(shù)組中的下標(biāo)
key相同則替換
不同則存入鏈表或紅黑樹中
3，獲取數(shù)據(jù)通過key的hash計算數(shù)組下標(biāo)獲取元素
面試官：HashMap的jdk1.7和jdk1.8有什么區(qū)別
候選人：
JDK1.8之前采用的拉鏈法，數(shù)組+鏈表
JDK1.8之后采用數(shù)組+鏈表+紅黑樹，鏈表長度大于8且數(shù)組長度大于64則會從鏈表轉(zhuǎn)化為紅黑樹
面試官：好的，你能說下HashMap的put方法的具體流程嗎？
候選人：
嗯好的。
判斷鍵值對數(shù)組table是否為空或為null，否則執(zhí)行resize()進行擴容（初始化）
根據(jù)鍵值key計算hash值得到數(shù)組索引
判斷table[i]==null，條件成立，直接新建節(jié)點添加
如果table[i]==null ,不成立
4.1 判斷table[i]的首個元素是否和key一樣，如果相同直接覆蓋value
4.2 判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對
4.3 遍歷table[i]，鏈表的尾部插入數(shù)據(jù)，然后判斷鏈表長度是否大于8，大于8的話把鏈表轉(zhuǎn)換為紅黑樹，在紅黑樹中執(zhí)行插入操 作，遍歷過程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value
插入成功后，判斷實際存在的鍵值對數(shù)量size是否超多了最大容量threshold（數(shù)組長度*0.75），如果超過，進行擴容。
面試官：好的，剛才你多次介紹了hsahmap的擴容，能講一講HashMap的擴容機制嗎？
候選人：
好的
在添加元素或初始化的時候需要調(diào)用resize方法進行擴容，第一次添加數(shù)據(jù)初始化數(shù)組長度為16，以后每次每次擴容都是達到了擴容閾值（數(shù)組長度 * 0.75）
每次擴容的時候，都是擴容之前容量的2倍；
擴容之后，會新創(chuàng)建一個數(shù)組，需要把老數(shù)組中的數(shù)據(jù)挪動到新的數(shù)組中
沒有hash沖突的節(jié)點，則直接使用 e.hash & (newCap - 1) 計算新數(shù)組的索引位置
如果是紅黑樹，走紅黑樹的添加
如果是鏈表，則需要遍歷鏈表，可能需要拆分鏈表，判斷(e.hash & oldCap)是否為0，該元素的位置要么停留在原始位置，要么移動到原始位置+增加的數(shù)組大小這個位置上
面試官：好的，剛才你說的通過hash計算后找到數(shù)組的下標(biāo)，是如何找到的呢，你了解hashMap的尋址算法嗎？
候選人：
這個哈希方法首先計算出key的hashCode值，然后通過這個hash值右移16位后的二進制進行按位 異或運算得到最后的hash值。
在putValue的方法中，計算數(shù)組下標(biāo)的時候使用hash值與數(shù)組長度取模得到存儲數(shù)據(jù)下標(biāo)的位置，hashmap為了性能更好，并沒有直接采用取模的方式，而是使用了數(shù)組長度-1 得到一個值，用這個值按位與運算hash值，最終得到數(shù)組的位置。
面試官：為何HashMap的數(shù)組長度一定是2的次冪？
候選人：
嗯，好的。hashmap這么設(shè)計主要有兩個原因：
第一：
計算索引時效率更高：如果是 2 的 n 次冪可以使用位與運算代替取模
第二：
擴容時重新計算索引效率更高：在進行擴容是會進行判斷 hash值按位與運算舊數(shù)組長租是否 == 0
如果等于0，則把元素留在原來位置 ，否則新位置是等于舊位置的下標(biāo)+舊數(shù)組長度
面試官：好的，我看你對hashmap了解的挺深入的，你知道hashmap在1.7情況下的多線程死循環(huán)問題嗎？
候選人：
嗯，知道的。是這樣
jdk7的的數(shù)據(jù)結(jié)構(gòu)是：數(shù)組+鏈表
在數(shù)組進行擴容的時候，因為鏈表是 頭插法，在進行數(shù)據(jù)遷移的過程中，有可能導(dǎo)致死循環(huán)
比如說，現(xiàn)在有兩個線程
線程一： 讀取到當(dāng)前的hashmap數(shù)據(jù)，數(shù)據(jù)中一個鏈表，在準(zhǔn)備擴容時，線程二介入
線程二也讀取hashmap，直接進行擴容。因為是頭插法，鏈表的順序會進行顛倒過來。比如原來的順序是AB，擴容后的順序是BA，線程二執(zhí)行結(jié)束。
當(dāng)線程一再繼續(xù)執(zhí)行的時候就會出現(xiàn)死循環(huán)的問題。
線程一先將A移入新的鏈表，再將B插入到鏈頭，由于另外一個線程的原因，B的next指向了A，所以B->A->B,形成循環(huán)。
當(dāng)然，JDK 8 將擴容算法做了調(diào)整，不再將元素加入鏈表頭（而是保持與擴容前一樣的順序）， 尾插法，就避免了jdk7中死循環(huán)的問題。
面試官：好的，hashmap是線程安全的嗎？
候選人：不是線程安全的
面試官：那我們想要使用線程安全的map該怎么做呢？
候選人：我們可以采用ConcurrentHashMap進行使用，它是一個線程安全的HashMap
面試官：那你能聊一下ConcurrentHashMap的原理嗎？
候選人：好的，請參考《多線程相關(guān)面試題》中的ConcurrentHashMap部分的講解

面試官：HashSet與HashMap的區(qū)別？
候選人：嗯，是這樣。
HashSet底層其實是用HashMap實現(xiàn)存儲的, HashSet封裝了一系列HashMap的方法. 依靠HashMap來存儲元素值,(利用hashMap的key鍵進行存儲), 而value值默認為Object對象. 所以HashSet也不允許出現(xiàn)重復(fù)值, 判斷標(biāo)準(zhǔn)和HashMap判斷標(biāo)準(zhǔn)相同, 兩個元素的hashCode相等并且通過equals()方法返回true.
面試官：HashTable與HashMap的區(qū)別
候選人：
嗯，他們的主要區(qū)別是有幾個吧
第一，數(shù)據(jù)結(jié)構(gòu)不一樣，hashtable是數(shù)組+鏈表，hashmap在1.8之后改為了數(shù)組+鏈表+紅黑樹
第二，hashtable存儲數(shù)據(jù)的時候都不能為null，而hashmap是可以的
第三，hash算法不同，hashtable是用本地修飾的hashcode值，而hashmap經(jīng)常了二次hash
第四，擴容方式不同，hashtable是當(dāng)前容量翻倍+1，hashmap是當(dāng)前容量翻倍
第五，hashtable是線程安全的，操作數(shù)據(jù)的時候加了鎖synchronized，hashmap不是線程安全的，效率更高一些
在實際開中不建議使用HashTable，在多線程環(huán)境下可以使用ConcurrentHashMap類