Map (interface)
├── HashMap (class)
│   └── LinkedHashMap (class)
├── TreeMap (class)
├── Hashtable (class)
│   └── Properties (class)
└── ConcurrentMap (interface)
    └── ConcurrentHashMap (class)

// 默認(rèn)初始容量16，必須是2的n次冪
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默認(rèn)負(fù)載因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 鏈表轉(zhuǎn)紅黑樹(shù)閾值
static final int TREEIFY_THRESHOLD = 8;
// 紅黑樹(shù)轉(zhuǎn)鏈表閾值
static final int UNTREEIFY_THRESHOLD = 6;
// 樹(shù)化最小數(shù)組容量
static final int MIN_TREEIFY_CAPACITY = 64;

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 1. 數(shù)組延遲初始化：首次put時(shí)創(chuàng)建數(shù)組
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2. 計(jì)算下標(biāo)，如果該位置為空直接插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 3. 處理Hash沖突
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // 第一個(gè)節(jié)點(diǎn)就是要找的key
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 紅黑樹(shù)插入
        else {
            // 鏈表遍歷
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null); // 尾插法
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash); // 檢查是否需要樹(shù)化
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 4. 找到相同key，替換value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 5. 檢查是否需要擴(kuò)容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 計(jì)算新容量
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 容量翻倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 閾值也翻倍
    }
    // ... 初始化邏輯
    // 創(chuàng)建新數(shù)組
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 數(shù)據(jù)遷移
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    // 單個(gè)節(jié)點(diǎn)直接重新計(jì)算下標(biāo)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 紅黑樹(shù)拆分
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
                    // 鏈表拆分：保持原順序
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 關(guān)鍵優(yōu)化：根據(jù)hash值新增位判斷新位置
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        } else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                        e = next;
                    } while (e != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead; // 原索引位置
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead; // 原索引+舊容量
                    }
                }
            }
        }
    }
    return newTab;
}

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after; // 前驅(qū)和后繼指針
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

// 指定訪(fǎng)問(wèn)順序
Map<String, String> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("a", "1");
map.put("b", "2");
map.get("a"); // 訪(fǎng)問(wèn)a，a會(huì)被移動(dòng)到鏈表尾部
// 迭代順序：b, a（最近訪(fǎng)問(wèn)的在最后）

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxCapacity;
    public LRUCache(int maxCapacity) {
        super(16, 0.75f, true); // 啟用訪(fǎng)問(wèn)順序
        this.maxCapacity = maxCapacity;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxCapacity; // 超過(guò)容量時(shí)移除最久未訪(fǎng)問(wèn)的元素
    }
}

// 自然排序：鍵必須實(shí)現(xiàn)Comparable
TreeMap<Integer, String> naturalMap = new TreeMap<>();
// 定制排序：提供Comparator
TreeMap<String, Integer> customMap = new TreeMap<>(
    (s1, s2) -> s2.compareTo(s1) // 降序
);

TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "one");
map.put(3, "three");
map.put(5, "five");
map.put(7, "seven");
Integer firstKey = map.firstKey();        // 1
Integer lastKey = map.lastKey();          // 7
Integer lowerKey = map.lowerKey(5);       // 3（小于5的最大鍵）
Integer floorKey = map.floorKey(4);       // 3（小于等于4的最大鍵）
Integer ceilingKey = map.ceilingKey(4);   // 5（大于等于4的最小鍵）
Integer higherKey = map.higherKey(5);     // 7（大于5的最小鍵）
// 子Map視圖
SortedMap<Integer, String> headMap = map.headMap(5);   // 鍵<5的部分
SortedMap<Integer, String> tailMap = map.tailMap(5);   // 鍵>=5的部分
SortedMap<Integer, String> subMap = map.subMap(3, 6);  // 3<=鍵<6

final int compare(Object k1, Object k2) {
    return comparator == null ? 
        ((Comparable<? super K>)k1).compareTo((K)k2) : 
        comparator.compare((K)k1, (K)k2);
}

Hashtable<String, Integer> table = new Hashtable<>();
table.put("key", 1);
// table.put(null, 2); // 運(yùn)行時(shí)異常

Properties props = new Properties();
props.setProperty("url", "jdbc:mysql://localhost:3306/db");
props.setProperty("username", "root");
props.setProperty("password", "123456");
// 加載配置文件
try (InputStream input = new FileInputStream("config.properties")) {
    props.load(input);
    String url = props.getProperty("url");
    String username = props.getProperty("username");
}

static final class Segment<K,V> extends ReentrantLock implements Serializable {
    transient volatile HashEntry<K,V>[] table;
    // ...
}

// putVal核心片段
final V putVal(K key, V value, boolean onlyIfAbsent) {
    // ... 非空校驗(yàn)等
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable(); // 初始化，CAS保證線(xiàn)程安全
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 該位置為空，CAS嘗試插入
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                break;
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f); // 幫助擴(kuò)容
        else {
            V oldVal = null;
            synchronized (f) { // 鎖住鏈表頭節(jié)點(diǎn)
                // 鏈表或紅黑樹(shù)操作
            }
        }
    }
}

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
// forEach：遍歷每個(gè)元素
map.forEach(1, (k, v) -> System.out.println(k + ":" + v));
// search：查找第一個(gè)符合條件的元素
String result = map.search(1, (k, v) -> v > 100 ? k : null);
// reduce：累加操作
Integer sum = map.reduceValues(1, Integer::sum);
// 用作頻率統(tǒng)計(jì)（MultiSet）
ConcurrentHashMap<String, LongAdder> freqs = new ConcurrentHashMap<>();
freqs.computeIfAbsent("word", k -> new LongAdder()).increment();

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

for (String key : map.keySet()) {
    System.out.println(key + ": " + map.get(key));
}
// 缺點(diǎn)：每次get都需要二次查找，效率較低

for (Integer value : map.values()) {
    System.out.println(value);
}

Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, Integer> entry = iterator.next();
    if (entry.getValue() < 0) {
        iterator.remove(); // 安全刪除
    }
}

map.forEach((key, value) -> System.out.println(key + ": " + value));

// 如果key不存在，則通過(guò)函數(shù)計(jì)算value并放入Map
map.computeIfAbsent("key", k -> new ArrayList<>()).add("value");
// 經(jīng)典用法：實(shí)現(xiàn)多值Map
Map<String, List<String>> multiMap = new HashMap<>();
multiMap.computeIfAbsent("group1", k -> new ArrayList<>()).add("item1");
// 如果key存在，則根據(jù)原值計(jì)算新值
map.computeIfPresent("key", (k, v) -> v * 2);

// 合并操作：如果key不存在則放入給定值，存在則通過(guò)合并函數(shù)計(jì)算新值
map.merge("key", 1, Integer::sum); // 統(tǒng)計(jì)功能
// 經(jīng)典用法：?jiǎn)卧~計(jì)數(shù)
String text = "apple banana apple orange apple";
Map<String, Integer> wordCount = new HashMap<>();
for (String word : text.split(" ")) {
    wordCount.merge(word, 1, Integer::sum);
}
// 結(jié)果：{apple=3, banana=1, orange=1}

// 僅在key不存在時(shí)放入
map.putIfAbsent("key", "value");

// 替換指定key的值（僅當(dāng)存在時(shí)）
map.replace("key", "newValue");
// 對(duì)所有entry應(yīng)用替換函數(shù)
map.replaceAll((k, v) -> v.toUpperCase());

// 創(chuàng)建不可變Map（最多支持10對(duì)鍵值）
Map<String, Integer> map1 = Map.of(
    "a", 1,
    "b", 2,
    "c", 3
);
// 任意數(shù)量鍵值對(duì)
Map<String, Integer> map2 = Map.ofEntries(
    Map.entry("a", 1),
    Map.entry("b", 2),
    Map.entry("c", 3),
    Map.entry("d", 4)
);

// 錯(cuò)誤示例
Map<List<String>, String> map = new HashMap<>();
List<String> key = new ArrayList<>();
key.add("a");
map.put(key, "value1");
key.add("b"); // 鍵被修改，hashCode改變
map.get(key); // 返回null，再也找不到
map.containsKey(key); // false

class User {
    String name;
    // 沒(méi)有重寫(xiě)hashCode和equals
}
Map<User, Integer> map = new HashMap<>();
User u1 = new User("Alice");
User u2 = new User("Alice");
map.put(u1, 100);
map.get(u2); // 返回null，雖然內(nèi)容相同

Map<String, Integer> map = new HashMap<>();
// ... 填充數(shù)據(jù)
for (String key : map.keySet()) {
    if (key.startsWith("temp")) {
        map.remove(key); // 拋出ConcurrentModificationException
    }
}

// 方式1：使用Iterator的remove
Iterator<String> it = map.keySet().iterator();
while (it.hasNext()) {
    String key = it.next();
    if (key.startsWith("temp")) {
        it.remove();
    }
}
// 方式2：使用removeIf（Java 8+）
map.keySet().removeIf(key -> key.startsWith("temp"));
// 方式3：使用ConcurrentHashMap（允許并發(fā)修改）

Map<String, Integer> map = new HashMap<>(expectedSize * 4 / 3 + 1);

// 老式
if (!map.containsKey(key)) {
    map.put(key, new ArrayList<>());
}
map.get(key).add(value);
// 新式
map.computeIfAbsent(key, k -> new ArrayList<>()).add(value);