歡迎光臨
每天分享高質量文章

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技能

贊(0)

分享創造快樂