Map

---

Map是一種用于快速查找的數(shù)據(jù)結(jié)構(gòu)，它以鍵值對(duì)的形式存儲(chǔ)數(shù)據(jù)，每一個(gè)鍵都是唯一的，且對(duì)應(yīng)著一個(gè)值，如果想要查找Map中的數(shù)據(jù)，只需要傳入一個(gè)鍵，Map會(huì)對(duì)鍵進(jìn)行匹配并返回鍵所對(duì)應(yīng)的值，可以說Map其實(shí)就是一個(gè)存放鍵值對(duì)的集合。Map被各種編程語言廣泛使用，只不過在名稱上可能會(huì)有些混淆，像Python中叫做字典（Dictionary），也有些語言稱其為關(guān)聯(lián)數(shù)組（Associative Array），但其實(shí)它們都是一樣的，都是一個(gè)存放鍵值對(duì)的集合。至于Java中經(jīng)常用到的HashMap也是Map的一種，它被稱為散列表，關(guān)于散列表的細(xì)節(jié)我會(huì)在本文中解釋HashMap的源碼時(shí)提及。

Java還提供了一種與Map密切相關(guān)的數(shù)據(jù)結(jié)構(gòu)：Set，它是數(shù)學(xué)意義上的集合，特性如下：

• 無序性：一個(gè)集合中，每個(gè)元素的地位都是相同的，元素之間也都是無序的。不過Java中也提供了有序的Set，這點(diǎn)倒是沒有完全遵循。
• 互異性：一個(gè)集合中，任何兩個(gè)元素都是不相同的。
• 確定性：給定一個(gè)集合以及其任一元素，該元素屬于或者不屬于該集合是必須可以確定的。

很明顯，Map中的key就很符合這些特性，Set的實(shí)現(xiàn)其實(shí)就是在內(nèi)部使用Map。例如，HashSet就定義了一個(gè)類型為HashMap的成員變量，向HashSet添加元素a，等同于向它內(nèi)部的HashMap添加了一個(gè)key為a，value為一個(gè)Object對(duì)象的鍵值對(duì)，這個(gè)Object對(duì)象是HashSet的一個(gè)常量，它是一個(gè)虛擬值，沒有什么實(shí)際含義，源碼如下：

private transient HashMap<E,Object> 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的一個(gè)頂級(jí)接口，提供了三種集合視圖（Collection Views）：包含所有key的集合、包含所有value的集合以及包含所有鍵值對(duì)的集合，Map中的元素順序與它所返回的集合視圖中的元素的迭代順序相關(guān)，也就是說，Map本身是不保證有序性的，當(dāng)然也有例外，比如TreeMap就對(duì)有序性做出了保證，這主要因?yàn)樗�是基于紅黑樹實(shí)現(xiàn)的。

所謂的集合視圖就是由集合本身提供的一種訪問數(shù)據(jù)的方式，同時(shí)對(duì)視圖的任何修改也會(huì)影響到集合。好比Map.keySet()返回了它包含的key的集合，如果你調(diào)用了Map.remove(key)那么keySet.contains(key)也將返回false，再比如說Arrays.asList(T)可以把一個(gè)數(shù)組封裝成一個(gè)List，這樣你就可以通過List的API來訪問和操作這些數(shù)據(jù)，如下列示例代碼：

String[] strings = {"a", "b", "c"};
List<String> 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"

是不是感覺很神奇，其實(shí)Arrays.asList()只是將傳入的數(shù)組與Arrays中的一個(gè)內(nèi)部類ArrayList（注意，它與java.util包下的ArrayList不是同一個(gè)）做了一個(gè)”綁定“，在調(diào)用get()時(shí)會(huì)直接根據(jù)下標(biāo)返回?cái)?shù)組中的元素，而調(diào)用set()時(shí)也會(huì)直接修改數(shù)組中對(duì)應(yīng)下標(biāo)的元素。相對(duì)于直接復(fù)制來說，集合視圖的優(yōu)點(diǎn)是內(nèi)存利用率更高，假設(shè)你有一個(gè)數(shù)組，又很想使用List的API來操作它，那么你不用new一個(gè)ArrayList以拷貝數(shù)組中的元素，只需要一點(diǎn)額外的內(nèi)存（通過Arrays.ArrayList對(duì)數(shù)組進(jìn)行封裝），原始數(shù)據(jù)依然是在數(shù)組中的，并不會(huì)復(fù)制成多份。

Map接口規(guī)范了Map數(shù)據(jù)結(jié)構(gòu)的通用API（也含有幾個(gè)用于簡(jiǎn)化操作的default方法，default是JDK8的新特性，它是接口中聲明的方法的默認(rèn)實(shí)現(xiàn)，即非抽象方法）并且還在內(nèi)部定義了Entry接口（鍵值對(duì)的實(shí)體類），在JDK中提供的所有Map數(shù)據(jù)結(jié)構(gòu)都實(shí)現(xiàn)了Map接口，下面為Map接口的源碼（代碼中的注釋太長(zhǎng)了，基本都是些實(shí)現(xiàn)的規(guī)范，為了篇幅我就盡量省略了）。

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<K,V> {

	// 查詢操作
    /**
     * 返回這個(gè)Map中所包含的鍵值對(duì)的數(shù)量，如果大于Integer.MAX_VALUE，
     * 則應(yīng)該返回Integer.MAX_VALUE。
     */
    int size();
    /**
     * Map是否為空。
     */
    boolean isEmpty();
    /**
 	 * Map中是否包含key，如果是返回true，否則false。
     */
    boolean containsKey(Object key);
    /**
     * Map中是否包含value，如果是返回true，否則false。
     */
    boolean containsValue(Object value);
    /**
     * 根據(jù)key查找value，如果Map不包含該key，則返回null。
     */
    V get(Object key);
    // 修改操作
    /**
     * 添加一對(duì)鍵值對(duì)，如果Map中已含有這個(gè)key，那么新value將覆蓋掉舊value，
     * 并返回舊value，如果Map中之前沒有這個(gè)key，那么返回null。
     */
    V put(K key, V value);
    /**
     * 刪除指定key并返回之前的value，如果Map中沒有該key，則返回null。
     */
    V remove(Object key);
    // 批量操作
    /**
     * 將指定Map中的所有鍵值對(duì)批量添加到當(dāng)前Map。
     */
    void putAll(Map<? extends K, ? extends V> m);
    /**
     * 刪除Map中所有的鍵值對(duì)。
     */
    void clear();
    // 集合視圖
    /**
     * 返回包含Map中所有key的Set，對(duì)該視圖的所有修改操作會(huì)對(duì)Map產(chǎn)生同樣的影響，反之亦然。
     */
    Set<K> keySet();
    /**
     * 返回包含Map中所有value的集合，對(duì)該視圖的所有修改操作會(huì)對(duì)Map產(chǎn)生同樣的影響，反之亦然。
     */
    Collection<V> values();
    /**
     * 返回包含Map中所有鍵值對(duì)的Set，對(duì)該視圖的所有修改操作會(huì)對(duì)Map產(chǎn)生同樣的影響，反之亦然。
     */
    Set<Map.Entry<K, V>> entrySet();
    /**
     * Entry代表一對(duì)鍵值對(duì)，規(guī)范了一些基本函數(shù)以及幾個(gè)已實(shí)現(xiàn)的類函數(shù)（各種比較器）。
     */
    interface Entry<K,V> {

        K getKey();
        V getValue();
        V setValue(V value);
        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());
        }
    }
    // 比較和hashing
    /**
     * 將指定的對(duì)象與此Map進(jìn)行比較是否相等。
     */
    boolean equals(Object o);
    /**
     * 返回此Map的hash code。
     */
    int hashCode();
    // 默認(rèn)方法（非抽象方法）
    /**
     * 根據(jù)key查找value，如果該key不存在或等于null則返回defaultValue。
     */
    default V getOrDefault(Object key, V defaultValue) {
        V v;
        return (((v = get(key)) != null) || containsKey(key)) ? v : defaultValue;
    }
    /**
     * 遍歷Map并對(duì)每個(gè)鍵值對(duì)執(zhí)行指定的操作（action）。
     * BiConsumer是一個(gè)函數(shù)接口（具有一個(gè)抽象方法的接口，用于支持Lambda），
     * 它代表了一個(gè)接受兩個(gè)輸入?yún)��?shù)的操作，且不返回任何結(jié)果。
     * 至于它奇怪的名字，根據(jù)Java中的其他函數(shù)接口的命名規(guī)范，Bi應(yīng)該是Binary的縮寫，意思是二元的。
     */
    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);
        }
    }
    /** 
     * 遍歷Map，然后調(diào)用傳入的函數(shù)function生成新value對(duì)舊value進(jìn)行替換。
     * BiFunction同樣是一個(gè)函數(shù)接口，它接受兩個(gè)輸入?yún)��?shù)并且返回一個(gè)結(jié)果。
     */
    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);
            }
        }
    }
    /**
     * 如果指定的key不存在或者關(guān)聯(lián)的value為null，則添加鍵值對(duì)。
     */
    default V putIfAbsent(K key, V value) {
        V v = get(key);
        if (v == null) {
            v = put(key, value);
        }
        return v;
    }
    /**
     * 當(dāng)指定key關(guān)聯(lián)的value與傳入的參數(shù)value相等時(shí)刪除該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;
    }
    /**
     * 當(dāng)指定key關(guān)聯(lián)的value與oldValue相等時(shí)，使用newValue進(jìn)行替換。
     */
    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;
    }
    /**
     * 當(dāng)指定key關(guān)聯(lián)到某個(gè)value時(shí)進(jìn)行替換。
     */
    default V replace(K key, V value) {
        V curValue;
        if (((curValue = get(key)) != null) || containsKey(key)) {
            curValue = put(key, value);
        }
        return curValue;
    }
    /**
     * 當(dāng)指定key沒有關(guān)聯(lián)到一個(gè)value或者value為null時(shí)，調(diào)用mappingFunction生成值并添加鍵值對(duì)到Map。
     * Function是一個(gè)函數(shù)接口，它接受一個(gè)輸入?yún)��?shù)并返回一個(gè)結(jié)果，如果mappingFunction返回的結(jié)果
     * 也為null，那么將不會(huì)調(diào)用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;
    }
    /**
     * 當(dāng)指定key關(guān)聯(lián)到一個(gè)value并且不為null時(shí)，調(diào)用remappingFunction生成newValue，
     * 如果newValue不為null，那么進(jìn)行替換，否則刪除該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根據(jù)key與其相關(guān)聯(lián)的value生成newValue，
     * 當(dāng)newValue等于null時(shí)刪除該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;
        }
    }
    /**
     * 當(dāng)指定key沒有關(guān)聯(lián)到一個(gè)value或者value為null，將它與傳入的參數(shù)value
     * 進(jìn)行關(guān)聯(lián)。否則，調(diào)用remappingFunction生成newValue并進(jìn)行替換。
     * 如果，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;
    }
}

需要注意一點(diǎn)，這些default方法都是非線程安全的，任何保證線程安全的擴(kuò)展類都必須重寫這些方法，例如ConcurrentHashMap。

下圖為Map的繼承關(guān)系結(jié)構(gòu)圖，它也是本文接下來將要分析的Map實(shí)現(xiàn)類的大綱，這些實(shí)現(xiàn)類都是比較常用的，在JDK中Map的實(shí)現(xiàn)類有幾十個(gè)，大部分都是我們用不到的，限于篇幅原因就不一一講解了（本文包含許多源碼與對(duì)實(shí)現(xiàn)細(xì)節(jié)的分析，建議讀者抽出一段連續(xù)的空閑時(shí)間靜下心來慢慢閱讀）。

標(biāo)簽： 安全 代碼

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。