1.HashMap的底層數(shù)據(jù)結(jié)構(gòu)？

數(shù)組長度是有限的，我們通過key.hashcode()得到的值有可能是相同的，則會(huì)形成鏈表

JDK1.7 數(shù)組+鏈表

public void node(){
    final K key;
    V value;
    final int hash;
     Entry<K,V> entry;
}

? JDK1.8 數(shù)組+鏈表+紅黑樹

class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        }

2.HashMap的存取原理與HashMap是怎么處理hash碰撞的？

• 存數(shù)據(jù)
  • 首先會(huì)對key進(jìn)行hashcode，獲取它的bucket位置，然后會(huì)entry對象放入，如果存在key.hashcode相同[hash碰撞]

JDK1.7 entry鏈表插入方式 每次擴(kuò)容的時(shí)候會(huì)將所有的entry值重新rehash 會(huì)出現(xiàn)環(huán)形鏈表，出現(xiàn)死循環(huán)

java8之前是頭插法，就是說新來的值會(huì)取代原有的值，原有的值就順推到鏈表中去，就像上面的例子一樣，因?yàn)閷戇@個(gè)代碼的作者認(rèn)為后來的值被查找的可能性更大一點(diǎn)，提升查找的效率。

JDK1.8 Node尾部插入了 在擴(kuò)容時(shí)會(huì)保持鏈表元素原本的順序，就不會(huì)出現(xiàn)鏈表成環(huán)的問題了。

• 取數(shù)據(jù)
  • 逆向，會(huì)將key進(jìn)行hashcode，獲取bucket位置，由于entry存放的是個(gè)鏈表，則會(huì)進(jìn)行equal與hashcode比較內(nèi)存地址

3.hashmap為啥會(huì)線程不安全？有什么線程安全的類代替么?

• 為啥不安全
  • put與get都未進(jìn)行加鎖，多線程會(huì)導(dǎo)致put的值 get獲取不同的值;
• 線程安全的類
  • concurrentHashMap與hashTable

4.默認(rèn)初始化大小是多少？為啥是這么多？為啥大小都是2的冪？

• 初始化大小16
• 1<<4就是16
• 在使用2的冥的時(shí)候，length-1的值所有的二進(jìn)制的值都為1，index的結(jié)果與hashcode的后幾位相同，實(shí)現(xiàn)了均勻分布
  • index = hashcode(key) & (length -1)

5.HashMap的擴(kuò)容方式？負(fù)載因子是多少？為什是這么多？

• 數(shù)組容量是有限的，數(shù)據(jù)多次插入的，到達(dá)一定的數(shù)量就會(huì)進(jìn)行擴(kuò)容，也就是resize。

  • resize有兩個(gè)因素：

    • Capacity：HashMap當(dāng)前長度。
    • loadFactor: 負(fù)載因子，默認(rèn)值0.75

    就比如當(dāng)前的容量大小為100，當(dāng)你存進(jìn)第76個(gè)的時(shí)候，判斷發(fā)現(xiàn)需要進(jìn)行resize了，那就進(jìn)行擴(kuò)容，但是HashMap的擴(kuò)容也不是簡單的擴(kuò)大點(diǎn)容量這么簡單的。
    

• 擴(kuò)容方式

  • 1.創(chuàng)建一個(gè)新的 Entry空數(shù)組，長度是原數(shù)組的2倍
  • 2.Rehash：遍歷原Entry 數(shù)組，把所有的Entry重新Hash到數(shù)組

• 為啥是loadFactor是0.75

  • 空間換時(shí)間 - 如果大于0.75 數(shù)組被填滿的元素就多，沖突的幾率大，鏈表存的元素就越多，查詢不方便
  • 時(shí)間換空間-小于0.75，數(shù)組被填滿的元素少，沖突的幾率少，鏈表存的元素少，查詢快

6.HashMap的主要參數(shù)都有哪些？

• 初始化容量

• 最大容量

• 默認(rèn)負(fù)載因子

• 樹形化閾值

• 解樹形化閾值 其實(shí)就是當(dāng)紅黑樹的節(jié)點(diǎn)的個(gè)數(shù)小于等于6時(shí)，會(huì)將紅黑樹結(jié)構(gòu)轉(zhuǎn)為鏈表結(jié)構(gòu)。

• 樹形化的最小容量

• 轉(zhuǎn)為紅黑樹有兩個(gè)條件

  • 鏈表的長度大于8
  • HashMap數(shù)組的容量大于等于64

  根據(jù)泊松分布，在負(fù)載因子默認(rèn)為0.75的時(shí)候，單個(gè)hash槽內(nèi)元素個(gè)數(shù)為8的概率小于百萬分之一，所以將7作為一個(gè)分水嶺，等于7的時(shí)候不轉(zhuǎn)換，大于等于8的時(shí)候才進(jìn)行轉(zhuǎn)換，小于等于6的時(shí)候就化為鏈表。
  

hashTable

• 1.效率低的原因

  • 對數(shù)據(jù)操作都會(huì)上鎖

• 2.與hashmap不同點(diǎn)

  • 1.hashtable不允許key與value為空值，hashMap是允許的
    • Hashtable在我們put 空值的時(shí)候會(huì)直接拋空指針異常，但是HashMap卻做了特殊處理。
    • Hashtable使用的是安全失敗機(jī)制（fail-safe）
  • 2.實(shí)現(xiàn)方式不同，hashTable繼承Dictionary； hashMap繼承AbstractMap
  • 3.初始化容量不同，hashTable 是 11 ，hashMap為16
  • 4.擴(kuò)容機(jī)制不同 hashMap是翻倍 hashtable是翻倍+1
  • 5.迭代器不同 hashMap的迭代器iterator 是fail-safe

• fail-safe

  • 原理

    • 迭代器遍歷訪問內(nèi)容，會(huì)存在modCount 變量，如果遍歷發(fā)生內(nèi)容的改變，則會(huì)改變modCount的值，當(dāng)下次hashNext()/next()遍歷下一個(gè)節(jié)點(diǎn)，會(huì)檢測 expectedmodCount值，是的話返回遍歷，否則拋出異常

  • 場景

    • 并發(fā)修改

ConcurrentHashMap

• 數(shù)據(jù)結(jié)構(gòu)是什么，以及為啥他并發(fā)度這么高

  1.7 segment數(shù)組 +hashEntry組成

  • 數(shù)據(jù)結(jié)構(gòu)

    • volatile修飾了HashEntry

      1. 可見性-保證了不同線程對這個(gè)變量的可見性，一個(gè)線程修改值，其他線程可獲取修改的值
      2. 排序性-禁止指令重排序
      3. 原子性-只能保證對單次讀寫的原子性,i++ 不能保證

  • 并發(fā)度高的原因

    • 1.采用分段鎖 segment 繼承的 ReentrantLock

    • 2.存取

    • 存

      1.嘗試自旋獲取鎖

      2.如果重試次數(shù)達(dá)到 MAX_SCAN_RETRIES 則改為阻塞鎖獲取

    • 取

      因?yàn)橛胿olatile修飾，保存了內(nèi)存的可見性，獲取的都是最新的值

  1.8 拋棄了segment 分段鎖，采用 CAS + synchronized 來保證并發(fā)的安全性 + node 組成

  cas-樂觀鎖，讀取時(shí)不進(jìn)行加鎖，寫回時(shí)會(huì)跟原有值判斷是否被修改，如果修改則重新讀取

  cas會(huì)出現(xiàn)ABA問題

• 存
• 根據(jù) key 計(jì)算出 hashcode
• 判讀是否進(jìn)行初始化
• 根據(jù)key定位出node位置，如果為空，則表示當(dāng)前可以寫入，利用cas嘗試寫入,失敗則自旋保證成功
• 如果 hashcode == moved == -1 進(jìn)行擴(kuò)容
• 都不滿足則用 synchronized 寫入
• 數(shù)量大于 鏈表 8 則會(huì)轉(zhuǎn)為紅黑樹
• 取
• 與hashMap相同
• key經(jīng)過hashcode 獲取桶的位置
• 如果是紅黑樹就按照樹的方式獲取
• 如果是鏈表就按照鏈表獲取