Map

• Map接口并不是繼承自Collection接口，這個(gè)要注意了

• 常見的Map實(shí)現(xiàn)類:

  • HashMap
  • ConcurrentHashMap
  • LinkedHashMap
  • TreeMap

• util包的關(guān)系圖，Map和Dictionary

  
  
  util包中Map依賴關(guān)系圖

• 關(guān)于Hash算法和Hash沖突的解決方法，詳細(xì)可參考全網(wǎng)把Map中的hash()分析的最透徹的文章，別無二家。-HollisChuang's Blog

HashMap

• 環(huán)形鏈表的問題：具體見疫苗：Java HashMap的死循環(huán) | | 酷 殼 - CoolShell
  • 環(huán)形鏈表的形成是發(fā)生在并發(fā)rehash的過程中的
  • 并不是說rehash就直接導(dǎo)致死循環(huán)了，rehash只是導(dǎo)致的了環(huán)形鏈表的形成
• 底層數(shù)據(jù)結(jié)構(gòu)
  • 數(shù)組
  • 鏈表
  • 紅黑樹
• 擴(kuò)容
  • 時(shí)機(jī)：map中的key個(gè)數(shù)達(dá)到容量c * 負(fù)載因子loadFactor的時(shí)候
  • 過程
    • 容量擴(kuò)大一倍
    • rehash一次
• 沖突解決
  • 默認(rèn)的策略是在相應(yīng)的index位置形成鏈表
  • 當(dāng)鏈表的數(shù)量達(dá)到8個(gè)時(shí)，出于性能考慮會(huì)把鏈表轉(zhuǎn)成紅黑樹
• 快速失敗是什么意思? 集合遍歷的時(shí)候檢測是否集合中的元素個(gè)數(shù)有變動(dòng)，有變動(dòng)就立即拋出異常ConcurrentModificationException

The number of times this HashMap has been structurally modified Structural modifications are those that change the number of mappings in the HashMap or otherwise modify its internal structure (e.g.,
rehash). This field is used to make iterators on Collection-views of
the HashMap fail-fast. (See ConcurrentModificationException).

• [x]loadFactor是用來干什么的？決定是否擴(kuò)容

ConcurrentHashMap

• 底層數(shù)據(jù)結(jié)構(gòu)
  • 數(shù)組
  • 鏈表
  • 紅黑樹
• 擴(kuò)容過程
  • JDK7鎖住所有段，然后擴(kuò)容，保證一致性
  • JDK8多線程擴(kuò)容，標(biāo)記要遷移的點(diǎn)（要遷移的點(diǎn)node的hash值會(huì)被標(biāo)記成為MOVED，即-3），當(dāng)一個(gè)線程要獲取fh被標(biāo)記為MOVED的節(jié)點(diǎn)時(shí)，要先幫忙擴(kuò)容，然后再獲取值
• size是怎么計(jì)算的？
  • 默認(rèn)是使用baseCount，如果因?yàn)椴l(fā)導(dǎo)致這個(gè)屬性更新失敗，會(huì)使用counterCells來計(jì)數(shù)。
  • 計(jì)數(shù)的時(shí)候，會(huì)使用先計(jì)算兩次，如果沒變化，就認(rèn)為總數(shù)是正確
  • 如果一直在變化，就多嘗試兩次。如果還是失敗，就鎖全表進(jìn)行計(jì)算。
• JDK7和JDK8上的分段鎖機(jī)制的差別
  • DK7使用ReentrantLock來實(shí)現(xiàn)分段鎖
  • JDK8使用CAS+synchronized，為什么使用synchronized+CAS, 而不是segment+ReentrantLock呢？ConcurrentHashMap 1.8為什么要使用CAS+Synchronized取代Segment+ReentrantLock - 羊飛 - 博客園
    • [x]synchronized默認(rèn)情況是偏向鎖，或者是自旋鎖，效率高，ReentrantLock則是tryLock之后就掛起，這樣導(dǎo)致有線程上下文切換的成本， JDK7版本這里會(huì)tryLock很多次
    • [x]鎖的粒度細(xì)化到了node級(jí)別，粒度更小，并發(fā)能力更大

常見面試題

Map

• rehash的時(shí)候，鏈表上的點(diǎn)還會(huì)在同一個(gè)鏈表上么？@可能不在同一個(gè)位置上了， 這是因?yàn)橥拔恢玫挠?jì)算方式是hash&(cap-1), hash值是不變的， cap變化的情況，可能導(dǎo)致計(jì)算的index不一樣， 譬如cap為16，hash分別為5, 21, 37, rehash之后，桶的index分別為5, 21,

HashMap

• 擴(kuò)容過程 @見上面的筆記
• size為什么是2的整數(shù)倍?
  • 計(jì)算index的時(shí)候可以減小沖突
  • 計(jì)算index的公式 hash & (size - 1)
• 沖突解決的過程 @見上面的筆記

ConcurrentHashMap

• 為什么JDK8中要用CAS+synchronized替代segment+ReentrantLock的實(shí)現(xiàn)來防止并發(fā)？@見上面的筆記