一更米、區(qū)別總結(jié)

1??HashMap 是非線程安全的欺栗，不適用于多線程資源共享場景，在單線程場景下性能最好征峦。在多線程環(huán)境中迟几，需要手動實現(xiàn)同步機制。HashMap 中栏笆，null 可以作為鍵类腮，這樣的鍵只有一個，但可以有一個或多個鍵所對應(yīng)的值為 null蛉加。當(dāng) get() 返回 null 時蚜枢，既可以表示 HashMap 中沒有該 key，也可以表示該 key 所對應(yīng)的 value 為 null针饥。因此厂抽，在 HashMap 中不能用 get() 來判斷是否存在某個 key，應(yīng)該用 containsKey() 來判斷丁眼。

2??Hashtable 的 API 都是 sychronized 的筷凤，因此是線程安全的，可以直接用在多線程環(huán)境中苞七。由于 Hashtable 中的所有數(shù)據(jù)都加了同步鎖藐守，因此性能最差。Hashtable 中蹂风，無論是 key 還是 value 都不能為 null卢厂。

3??HashMap 的迭代器(Iterator)是 fail-fast 迭代器，而 Hashtable 的 enumerator 迭代器不是 fail-fast 的硫眨。所以當(dāng)有其它線程改變了 HashMap 的結(jié)構(gòu)(增加或者移除元素)足淆，將會拋出 ConcurrentModificationException巢块，但迭代器本身的 remove() 移除元素則不會拋出 ConcurrentModificationException。但這并不是一定發(fā)生的行為巧号，要看 JVM族奢。

4??Hashtable 和 HashMap 都實現(xiàn)了 Map 接口，但是 Hashtable 的實現(xiàn)是基于 Dictionary 抽象類的丹鸿。Java5 提供了 ConcurrentHashMap越走，它是 Hashtable 的替代，比 Hashtable 的擴展性更好靠欢。ConcurrentHashMap 在 HashMap 的基礎(chǔ)上對其所存的數(shù)據(jù)進行了分段廊敌，每個分段都有一個鎖，當(dāng)讀的時候不受鎖的影響门怪，只有在寫的時候受鎖的限制骡澈，縮小了鎖的范圍，不同段之間不受鎖競爭影響掷空，既保證了線程安全肋殴，又提升了性能。ConcurrentHashMap 類是 Java 并發(fā)包 java.util.concurrent中提供的一個線程安全且高效的 HashMap 實現(xiàn)坦弟。在 JDK7 中采用分段鎖的方式护锤；JDK8 中直接采用了 CAS(無鎖算法)+ sychronized。

5??Segment 類繼承于 ReentrantLock 類酿傍，從而使得 Segment 對象能充當(dāng)鎖的角色烙懦。每個 Segment 對象用來守護其(成員對象 table 中)包含的若干個桶。

table 是一個由 HashEntry 對象組成的數(shù)組赤炒。table 數(shù)組的每一個數(shù)組成員就是散列映射表的一個桶氯析。

count 變量是一個計數(shù)器，它表示每個 Segment 對象管理的 table 數(shù)組(若干個 HashEntry 組成的鏈表)包含的 HashEntry 對象的個數(shù)可霎。每一個 Segment 對象都有一個 count 對象來表示本 Segment 中包含的 HashEntry 對象的總數(shù)魄鸦。注意，之所以在每個 Segment 對象中包含一個計數(shù)器癣朗，而不是在 ConcurrentHashMap 中使用全局的計數(shù)器拾因，是為了避免出現(xiàn)“熱點域”而影響 ConcurrentHashMap 的并發(fā)性。

二旷余、ConcurrentHashMap(線程安全)

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

從類圖可看出在存儲結(jié)構(gòu)中 ConcurrentHashMap 比 HashMap 多出了一個類 Segment昌执，而 Segment 是一個可重入鎖烛亦。ConcurrentHashMap 是使用了鎖分段技術(shù)來保證線程安全的诈泼。

鎖分段技術(shù)：
首先將數(shù)據(jù)分成一段一段的存儲懂拾，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個線程占用鎖訪問其中一個段數(shù)據(jù)的時候铐达，其他段的數(shù)據(jù)仍能被其他線程訪問岖赋。

ConcurrentHashMap 提供了與 Hashtable 和 SynchronizedMap 不同的鎖機制。Hashtable 中采用的鎖機制是一次鎖住整個 hash 表瓮孙，從而在同一時刻只能由一個線程對其進行操作唐断；而 ConcurrentHashMap 中則是一次鎖住一個桶。

ConcurrentHashMap 默認將 hash 表分為16個桶杭抠，諸如 get脸甘、put、remove 等常用操作只鎖住當(dāng)前需要用到的桶偏灿。這樣丹诀，原來只能一個線程進入，現(xiàn)在卻能同時有16個寫線程執(zhí)行翁垂，并發(fā)性能的提升是顯而易見的铆遭。

三、Hashtable(線程安全)

• 底層采用數(shù)組+鏈表實現(xiàn)沿猜。key 和 value 都不能為 null枚荣。實現(xiàn)線程安全的方式是在修改數(shù)據(jù)時鎖住整個 Hashtable，效率低啼肩。
• 初始 size 為11橄妆，擴容：newsize = oldsize*2+1
• 計算 index 的方法：index = (hash & 0x7FFFFFFF) % tab.length

四衙伶、hash表的屬性：加載因子/負載極限

1??HashMap 和 Hashtable 都是用 hash 算法來決定其元素的存儲，因此HashMap 和 Hashtable 的 hash 表包含如下屬性：
①容量(capacity)：hash 表中桶(buckets)的數(shù)量害碾；圖中的標(biāo)有0痕支、1、2蛮原、3 … 11所對應(yīng)的數(shù)組空間就是一個個桶卧须。
②初始化容量(initial capacity)：創(chuàng)建 hash 表時桶的數(shù)量，HashMap 允許在構(gòu)造器中指定初始化容量儒陨；
③尺寸(size)：當(dāng)前 hash 表中記錄的數(shù)量花嘶；
④加載因子(load factor)：加載因子等于“size/capacity”。加載因子為0蹦漠，表示空的hash表椭员，0.5表示半滿的散列表，依此類推笛园。輕負載的散列表具有沖突少隘击、適宜插入與查詢的特點(但是使用Iterator迭代元素時比較慢)。
除此之外研铆，hash表里還有一個“負載極限”埋同，“負載極限”是一個0～1的數(shù)值，“負載極限”決定了hash表的最大填滿程度棵红。當(dāng)hash表中的加載因子達到指定的“負載極限”時凶赁，hash表會自動成倍地增加容量(桶的數(shù)量)，并將原有的對象重新分配逆甜，放入新的桶內(nèi)虱肄，這稱為rehashing。
加載因子：為了降低哈希沖突的概率交煞，默認當(dāng)HashMap中的鍵值對達到數(shù)組大小的75%時咏窿，即會觸發(fā)擴容。因此素征，如果預(yù)估容量是75集嵌，即需要設(shè)定75/0.75＝100的數(shù)組大小。
⑤哈希沖突：若干Key的哈希值按數(shù)組大小取模后稚茅，如果落在同一個數(shù)組下標(biāo)上纸淮，將組成一條Entry鏈，對Key的查找需要遍歷Entry鏈上的每個元素執(zhí)行equals()比較亚享。
⑥空間換時間：如果希望加快Key查找的時間咽块，還可以進一步降低加載因子，加大初始大小欺税，以降低哈希沖突的概率侈沪。

HashMap 和 Hashtable的構(gòu)造器允許指定一個負載極限揭璃，HashMap 和 Hashtable默認的“負載極限”為0.75，這表明當(dāng)該hash表的3/4已經(jīng)被填滿時亭罪，hash 表會發(fā)生 rehashing瘦馍。

2??“負載極限”值可以根據(jù)實際情況來調(diào)整，默認值(0.75)是時間和空間成本上的一種折中：

• 較高的“負載極限”可以降低 hash 表所占用的內(nèi)存空間应役，但會增加查詢數(shù)據(jù)的時間開銷情组，而查詢是最頻繁的操作。HashMap 的 get() 與 put() 都要用到查詢
• 較低的“負載極限”會提高查詢數(shù)據(jù)的性能箩祥，但會增加 hash 表所占用的內(nèi)存開銷院崇。

3??影響 HashMap 性能的兩個因素：哈希表中的初始化容量(桶的數(shù)量)和加載因子
當(dāng)哈希表中條目數(shù)超過了當(dāng)前容量與加載因子的乘積時，哈希表將會作出自我調(diào)整袍祖，將容量擴充為原來的兩倍底瓣，并且重新將原有的元素重新映射到表中，這一過程成為 rehash蕉陋。rehash 操作是會造成時間與空間的開銷的捐凭，因此初始化容量與加載因子會影響 HashMap 的性能。