Map

Map是一种用于快速查找的数据布局，它以键值对的形式存储数据，每一个键都是独一的，且对应着一个值，假如想要查找Map中的数据，只需要传入一个键，Map会对键举办匹配并返回键所对应的值，可以说Map其实就是一个存放键值对的荟萃。Map被各类编程语言遍及利用，只不外在名称上大概会有些夹杂，像Python中叫做字典（Dictionary），也有些语言称其为关联数组（Associative Array），但其实它们都是一样的，都是一个存放键值对的荟萃。至于Java中常常用到的HashMap也是Map的一种，它被称为散列表，关于散列表的细节我会在本文中表明HashMap的源码时提及。

Java还提供了一种与Map密切相关的数据布局：Set，它是数学意义上的荟萃，特性如下：

很明明，Map中的key就很切合这些特性，Set的实现其实就是在内部利用Map。譬喻，HashSet就界说了一个范例为HashMap的成员变量，向HashSet添加元素a，等同于向它内部的HashMap添加了一个key为a，value为一个Object工具的键值对，这个Object工具是HashSet的一个常量，它是一个虚拟值，没有什么实际寄义，源码如下：

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的一个顶级接口，提供了三种荟萃视图（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<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"

是不是感受很神奇，其实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<K,V> {

	// 查询操纵
    /**
     * 返回这个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<K> keySet();
    /**
     * 返回包括Map中所有value的荟萃，昆山软件开发，对该视图的所有修改操纵会对Map发生同样的影响，反之亦然。
     */
    Collection<V> values();
    /**
     * 返回包括Map中所有键值对的Set，对该视图的所有修改操纵会对Map发生同样的影响，昆山软件开发，反之亦然。
     */
    Set<Map.Entry<K, V>> entrySet();
    /**
     * Entry代表一对键值对，类型了一些根基函数以及几个已实现的类函数（各类较量器）。
     */
    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
    /**
     * 将指定的工具与此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<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，然后挪用传入的函数function生成新value对旧value举办替换。
     * BiFunction同样是一个函数接口，它接管两个输入参数而且返回一个功效。
     */
    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不存在可能关联的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。