Hashmap：
數(shù)組+鏈表
通過hash函數(shù)計算下標(biāo)值

哈希沖突解決辦法：開放尋址法，再散列函數(shù)法，鏈地址法

HashMap的主干是一個Entry數(shù)組。Entry是HashMap的基本組成單元，每一個Entry包含一個key-value鍵值對
Entry里面存了key value hash next

默認(rèn)16 到達(dá)加載因子0.75 每次翻倍

為什么大小一定是2的整數(shù)次冪：
因為數(shù)組下表index = h&(length-1)，保證index一定在數(shù)組范圍內(nèi)
每次擴容后只要最左位為0，就能保證索引值一致
高位也不會對計算產(chǎn)生影響，低位更加散列

重寫equals方法的時候要重寫hashcode方法，不然可能導(dǎo)致存取的時候hashcode值不相等找不到對應(yīng)的索引值

Hashtable：
底層數(shù)組+鏈表實現(xiàn)，無論key還是value都不能為null，線程安全，實現(xiàn)線程安全的方式是在修改數(shù)據(jù)時鎖住整個HashTable，效率低，ConcurrentHashMap做了相關(guān)優(yōu)化
初始size為11，擴容：2*n+1
計算index的方法：index = (hash & 0x7FFFFFFF) % tab.length

ConcurrentHashMap
底層采用分段的數(shù)組+鏈表實現(xiàn)，線程安全
通過把整個Map分為N個Segment，可以提供相同的線程安全，但是效率提升N倍，默認(rèn)提升16倍。(讀操作不加鎖，由于HashEntry的value變量是 volatile的，也能保證讀取到最新的值。)
Hashtable的synchronized是針對整張Hash表的，即每次鎖住整張表讓線程獨占，ConcurrentHashMap允許多個修改操作并發(fā)進(jìn)行，其關(guān)鍵在于使用了鎖分離技術(shù)
有些方法需要跨段，比如size()和containsValue()，它們可能需要鎖定整個表而而不僅僅是某個段，這需要按順序鎖定所有段，操作完畢后，又按順序釋放所有段的鎖
擴容：段內(nèi)擴容（段內(nèi)元素超過該段對應(yīng)Entry數(shù)組長度的75%觸發(fā)擴容，不會對整個Map進(jìn)行擴容），插入前檢測需不需要擴容，有效避免無效擴容