李文軒 2019-03-30
聲明：這是本人學(xué)習(xí)極客時(shí)間的Java核心36講的筆記，有侵權(quán)請(qǐng)聯(lián)系我。

Java的集合框架，此處不包括 Map 和 java.util.concurrent 下的線程安全容器

Hashtable、HashMap、TreeMap

• 都是 Map的實(shí)現(xiàn)，以鍵值對(duì)的形式存儲(chǔ)和操作數(shù)據(jù)的容器類型

• Hashtable是哈希表的實(shí)現(xiàn)，是同步的，性能開銷比較大；具備無序特性；不支持 null鍵和值

• HashMap也是哈希表的實(shí)現(xiàn)，不是同步的，所以比較常用；具備無序特性；支持null鍵和值；put和get操作都達(dá)到常數(shù)時(shí)間的性能

• TreeMap是基于紅黑樹的一種提供順序訪問的Map；get、put、remove之類的基本操作都是O(log(n))的時(shí)間復(fù)雜度。具體順序由Comparator或鍵的自由順序決定；所以一般需要排序?qū)η闆r下是選擇它。默認(rèn)升序排序方式。當(dāng)未實(shí)現(xiàn)Comparator或在實(shí)現(xiàn)中未對(duì)null情況進(jìn)行判斷時(shí)，key不能為null。

• 同樣是可以保證某種順序，LinkedHashMap通常提供的是遍歷順序符合插入順序，它的實(shí)現(xiàn)是通過為鍵值對(duì)維護(hù)一個(gè)雙向鏈表

線程安全（來自評(píng)論區(qū)）

• HashMap本身是不支持同步的；Hashtable因?yàn)橥ㄟ^阻塞狀態(tài)的方式，所以在多線程下也會(huì)效率低下
• 建議可以使用Collection的synchronizedMap方法 或者 ConcurrentHashMap類
  • ConcurrentHashMap類是基于lock實(shí)現(xiàn)鎖分段
  • 將Map存放的數(shù)據(jù)分成一段一段的存儲(chǔ)方式，然后給每一段數(shù)據(jù)分配一把鎖，當(dāng)一個(gè)線程占用鎖訪問其中一個(gè)段的數(shù)據(jù)時(shí)，其他段的數(shù)據(jù)也能被其他線程訪問。
  • ConcurrentHashMap不僅保證了多線程運(yùn)行環(huán)境下的數(shù)據(jù)訪問安全性，而且性能上有長(zhǎng)足的提升。

Map 整體結(jié)構(gòu)

• Hashtable比其他Map要不同，它是擴(kuò)展了Dictionary類的

• 其他Map都是擴(kuò)展類AbstractMap的，里面包含類通用方法抽象。設(shè)計(jì)目的一句體現(xiàn)在不用接口上。

• 大部分Map的使用場(chǎng)景都是，放入、訪問或者刪除，對(duì)順序沒有要求；HashMap的性能較好，它是一般情況的最好選擇。

• HashMap的性能依賴于哈希值的有效性：

  • equals相等，hashCode一定也要相等
  • 重寫了hashCode也要重寫equals
  • hashCode需要保持一致性，狀態(tài)改變返回的哈希值仍然要一致
  • equals的對(duì)稱、反射、傳遞等特性
  • compareTo的返回值需要和equals一致，否則會(huì)出香模凌兩可的情況

• LinkedHashMap通過特定構(gòu)造函數(shù)，可以創(chuàng)建反映訪問順序的實(shí)例

• 比如如果想建造一個(gè)空間敏感的資源池，我們希望在新資源加入時(shí)，同時(shí)釋放最不常用的一個(gè)數(shù)據(jù)

import java.util.LinkedHashMap;
import java.util.Map;  
public class LinkedHashMapSample {
    public static void main(String[] args) {
        LinkedHashMap<String, String> accessOrderedMap = new LinkedHashMap<String, String>(16, 0.75F, true){
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, String> eldest) { // 實(shí)現(xiàn)自定義刪除策略，否則行為就和普遍 Map 沒有區(qū)別
                return size() > 3;
            }
        };
        accessOrderedMap.put("Project1", "Valhalla");
        accessOrderedMap.put("Project2", "Panama");
        accessOrderedMap.put("Project3", "Loom");
        accessOrderedMap.forEach( (k,v) -> {
            System.out.println(k +":" + v);
        });
        // 模擬訪問
        accessOrderedMap.get("Project2");
        accessOrderedMap.get("Project2");
        accessOrderedMap.get("Project3");
        System.out.println("Iterate over should be not affected:");
        accessOrderedMap.forEach( (k,v) -> {
            System.out.println(k +":" + v);
        });
        // 觸發(fā)刪除
        accessOrderedMap.put("Project4", "Mission Control");
        System.out.println("Oldest entry should be removed:");
        accessOrderedMap.forEach( (k,v) -> {// 遍歷順序不變
            System.out.println(k +":" + v);
        })
    }
}

• 這段代碼限制了資源池size為3，當(dāng)“project4“加入時(shí)，同時(shí)刪除了”project1“

HashMap源碼

• HashMap內(nèi)部實(shí)現(xiàn)基本點(diǎn)

• 可以看作一個(gè)數(shù)組和鏈表結(jié)合的復(fù)合結(jié)構(gòu)，數(shù)組被分為桶（bucket）
• 用哈希值決定了鍵值對(duì)屬于哪個(gè)桶

• 容量（capacity)和負(fù)載系數(shù)（load factor）。

  • 容量理論最大極限由 MAXIMUM_CAPACITY指定，數(shù)值為2的30次方
  • 在源碼的putVal方法里可以看出，resize方法處理了幾個(gè)問題：
    • 在表格是null的時(shí)候，resize方法會(huì)負(fù)責(zé)初始化
    • resize也負(fù)責(zé)擴(kuò)容；新插入的鍵值對(duì)會(huì)檢查++size > threshold；若true，則調(diào)用resize
  • 門閥值threshold等于（負(fù)載因子）*（容量），判斷是否擴(kuò)容的關(guān)鍵
  • 門閥值通常以倍數(shù)調(diào)整，當(dāng)元素?cái)?shù)量超過門閥值時(shí)，調(diào)整Map大小。
  • 而容量和負(fù)載因子決定了可用的桶的數(shù)量；若只使用一個(gè)桶，HashMap會(huì)退回鏈表的狀態(tài)

• 樹化

  • 邏輯主要存在于putVal和treeifyBin中
  • 主要注意的是，如果桶里的元素?cái)?shù)量大于TREEIFY_THRESHOLD
    • 如果容量小于MIN_TREEIFY_CAPACITY，只會(huì)進(jìn)行簡(jiǎn)單擴(kuò)容
    • 如果容量大于MIN_TREEIFY_CAPACITY，則是進(jìn)行樹化改造
  • 樹化大主要原因是安全問題，若大部分鍵值對(duì)處于一個(gè)bin中，則會(huì)形成一個(gè)鏈表
    • 構(gòu)造哈希沖突從而導(dǎo)致服務(wù)器CPU大量占用（鏈表查詢?yōu)榫€性，嚴(yán)重影響存?。┦潜容^簡(jiǎn)單的攻擊手段

重寫 hashCode 和 equals 方法

• 如果我們要將自定義類當(dāng)作鍵加入到HashMap中，如果不重寫，結(jié)果可能和我們預(yù)想的不太一樣

• 如果我們沒有重寫自定義對(duì)象的hashCode方法，在作為鍵加入到HashMap里時(shí)調(diào)用hashCode方法的時(shí)候，程序?qū)⒄{(diào)用Object里的hashCode方法，即返回對(duì)象的內(nèi)存地址。這并不是我們所期待的。

• 重寫可以調(diào)用Object.hash(Object...values)方法，或xx.hashCode()

• 如果我們沒有重寫自定義對(duì)象的equals方法，即使我們用同樣哈希值去找HashMap里的值的時(shí)候，get會(huì)返回null。因?yàn)槲覀儧]有重寫equals的話，程序自動(dòng)調(diào)用Object里的equals方法；這個(gè)固定方法是比較鍵的內(nèi)存地址的，所以即使用同樣的哈希值的不同對(duì)象，返回的依然是null。

• 重寫可以先檢查是否是null對(duì)象和是否同一類型的對(duì)象。如果不是null和是同一類型，那么可以逐個(gè)對(duì)比兩個(gè)對(duì)象里的成員變量

• 兩個(gè)equals返回true的對(duì)象一定有一樣的hashCode，但是兩個(gè)有相同hashCode的對(duì)象不一定equals返回true。因?yàn)?code>hashCode其實(shí)作為一個(gè)對(duì)象存儲(chǔ)的參數(shù)存在于對(duì)象中，有可能兩個(gè)對(duì)象有相同的hashCode，但是他們的成員變量不一定都是相等；一定是所以成員變量相等和同一對(duì)象類型的兩個(gè)對(duì)象才相等。