Map

介面大致說明(jdk11):

整體介紹:

一個將鍵映射到值的(key-value)對象, 鍵值(key)不能重覆, 每個鍵值只能影射一個對象(一一對應).

這個介面取代了Dictionary類，後者是一個完全抽象的類，而不是一個介面。

Map介面提供了三個集合視圖(Set<K> keySet(); Collection<V> values();, Set<Map.Entry<K, V>> entrySet();)，允許將Map的內容視為一組鍵、一組值或一組鍵-值映射。映射的順序被定義為映射集合視圖上的迭代器返回元素的順序。一些映射實現，比如TreeMap類，對它們的順序做出了特定的保證;其他類，比如HashMap，則不需要。
註意: 如果使用可變對象作為映射鍵，必須非常小心。這種情況下equals和hashCode方法會很難定義...最好別用.

所有通用映射實現類都應該提供兩個“標準”構造函數:一個是void(無參數)構造函數，它創建一個空映射;另一個是帶有一個類型為map的參數的構造函數，它創建一個具有與它的參數相同的鍵-值映射的新映射。實際上，後一個構造函數允許用戶複製任何映射，生成所需類的等效映射。雖然沒有辦法強制執行這一規範(因為介面不能包含構造函數)，但是JDK中的所有通用映射實現都遵循這一規範。

此介面中包含的“破壞性”方法，即修改它們所操作的映射的方法，被指定為在該映射不支持操作時拋出UnsupportedOperationException。如果調用對映射沒有影響，這些方法可能(但不是必需的)拋出UnsupportedOperationException。例如，在不可修改的映射上調用putAll(Map)方法，如果要“疊加”的映射為空的映射可能(但不是必需的)拋出異常。

有些map實現對它們可能包含的鍵和值有限制。例如，有些實現禁止空鍵和值，而有些則限制其鍵的類型。試圖插入不合格的鍵或值會拋出未檢查的異常，通常是NullPointerException或ClassCastException。試圖查詢是否存在不合格的鍵或值可能會拋出異常，或者它可能僅僅返回false;有些實現會顯示前一種行為，有些則會顯示後一種行為。更普遍的情況是，嘗試對不符合條件的鍵或值執行操作，如果完成操作不會導致在映射中插入不符合條件的元素，則可能會拋出異常或成功，具體取決於實現的選項。這種異常在該介面的規範中被標記為“可選”。

集合框架介面中的許多方法都是根據equals方法定義的。
例如，containsKey(對象鍵)方法的規範說:“當且僅當這個映射包含一個鍵k的映射，這樣(key==null ?k = = null: key.equals (k))。”此規範不應被解釋為暗示調用映射。包含一個非空參數key的containsKey會導致key.equals(k)被任何key k調用。實現可以自由地實現優化，從而避免調用equals.
例如，首先比較兩個key的哈希碼。(Object.hashCode()規範保證兩個哈希碼不相等的對象不能相等。)更普遍的是，在實現者認為合適的地方，各種集合框架介面的實現可以自由地利用底層對象方法的指定行為。

不可變的Map:

Map.of, Map.ofEntries, Map.copyOf靜態工廠方法提供了一種創建不可修改映射的方便方法。這些方法創建的映射實例具有以下特征:

• 他們是無法改變的。不能添加、刪除或更新鍵和值。調用映射上的任何mutator方法總是會導致拋出UnsupportedOperationException。但是，如果包含的鍵或值本身是可變的，這可能會導致映射的行為不一致或其內容似乎發生了變化。
• 它們不允許空鍵和值。嘗試使用空鍵或值創建它們會導致NullPointerException。
• 如果所有鍵和值都是可序列化的，則它們是可序列化的。
• 它們在創建時拒絕重覆的key。傳遞給靜態工廠方法的重覆鍵會導致IllegalArgumentException異常。
• 映射的迭代順序是未指定的，並且可能會更改
• value值如果是對象的話,是不完全可靠的.有可能會發生變化.
• 它們被序列化為在序列化表單頁面上指定的格式。

常用類繼承結構

方法介紹

查詢操作

/** 
 * 返回此映射中鍵-值映射的數目。如果映射包含超過整數。MAX_VALUE元素，返回整數。MAX_VALUE。
 * @return 該映射中鍵-值映射的數量
 */
int size();

/**
 * 判斷是否為空
 */
boolean isEmpty();

/**
 * 判斷傳入的鍵值在該map中是否存在.
 * 等於 Objects.equals(key, k) (最多只能有一個這樣的映射)
 */
boolean containsKey(Object key);

/**
 * 如果此映射將一個或多個鍵映射到指定的值，則返回true。
 * 更正式地說，當且僅當這個映射包含至少一個到值v的映射時，返回true。
 * 對於大多數map介面的實現來說，這個操作可能需要映射大小的線性時間。(時間複雜度為O(n))
 */
boolean containsValue(Object value);

/**
 * 返回指定鍵映射到的值，如果該映射不包含該鍵的映射，則返回null。
 */
V get(Object key);

修改操作

/**
 * 將此映射中的指定值與指定鍵關聯(可選操作)。
 * 如果映射以前包含該鍵的映射，則舊值將被指定的值替換。
 * (當且僅當m. containskey (k)返回true時，映射m被稱為包含鍵k的映射。
 */
V put(K key, V value);

/**
 * 如果密鑰存在，則從該映射中刪除該密鑰的映射(可選操作)。
 * 返回此映射以前與鍵關聯的值，如果映射不包含該鍵的映射，則返回null。
 * 如果該映射允許空值，那麼null的返回值並不一定表明該映射不包含該鍵的映射;映射也可能顯式地將鍵映射為null。
 * 一旦調用返回，映射將不包含指定鍵的映射
 */
V remove(Object key);

批量處理

/**
 * 將指定映射中的所有映射複製到此映射(可選操作)。
 * 這個調用的效果相當於對指定映射中從鍵k到值v的每個映射在這個映射上調用一次put(k, v)。
 * 如果在操作過程中修改了指定的映射，則此操作的行為未定義。
 */
void putAll(Map<? extends K, ? extends V> m);

/**
 * 從該映射中刪除所有映射(可選操作)。此調用返回後映射將為空。
 */
void clear();

視圖

/**
 * 返回此映射中包含的鍵的Set視圖。
 * 集合受到映射的支持，因此對映射的更改反映在集合中，反之亦然。
 * 如果在對集合進行迭代時修改了映射(迭代器自己的刪除操作除外)，那麼迭代的結果是未定義的。
 * 這個集合支持元素刪除，從Map中刪除相應的映射,
 * 通過remove、Set.remove、removeAll、retainAll和clear操作。
 * 它不支持add或addAll操作。
 */
Set<K> keySet();

/**
 * 返回此映射中包含的值的Collection視圖。
 * 映射支持集合，因此對映射的更改反映在集合中，反之亦然。
 * 如果在對集合進行迭代時修改了映射(迭代器自己的刪除操作除外)，那麼迭代的結果是未定義的。
 * 集合支持元素刪除，元素刪除通過迭代器從映射中刪除相應的映射,通過Iterator.remove, Set.remove, removeAll, retainAll和clear操作。
 * 它不支持add或addAll操作。
 */
Collection<V> values();

/**
 * 迭代的是map中的key-val映射實體(Entry), 其它的與上面倆差不多
 */
Set<Map.Entry<K, V>> entrySet();

比較和散列

/**
 * 比較指定的對象與此映射是否相等。
 * 如果給定的對象也是映射，並且這兩個映射表示相同的映射，則返回true。
 * 更正式地說，兩個映射m1和m2表示相同的映射，如果m1. entryset ().equals(m2. entryset())。
 * 這確保了equals方法在Map介面的不同實現之間正常工作。
 */
boolean equals(Object o);

/**
 * 返回此映射的哈希碼值。
 * 映射的哈希碼被定義為映射的entrySet()視圖中每個條目的哈希碼的和。
 * 這確保了m1.equals(m2)意味著對於任意兩個映射m1和m2, m1. hashcode ()==m2. hashcode()，這是Object.hashCode的一般契約所要求的。
 */
int hashCode();

預設方法 (jdk1.8提供的)

/**
 * 獲取key對應的值, 如果沒有就返回傳入的預設值
 */
default V getOrDefault(Object key, V defaultValue) {
    V v;
    return (((v = get(key)) != null) || containsKey(key))
        ? v
        : defaultValue;
}

/**
 * foreach迭代
 * 例子: 
 * for (Map.Entry<K, V> entry : map.entrySet())
 *  action.accept(entry.getKey(), entry.getValue());
 * }
 */
default void forEach(BiConsumer<? super K, ? super V> action) {
    Objects.requireNonNull(action);
    for (Map.Entry<K, V> entry : entrySet()) {
        K k;
        V v;
        try {
            k = entry.getKey();
            v = entry.getValue();
        } catch (IllegalStateException ise) {
            // this usually means the entry is no longer in the map.
            throw new ConcurrentModificationException(ise);
        }
        action.accept(k, v);
    }
}

/**
 * 遍歷過程中對值進行替換
 * 例子: 
 * for (Map.Entry<K, V> entry : map.entrySet())
 *  entry.setValue(function.apply(entry.getKey(), entry.getValue()));
 * }
 */
default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
    Objects.requireNonNull(function);
    for (Map.Entry<K, V> entry : entrySet()) {
        K k;
        V v;
        try {
            k = entry.getKey();
            v = entry.getValue();
        } catch (IllegalStateException ise) {
            // this usually means the entry is no longer in the map.
            throw new ConcurrentModificationException(ise);
        }

        // ise thrown from function is not a cme.
        v = function.apply(k, v);

        try {
            entry.setValue(v);
        } catch (IllegalStateException ise) {
            // this usually means the entry is no longer in the map.
            throw new ConcurrentModificationException(ise);
        }
    }
}

/**
 * 如果指定的鍵尚未與值關聯(或映射為null)，則將其與給定值關聯並返回null，否則返回當前值。
 */
default V putIfAbsent(K key, V value) {
    V v = get(key);
    if (v == null) {
        v = put(key, value);
    }

    return v;
}

/**
 * 僅當指定鍵項當前映射到指定值時才刪除該項。
 */
default boolean remove(Object key, Object value) {
    Object curValue = get(key);
    if (!Objects.equals(curValue, value) ||
        (curValue == null && !containsKey(key))) {
        return false;
    }
    remove(key);
    return true;
}

/**
 * 只有在key對應的value值與傳入的oldvalue相等時才替換並返回true, 否則返回false
 */
default boolean replace(K key, V oldValue, V newValue) {
    Object curValue = get(key);
    if (!Objects.equals(curValue, oldValue) ||
        (curValue == null && !containsKey(key))) {
        return false;
    }
    put(key, newValue);
    return true;
}

/**
 * 如果key/value鍵值對存在就替換
 */
default V replace(K key, V value) {
    V curValue;
    if (((curValue = get(key)) != null) || containsKey(key)) {
        curValue = put(key, value);
    }
    return curValue;
}
// 用於流處理的
// 之後寫流處理的時候再整理吧...
default V computeIfAbsent(K key,
        Function<? super K, ? extends V> mappingFunction) {
    Objects.requireNonNull(mappingFunction);
    V v;
    if ((v = get(key)) == null) {
        V newValue;
        if ((newValue = mappingFunction.apply(key)) != null) {
            put(key, newValue);
            return newValue;
        }
    }

    return v;
}
default V computeIfPresent(K key,
        BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
    Objects.requireNonNull(remappingFunction);
    V oldValue;
    if ((oldValue = get(key)) != null) {
        V newValue = remappingFunction.apply(key, oldValue);
        if (newValue != null) {
            put(key, newValue);
            return newValue;
        } else {
            remove(key);
            return null;
        }
    } else {
        return null;
    }
}
default V compute(K key,
        BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
    Objects.requireNonNull(remappingFunction);
    V oldValue = get(key);

    V newValue = remappingFunction.apply(key, oldValue);
    if (newValue == null) {
        // delete mapping
        if (oldValue != null || containsKey(key)) {
            // something to remove
            remove(key);
            return null;
        } else {
            // nothing to do. Leave things as they were.
            return null;
        }
    } else {
        // add or replace old mapping
        put(key, newValue);
        return newValue;
    }
}
default V merge(K key, V value,
        BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
    Objects.requireNonNull(remappingFunction);
    Objects.requireNonNull(value);
    V oldValue = get(key);
    V newValue = (oldValue == null) ? value :
               remappingFunction.apply(oldValue, value);
    if (newValue == null) {
        remove(key);
    } else {
        put(key, newValue);
    }
    return newValue;
}

// 十一個of方法
    static <K, V> Map<K, V> of() {
        return ImmutableCollections.emptyMap();
    }
    
    static <K, V> Map<K, V> of(K k1, V v1) {
        return new ImmutableCollections.Map1<>(k1, v1);
    }
    
    static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2) {
        return new ImmutableCollections.MapN<>(k1, v1, k2, v2);
    }   
    
    static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) {
        return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3);
    }    
// ...剩下的都是ImmutableCollections.MapN<>接收可變長參數進行實現的
    
// ImmutableCollections 中的Map1 MapN
// static final class Map1<K,V> extends AbstractImmutableMap<K,V>
// static final class MapN<K,V> extends AbstractImmutableMap<K,V>
// 這倆都是繼承自AbstractImmutableMap
// 而AbstractImmutableMap繼承自AbstractMap, 把所有跟put相關的方法都預設返回UnsupportedOperationException()
// 在Map1 MapN中,都是只有構造函數可以接收參數並創建好需要的集合.
// 除構造方法之外沒有別的修改以創建好集合的方法.
abstract static class AbstractImmutableMap<K,V> extends AbstractMap<K,V> implements Serializable {
    @Override public void clear() { throw uoe(); }
    @Override public V compute(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); }
    @Override public V computeIfAbsent(K key, Function<? super K,? extends V> mf) { throw uoe(); }
    @Override public V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> rf) { throw uoe(); }
    @Override public V merge(K key, V value, BiFunction<? super V,? super V,? extends V> rf) { throw uoe(); }
    @Override public V put(K key, V value) { throw uoe(); }
    @Override public void putAll(Map<? extends K,? extends V> m) { throw uoe(); }
    @Override public V putIfAbsent(K key, V value) { throw uoe(); }
    @Override public V remove(Object key) { throw uoe(); }
    @Override public boolean remove(Object key, Object value) { throw uoe(); }
    @Override public V replace(K key, V value) { throw uoe(); }
    @Override public boolean replace(K key, V oldValue, V newValue) { throw uoe(); }
    @Override public void replaceAll(BiFunction<? super K,? super V,? extends V> f) { throw uoe(); }
}    

// 創建一個不可變的映射
static <K, V> Entry<K, V> entry(K k, V v) {
    // KeyValueHolder checks for nulls
    return new KeyValueHolder<>(k, v);
}   
    
/**
 * 返回包含給定映射項的不可修改映射。給定的映射不能為空，也不能包含任何空鍵或值。
 * 如果給定的映射隨後被修改，返回的映射將不會反映這種修改。
 */
static <K, V> Map<K, V> copyOf(Map<? extends K, ? extends V> map) {
    if (map instanceof ImmutableCollections.AbstractImmutableMap) {
        return (Map<K,V>)map;
    } else {
        return (Map<K,V>)Map.ofEntries(map.entrySet().toArray(new Entry[0]));
    }
}    
  

Map.Entity介面

Map.Entity介面定義了Map集合中的實際存儲節點.
Map的實現類, 諸如Hashmap, TreeMap等, 存儲節點都是實現了Map.Entity的靜態內部類.
上面提到的Map.entrySet迴圈方法, 得到的就是所有Map.Entry<K, V>的集合.

interface Entry<K, V> {
    /**
     * 返回節點存儲的key值
     */
    K getKey();

    /**
     * 返回節點存儲的value值
     */
    V getValue();

    /**
     * 將與此項對應的值替換為指定的值
     */
    V setValue(V value);
    
    /**
     * 比較指定的對象與此條目是否相等。
     * 如果給定的對象也是映射項，並且這兩個項表示相同的映射，則返回true。
     */
    boolean equals(Object o);

    /**
     * 返回此映射項的哈希碼值。
     */
    int hashCode();
    
    // 用於流處理的比較器
    // 之後寫流處理的時候再整理吧...
    public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K, V>> comparingByKey() {
            return (Comparator<Map.Entry<K, V>> & Serializable)
                (c1, c2) -> c1.getKey().compareTo(c2.getKey());
        }
     public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K, V>> comparingByValue() {
            return (Comparator<Map.Entry<K, V>> & Serializable)
                (c1, c2) -> c1.getValue().compareTo(c2.getValue());
        }

    public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
        Objects.requireNonNull(cmp);
        return (Comparator<Map.Entry<K, V>> & Serializable)
            (c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
    }

    public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
        Objects.requireNonNull(cmp);
        return (Comparator<Map.Entry<K, V>> & Serializable)
            (c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
    }
}

哈希洪水攻擊

概念

哈希洪水攻擊（Hash-Flooding Attack）是一種拒絕服務攻擊（Denial of Service），一旦後端介面存在合適的攻擊面，攻擊者就能輕鬆讓整台伺服器陷入癱瘓。

哈希表的時間複雜性

哈希表（Hash Table）的'平均運行時間'和'最差運行時間'會差很遠。
假設我們想要連續插入n個元素到哈希表中：

• 如果這些元素的鍵(Key)極少出現相同哈希值，這項任務就只需O(n)的時間。
• 如果這些鍵頻繁出現相同的哈希值（頻繁發生碰撞），這項任務就需要O(n^2)的時間。

衍生出的奇思妙想:

既然哈希表數據結構的最差運行時間這麼廢物，我們有沒有可能通過演算法上的漏洞，強行構造出一個最差情況，讓伺服器把全部的資源都浪費在處理這個最差情況上？

由哈希map的預設計算哈希值和Object類的計算哈希值策略可以看到, 如果不做自定義的話, 預設就是使用Java自帶的字元串哈希函數 :“DJBX33A演算法”的變種.

// hashmap計算哈希值的策略
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// Object類的計算哈希值策略
@HotSpotIntrinsicCandidate
public native int hashCode();

而根據這個演算法定義，就可以輕鬆地構造出一批具有一樣哈希值的字元串, 這樣只要構造出足夠多的哈希的字元串，把它們提交給伺服器做哈希表， 就能用很低的成本將伺服器打癱.

如何防禦

哈希洪水攻擊的根本在於黑客可以通過已知的哈希演算法算出哈希值相同的數.

所以我們可以使用帶密鑰哈希演算法（Keyed Hash Function）, 在演算法中加入一個秘密參數 - 哈希種子（Hash Seed）, 讓黑客無法掌握具體的哈希演算法,就可以進行有效的防禦了.

來自Google、UIC等機構的眾多研究人員設計了許多新的哈希函數：SipHash、MurmurHash、CityHash等等。這些演算法不停地被推翻，不停地更新版本，到現在已經形成了一套穩定的演算法標準，被眾多編程語言和開源項目所採納。

Java提出的解決方案:

從JDK 8開始，HashMap、LinkedHashMap和ConcurrentHashMap三個類引入了一套新的策略來處理哈希碰撞。

• 當一個位置存儲的元素個數小於8個時，仍然使用鏈表存儲。
• 當一個位置存儲的元素個數大於等於8個時，改為使用平衡樹來存儲。

這樣一來，就能保證最差的運行時間是O(n log n)了。

為什麼要設立“8個元素”（TREEIFY threshold）:

因為平衡樹相比鏈表而言有著更高的開銷，以及更散亂的記憶體佈局（影響緩存命中率）。在正常情況下，哈希表的一個位置大約只會存儲1~4個左右的元素，所以沒有必要專門開一個平衡樹來存儲衝突的元素，對一些性能敏感的應用來說會造成顯著的負面影響。

哈希洪水概念說明整理自知乎大佬的回覆:

什麼是哈希洪水攻擊（Hash-Flooding Attack）？ - Gh0u1L5的回答 - 知乎

代碼測試

測試了一下最極端的每次的哈希值都相同和正常插入哈希值做對比:

public static void main(String[] args) {
    Map<TestString, Integer> map = new HashMap();
    Long l = System.currentTimeMillis();
    System.out.println(l);
    for (int i = 0; i < 100000; i++ ) {
        map.put(new TestString("ddd" + i), i);
    }
    System.out.println(System.currentTimeMillis() - l);
    Long c = System.currentTimeMillis();
    map.get(new TestString("ddd"+5000));
    System.out.println("-------" + (System.currentTimeMillis() - c));

    Map<TestStringNom, Integer> mapNom = new HashMap();
    Long ll = System.currentTimeMillis();
    System.out.println(l);
    for (int i = 0; i < 100000; i++ ) {
        mapNom.put(new TestStringNom("ddd" + i) , i);
    }
    System.out.println(System.currentTimeMillis() - ll);
    Long cc = System.currentTimeMillis();
    mapNom.get(map.get(new TestStringNom("ddd5000")));
    System.out.println("-------" + (System.currentTimeMillis() - cc));
}

public class TestString {
    final String val;

    public TestString(String val) {
        this.val = val;
    }

    @Override
    public int hashCode() {
        super.hashCode();
        return 88590;
    }
}

public class TestStringNom {
    final String val;

    public TestStringNom(String val) {
        this.val = val;
    }

    @Override
    public int hashCode() {
        return super.hashCode();
    }
}