HashMap

• 數(shù)組+鏈表

• 非同步，可使用 Collections.synchronizedMap 構(gòu)造同步 HashMap

• 通過(guò)“拉鏈法”實(shí)現(xiàn)的哈希表

• 默認(rèn)容量 16，必須為 2 的冪

• table ，一個(gè) Entry 數(shù)組（Entry 實(shí)際為單項(xiàng)鏈表）

• size，鍵值對(duì)數(shù)量

• threshold，閾值 = 容量 × 加載因子，用于判斷是否需要調(diào)整容量

• loadFactor，加載因子，默認(rèn) 0.75，時(shí)間與空間上的一種折中

  • 哈希沖撞

• modCount -> fail-fast 機(jī)制

• hash() 計(jì)算 key 的 hash 值，供尋找索引使用

• indexFor() 返回?cái)?shù)組索引 hash & (length - 1)

• resize() 重新調(diào)整大小，重新將元素添加到新數(shù)組

• put 元素放在鏈表表頭

• Entry implements Map.Entry ； key, value, next, hash

• HashIterator implements Iterator

  • current, next
  • expectedModCount
  • hasNext(), nextEntry(), remove()

• keySet, entrySet；Set不包含重復(fù)元素

• values 為 Collection，可重復(fù)

1.8 中使用了紅黑樹(shù)，在某個(gè)桶中鏈表長(zhǎng)度達(dá)到 8 時(shí)，鏈表會(huì)轉(zhuǎn)化為紅黑樹(shù)，提升查找性能 （O(N) -> O(logn)）

• JDK7與JDK8中HashMap的實(shí)現(xiàn)

• ConcurrentHashMap

  • 不允許 key/value 為空
  • 1.7
    • 分段鎖 Segment 繼承 ReentrantLock，分段只在使用時(shí)才會(huì)創(chuàng)建
      • 一個(gè)分段鎖定不影響其他分段的訪問(wèn)，提升高并發(fā)環(huán)境下的處理能力
      • 每個(gè)分段其實(shí)也是一個(gè)表
    • 默認(rèn)容量 16，默認(rèn)并發(fā)度 16，默認(rèn)負(fù)載因子 0.75
    • put 時(shí)會(huì)進(jìn)行 tryLock 一定次數(shù)后，若仍無(wú)法獲取鎖，則通過(guò) lock 申請(qǐng)
      • 獲得鎖后對(duì)鏈表進(jìn)行遍歷查找，無(wú)相同節(jié)點(diǎn)則將新的 HashEntry 做為鏈表頭
      • 如果容量達(dá)到閾值，則對(duì) Segment 進(jìn)行 rehash 擴(kuò)容
    • 弱一致性：get, containsKey 沒(méi)有使用鎖，而是通過(guò) Unsafe 的 getObjectVolatile() 提供原子語(yǔ)義
    • size, containsValue
      • 進(jìn)行兩次操作，如果連續(xù)兩次所有 Segment 的 modcount 和相等，則說(shuō)明未發(fā)生其他修改，返回獲得的值
      • 應(yīng)避免在多線程情況下使用
  • 1.8
    • 放棄分段鎖，使用 CAS + synchronized 頭節(jié)點(diǎn)
    • 與 HashMap 類似，使用 數(shù)組+鏈表+紅黑樹(shù) 實(shí)現(xiàn)
    • Node<K,V> implements Map.Entry<K,V> 用于存儲(chǔ)鍵值對(duì)
    • TreeNode<K,V> extends Node<K,V> 用于放入 TreeBin 完成紅黑樹(shù)的轉(zhuǎn)換

  • ConcurrentHashMap總結(jié)