歡迎閱覽

作者介紹：
本人Java特工，代號：Cris Li 充活； 中文名：克瑞斯理
簡書地址: http://www.reibang.com/u/c508b0afaaee
CSDN地址: https://blog.csdn.net/jianli95
個人純潔版博客: https://lijian69.github.io/blog/

Q1：你用過HashMap，你能跟我說說它的數據結構嗎蜡娶？

回答： HashMap是一種容器類型混卵，通過Key-Value鍵值對存儲數據，JDK1.8之前采用數組+鏈表的數據結構窖张，但是在JDK1.8以及1.8之后采用的數組+鏈表+紅黑樹的數據結構底部存儲數據幕随，當鏈表的長度為8的時候，轉換為紅黑樹宿接，當紅黑樹的長度減小到6的時候赘淮，轉換為鏈表，為什么是8睦霎，因為西方的采用泊松分布減少Hash的碰撞次數梢卸。

HashMap的底部數據結構

Q2：HashMap中hash函數怎么是是實現的?

回答：“模”運算的消耗還是比較大的副女，能不能找一種更快速蛤高，消耗更小的方式，我們來看看JDK1.8采用位異或方式代替取模運算。(h ^ (h >>> 16)) hash函數的位干擾戴陡。減少hash碰撞塞绿。

static final int hash(Object key) {
    if (key == null){
        return 0;
    }
     int h;
     h=key.hashCode()；返回散列值也就是hashcode
      // ^ ：按位異或 （相同得0恤批，不同得1）
      // & ：與運算（相同得1位隶，不同得0）
      // >>>:無符號右移，忽略符號位开皿，空位都以0補齊
      //其中n是數組的長度，即Map的數組部分初始化長度
     return  (n-1)&(h ^ (h >>> 16));
}

image.png

Q2：談一下HashMap的特性懊昨？

回答：

• HashMap鍵值對存儲數據實現快速存儲窄潭，key-value允許為null,key值不可重復，若key重復則覆蓋酵颁。
• 非同步 線程不安全
• 底層是hash表 無序 不保證插入的順序

Q3：拉鏈法導致的鏈表過深問題為什么不用二叉查找樹代替嫉你，而選擇紅黑樹？為什么不一直使用紅黑樹躏惋？

回答： 之所以選擇紅黑樹是為了解決二叉查找樹的缺陷幽污，二叉查找樹在特殊情況下會變成一條線性結構（這就跟原來使用鏈表結構一樣了，造成很深的問題）簿姨，遍歷查找會非常慢距误。而紅黑樹在插入新數據后可能需要通過左旋，右旋扁位、變色這些操作來保持平衡准潭，引入紅黑樹就是為了查找數據快，解決鏈表查詢深度的問題域仇，我們知道紅黑樹屬于平衡二叉樹刑然，但是為了保持“平衡”是需要付出代價的，但是該代價所損耗的資源要比遍歷線性鏈表要少暇务，所以當長度大于8的時候泼掠，會使用紅黑樹，如果鏈表長度很短的話垦细，根本不需要引入紅黑樹武鲁，引入反而會慢。

Q4：說說你對紅黑樹的見解蝠检？

image.png

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

Q4： 解決hash 碰撞還有那些辦法？

開放定址法饲梭。

Q3：HashMap的工作原理乘盖？

回答： HashMap給予Hashing原理，采用native本地方法調用C++函數寫的獲取Hash值憔涉。我們在通過get()和put()的時候订框，都要通過哈希算法計算出key的hashcode值，返回的hashcode值用于方便找到Bucket位置來儲存或者獲得Entry對象兜叨，JDK把Entry<K,T>改名為Node<K,T>對象穿扳，在put的時候，如果該位置已經有元素了国旷，調用equals方法判斷是否相等矛物，相等的話進行替換，不相等的話跪但，新增Node節(jié)點放在鏈表或者紅黑樹里面履羞。
當獲取對象的時候，通過鍵對象的equals()方法找到正確的鍵值對屡久，然后返回值對象忆首，HashMap使用鏈表或者紅黑樹來解決碰撞問題，當發(fā)生碰撞的時候被环，對象會存儲在鏈表的下一個節(jié)點中糙及。

image.png

Q4：如果HashMap的大小超過了負載因子(load factor)定義的容量，怎么辦筛欢？

回答： 默認的負載因子大小為0.75丁鹉，也就是說，當一個map填滿了75%的bucket時候悴能，和其它集合類(如ArrayList等)一樣揣钦，將會創(chuàng)建原來HashMap大小的兩倍的bucket數組，來重新調整map的大小漠酿，并將原來的對象放入新的bucket數組中冯凹。這個過程叫作rehashing，因為它調用hash方法找到新的bucket位置炒嘲。這個值只可能在兩個地方宇姚，一個是原下標的位置，另一種是在下標為<原下標+原容量>的位置夫凸。在1.7版本浑劳，多線程下容易發(fā)生線程不安全，在重Hash遷移數組的時候夭拌，容易出現鏈表死循環(huán)魔熏。

Q5：如何使HashMap變成線程安全的呢?

回答：調用工具類Collections.synchronizedMap(map); 或者使用ConcurrentHashMap集合類衷咽。

這里不推薦使用HashTable

Map mapNew = Collections.synchronizedMap(map);

Q5：重新調整HashMap大小存在什么問題嗎？

• 當重新調整HashMap大小的時候蒜绽，確實存在條件競爭镶骗，因為如果兩個線程都發(fā)現HashMap需要重新調整大小了，它們會同時試著調整大小躲雅。在調整大小的過程中鼎姊，存儲在鏈表中的元素的次序會反過來，因為移動到新的bucket位置的時候相赁，HashMap并不會將元素放在鏈表的尾部相寇，而是放在頭部，這是為了避免尾部遍歷(tail traversing)钮科。如果條件競爭發(fā)生了唤衫，那么就死循環(huán)了。(多線程的環(huán)境下不使用HashMap）
  為什么多線程會導致死循環(huán)跺嗽，它是怎么發(fā)生的？
  　　HashMap的容量是有限的页藻。當經過多次元素插入桨嫁，使得HashMap達到一定飽和度時，Key映射位置發(fā)生沖突的幾率會逐漸提高份帐。這時候璃吧，HashMap需要擴展它的長度蚓炬，也就是 　　進行Resize搁痛。1.擴容：創(chuàng)建一個新的Entry空數組赐稽，長度是原數組的2倍厚掷。2.ReHash：遍歷原Entry數組窖贤，把所有的Entry重新Hash到新數組挫以。

Q4：HashMap的bucket數組的數量默認為多少孤个？它的取值范圍是多少陋率？

回答： HashMap的bucket數組數量的默認大小為16驮宴，它的要求是必須為2的整數次密逮刨。所以不可能為15,21,22······等等。

• 為了數據的均勻分布堵泽，減少哈希碰撞修己。因為確定數組位置是用的位運算，若數據不是2的次冪則會增加哈希碰撞的次數和浪費數組空間迎罗。(PS:其實若不考慮效率睬愤，求余也可以就不用位運算了也不用長度必需為2的冪次)
• 輸入數據若不是2的冪，HashMap通過一通位移運算和或運算得到的肯定是2的冪次數纹安，并且是離那個數最近的數字尤辱，獲取大于它的最小2的整數冪

Q4：HashMap鍵值為什么只能為引用類型砂豌？

回答： 因為HashMap要根據hashcode()和equal()來保證鍵的唯一。

Q4：談一下hashMap中put是如何實現的啥刻？

回答：
1.計算關于key的hashcode值（與Key.hashCode的高16位做異或運算）
2.如果散列表為空時奸鸯，調用resize()初始化散列表
3.如果沒有發(fā)生碰撞，直接添加元素到散列表中去
4.如果發(fā)生了碰撞(hashCode值相同)可帽，進行三種判斷
4.1:若key地址相同或者equals后內容相同娄涩，則替換舊值
4.2:如果是紅黑樹結構，就調用樹的插入方法
4.3：鏈表結構映跟，循環(huán)遍歷直到鏈表中某個節(jié)點為空蓄拣，尾插法進行插入，插入之后判斷鏈表個數是否到達變成紅黑樹的闕值8努隙；也可以遍歷到有節(jié)點與插入元素的哈希值和內容相同球恤，進行覆蓋。
5.如果桶滿了大于閥值荸镊，則resize進行擴容

Q4：談一下hashMap中get是如何實現的咽斧？

回答： 對key的hashCode進行hashing，與運算計算下標獲取bucket位置躬存，如果在桶的首位上就可以找到就直接返回张惹，否則在樹中找或者鏈表中遍歷找，如果有hash沖突岭洲，則利用equals方法去遍歷鏈表查找節(jié)點宛逗。

Q4：談一下HashMap中hash函數是怎么實現的？還有哪些hash函數的實現方式盾剩？

回答：對key的hashCode做hash操作雷激，與高16位做異或運算還有平方取中法，除留余數法告私，偽隨機數法

Q4：為什么不直接將key作為哈希值而是與高16位做異或運算屎暇？

回答：因為數組位置的確定用的是與運算，僅僅最后四位有效驻粟，設計者將key的哈希值與高16為做異或運算使得在做&運算確定數組的插入位置時恭垦，此時的低位實際是高位與低位的結合，增加了隨機性格嗅，減少了哈希碰撞的次數番挺。

Q4：平時在使用HashMap時一般使用什么類型的元素作為Key？

回答：選擇Integer屯掖，String這種不可變的類型玄柏，像對String的一切操作都是新建一個String對象，對新的對象進行拼接分割等贴铜，這些類已經很規(guī)范的覆寫了hashCode()以及equals()方法粪摘。作為不可變類天生是線程安全的瀑晒，

Q4：傳統(tǒng)hashMap的缺點(為什么引入紅黑樹？)：

回答：JDK 1.8 以前 HashMap 的實現是 數組+鏈表徘意，即使哈希函數取得再好苔悦，也很難達到元素百分百均勻分布。當 HashMap 中有大量的元素都存放到同一個桶中時椎咧，這個桶下有一條長長的鏈表玖详，這個時候 HashMap 就相當于一個單鏈表，假如單鏈表有 n 個元素勤讽，遍歷的時間復雜度就是 O(n)蟋座，完全失去了它的優(yōu)勢。針對這種情況脚牍，JDK 1.8 中引入了 紅黑樹（查找時間復雜度為 O(logn)）來優(yōu)化這個問題向臀。

Q4：請解釋一下HashMap的參數loadFactor，它的作用是什么诸狭？

回答：loadFactor表示HashMap的擁擠程度券膀，影響hash操作到同一個數組位置的概率。默認loadFactor等于0.75驯遇，當HashMap里面容納的元素已經達到HashMap數組長度的75%時芹彬，表示HashMap太擠了，需要擴容妹懒，在HashMap的構造器中可以定制loadFactor雀监。

Q4：HashMap和HashTable的區(qū)別

回答：
相同點：都是存儲key-value鍵值對的
不同點：

1. HashMap允許Key-value為null双吆，hashTable不允許眨唬；
2. hashMap沒有考慮同步，是線程不安全的好乐。hashTable是線程安全的匾竿，給api套上了一層synchronized修飾;
3. HashMap繼承于AbstractMap類，hashTable繼承與Dictionary類蔚万。
4. 迭代器(Iterator)岭妖。HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的反璃。所以當有其它線程改變了HashMap的結構（增加或者移除元素）昵慌，將會拋出ConcurrentModificationException。
5. 容量的初始值和增加方式都不一樣：HashMap默認的容量大小是16淮蜈；增加容量時斋攀，每次將容量變?yōu)?原始容量x2"。Hashtable默認的容量大小是11梧田；增加容量時淳蔼，每次將容量變?yōu)?原始容量x2 + 1"侧蘸；
6. 添加key-value時的hash值算法不同：HashMap添加元素時，是使用自定義的哈希算法鹉梨。Hashtable沒有自定義哈希算法讳癌，而直接采用的key的hashCode()。

Q4：如果HashMap的大小超過了負載因子(load factor)定義的容量存皂，怎么辦晌坤？

回答：超過闕值會進行擴容操作，概括的講就是擴容后的數組大小是原數組的2倍艰垂，將原來的元素重新hashing放入到新的散列表中去泡仗。

Q4：談一下當兩個對象的hashCode相等時會怎么樣？

回答：會產生哈希碰撞猜憎，若key值相同則替換舊值娩怎，不然鏈接到鏈表后面，鏈表長度超過闕值8就轉為紅黑樹存儲

Q4：如果兩個鍵的hashcode相同胰柑，你如何獲取值對象截亦？

回答：HashCode相同，通過equals比較內容獲取值對象