Map 大家族的那點事兒 ( 1 ) ：Map

（點選上方公眾號，可快速關註）

來源：SylvanasSun’s Blog ，

sylvanassun.github.io/2018/03/16/2018-03-16-map_family/

Map

Map是一種用於快速查詢的資料結構，它以鍵值對的形式儲存資料，每一個鍵都是唯一的，且對應著一個值，如果想要查詢Map中的資料，只需要傳入一個鍵，Map會對鍵進行匹配並傳回鍵所對應的值，可以說Map其實就是一個存放鍵值對的集合。Map被各種程式語言廣泛使用，只不過在名稱上可能會有些混淆，像Python中叫做字典（Dictionary），也有些語言稱其為關聯陣列（Associative Array），但其實它們都是一樣的，都是一個存放鍵值對的集合。至於Java中經常用到的HashMap也是Map的一種，它被稱為散串列，關於散串列的細節我會在本文中解釋HashMap的原始碼時提及。

Java還提供了一種與Map密切相關的資料結構：Set，它是數學意義上的集合，特性如下：

• 無序性：一個集合中，每個元素的地位都是相同的，元素之間也都是無序的。不過Java中也提供了有序的Set，這點倒是沒有完全遵循。

• 互異性：一個集合中，任何兩個元素都是不相同的。

• 確定性：給定一個集合以及其任一元素，該元素屬於或者不屬於該集合是必須可以確定的。

很明顯，Map中的key就很符合這些特性，Set的實現其實就是在內部使用Map。例如，HashSet就定義了一個型別為HashMap的成員變數，向HashSet新增元素a，等同於向它內部的HashMap添加了一個key為a，value為一個Object物件的鍵值對，這個Object物件是HashSet的一個常量，它是一個虛擬值，沒有什麼實際含義，原始碼如下：

private transient HashMap map;

// Dummy value to associate with an Object in the backing Map

private static final Object PRESENT = new Object();

public boolean add(E e) {

    return map.put(e, PRESENT)==null;

}

小插曲過後，讓我們接著說Map，它是JDK的一個頂級介面，提供了三種集合檢視（Collection Views）：包含所有key的集合、包含所有value的集合以及包含所有鍵值對的集合，Map中的元素順序與它所傳回的集合檢視中的元素的迭代順序相關，也就是說，Map本身是不保證有序性的，當然也有例外，比如TreeMap就對有序性做出了保證，這主要因為它是基於紅黑樹實現的。

所謂的集合檢視就是由集合本身提供的一種訪問資料的方式，同時對檢視的任何修改也會影響到集合。好比Map.keySet()傳回了它包含的key的集合，如果你呼叫了Map.remove(key)那麼keySet.contains(key)也將傳回false，再比如說Arrays.asList(T)可以把一個陣列封裝成一個List，這樣你就可以透過List的API來訪問和操作這些資料，如下列示例程式碼：

String[] strings = {“a”, “b”, “c”};

List list = Arrays.asList(strings);

System.out.println(list.get(0)); // “a”

strings[0] = “d”;

System.out.println(list.get(0)); // “d”

list.set(0, “e”);

System.out.println(strings[0]); // “e”

是不是感覺很神奇，其實Arrays.asList()只是將傳入的陣列與Arrays中的一個內部類ArrayList（註意，它與java.util包下的ArrayList不是同一個）做了一個”系結“，在呼叫get()時會直接根據下標傳回陣列中的元素，而呼叫set()時也會直接修改陣列中對應下標的元素。相對於直接複製來說，集合檢視的優點是記憶體利用率更高，假設你有一個陣列，又很想使用List的API來操作它，那麼你不用new一個ArrayList以複製陣列中的元素，只需要一點額外的記憶體（透過Arrays.ArrayList對陣列進行封裝），原始資料依然是在陣列中的，並不會複製成多份。

Map介面規範了Map資料結構的通用API（也含有幾個用於簡化操作的default方法，default是JDK8的新特性，它是介面中宣告的方法的預設實現，即非抽象方法）並且還在內部定義了Entry介面（鍵值對的物體類），在JDK中提供的所有Map資料結構都實現了Map介面，下麵為Map介面的原始碼（程式碼中的註釋太長了，基本都是些實現的規範，為了篇幅我就儘量省略了）。

package java.util;

import java.util.function.BiConsumer;

import java.util.function.BiFunction;

import java.util.function.Function;

import java.io.Serializable;

public interface Map {

 

    // 查詢操作

    /**

     * 傳回這個Map中所包含的鍵值對的數量，如果大於Integer.MAX_VALUE，

     * 則應該傳回Integer.MAX_VALUE。

     */

    int size();

    /**

     * Map是否為空。

     */

    boolean isEmpty();

    /**

     * Map中是否包含key，如果是傳回true，否則false。

     */

    boolean containsKey(Object key);

    /**

     * Map中是否包含value，如果是傳回true，否則false。

     */

    boolean containsValue(Object value);

    /**

     * 根據key查詢value，如果Map不包含該key，則傳回null。

     */

    V get(Object key);

    // 修改操作

    /**

     * 新增一對鍵值對，如果Map中已含有這個key，那麼新value將改寫掉舊value，

     * 並傳回舊value，如果Map中之前沒有這個key，那麼傳回null。

     */

    V put(K key, V value);

    /**

     * 刪除指定key並傳回之前的value，如果Map中沒有該key，則傳回null。

     */

    V remove(Object key);

    // 批次操作

    /**

     * 將指定Map中的所有鍵值對批次新增到當前Map。

     */

    void putAll(Map extends K, ? extends V> m);

    /**

     * 刪除Map中所有的鍵值對。

     */

    void clear();

    // 集合檢視

    /**

     * 傳回包含Map中所有key的Set，對該檢視的所有修改操作會對Map產生同樣的影響，反之亦然。

     */

    Set keySet();

    /**

     * 傳回包含Map中所有value的集合，對該檢視的所有修改操作會對Map產生同樣的影響，反之亦然。

     */

    Collection values();

    /**

     * 傳回包含Map中所有鍵值對的Set，對該檢視的所有修改操作會對Map產生同樣的影響，反之亦然。

     */

    Set> entrySet();

    /**

     * Entry代表一對鍵值對，規範了一些基本函式以及幾個已實現的類函式（各種比較器）。

     */

    interface Entry {

 

        K getKey();

        V getValue();

        V setValue(V value);

        boolean equals(Object o);

        int hashCode();

        public static , V> Comparator> comparingByKey() {

            return (Comparator> & Serializable)

                (c1, c2) -> c1.getKey().compareTo(c2.getKey());

        }

        public static > Comparator> comparingByValue() {

            return (Comparator> & Serializable)

                (c1, c2) -> c1.getValue().compareTo(c2.getValue());

        }

        public static Comparator> comparingByKey(Comparator super K> cmp) {

            Objects.requireNonNull(cmp);

            return (Comparator> & Serializable)

                (c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());

        }

        public static Comparator> comparingByValue(Comparator super V> cmp) {

            Objects.requireNonNull(cmp);

            return (Comparator> & Serializable)

                (c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());

        }

    }

    // 比較和hashing

    /**

     * 將指定的物件與此Map進行比較是否相等。

     */

    boolean equals(Object o);

    /**

     * 傳回此Map的hash code。

     */

    int hashCode();

    // 預設方法（非抽象方法）

    /**

     * 根據key查詢value，如果該key不存在或等於null則傳回defaultValue。

     */

    default V getOrDefault(Object key, V defaultValue) {

        V v;

        return (((v = get(key)) != null) || containsKey(key)) ? v : defaultValue;

    }

    /**

     * 遍歷Map並對每個鍵值對執行指定的操作（action）。

     * BiConsumer是一個函式介面（具有一個抽象方法的介面，用於支援Lambda），

     * 它代表了一個接受兩個輸入引數的操作，且不傳回任何結果。

     * 至於它奇怪的名字，根據Java中的其他函式介面的命名規範，Bi應該是Binary的縮寫，意思是二元的。

     */

    default void forEach(BiConsumer super K, ? super V> action) {

        Objects.requireNonNull(action);

        for (Map.Entry 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);

        }

    }

    /** 

     * 遍歷Map，然後呼叫傳入的函式function生成新value對舊value進行替換。

     * BiFunction同樣是一個函式介面，它接受兩個輸入引數並且傳回一個結果。

     */

    default void replaceAll(BiFunction super K, ? super V, ? extends V> function) {

        Objects.requireNonNull(function);

        for (Map.Entry 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);

            }

        }

    }

    /**

     * 如果指定的key不存在或者關聯的value為null，則新增鍵值對。

     */

    default V putIfAbsent(K key, V value) {

        V v = get(key);

        if (v == null) {

            v = put(key, value);

        }

        return v;

    }

    /**

     * 當指定key關聯的value與傳入的引數value相等時刪除該key。

     */

    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相等時，使用newValue進行替換。

     */

    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;

    }

    /**

     * 當指定key沒有關聯到一個value或者value為null時，呼叫mappingFunction生成值並新增鍵值對到Map。

     * Function是一個函式介面，它接受一個輸入引數並傳回一個結果，如果mappingFunction傳回的結果

     * 也為null，那麼將不會呼叫put。

     */

    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;

    }

    /**

     * 當指定key關聯到一個value並且不為null時，呼叫remappingFunction生成newValue，

     * 如果newValue不為null，那麼進行替換，否則刪除該key。

     */

    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;

        }

    }

    /**

     * remappingFunction根據key與其相關聯的value生成newValue，

     * 當newValue等於null時刪除該key，否則新增或者替換舊的對映。

     */

    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;

        }

    }

    /**

     * 當指定key沒有關聯到一個value或者value為null，將它與傳入的引數value

     * 進行關聯。否則，呼叫remappingFunction生成newValue併進行替換。

     * 如果，newValue等於null，那麼刪除該key。

     */

    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;

    }

}

需要註意一點，這些default方法都是非執行緒安全的，任何保證執行緒安全的擴充套件類都必須重寫這些方法，例如ConcurrentHashMap。

下圖為Map的繼承關係結構圖，它也是本文接下來將要分析的Map實現類的大綱，這些實現類都是比較常用的，在JDK中Map的實現類有幾十個，大部分都是我們用不到的，限於篇幅原因就不一一講解了（本文包含許多原始碼與對實現細節的分析，建議讀者抽出一段連續的空閑時間靜下心來慢慢閱讀）。

【關於投稿】

如果大家有原創好文投稿，請直接給公號傳送留言。

① 留言格式：
【投稿】+《 文章標題》+ 文章連結

② 示例：
【投稿】《不要自稱是程式員，我十多年的 IT 職場總結》：http://blog.jobbole.com/94148/

③ 最後請附上您的個人簡介哈~

看完本文有收穫？請轉發分享給更多人

關註「ImportNew」，提升Java技能