之前所介绍的List、Set、Queue系列集合都是由Collection派生出来的，今天我们来分析java集合的另一个分支——Map集合。

Map系列集合中的继承实现关系

建议大家先看完本文再回过头来思考这张图。

Map集合简介

Map与之前所介绍的List、Set、Queue等不同，它是java集合的另一个分支。

Map是一种键值对集合（<key,value>），Map中的每一个对象都包含一个键(key)对象和一个值(value)对象。Map集合中不能包含重复的key，每个key可以映射到最多一个value，value值可以重复。

Map接口源码分析

Map是java提供的一个位于java.util包中的一个接口，它提供了一些操作Map集合的一些基本方法。

接口方法

//返回此集合中键值映射的数量。
	int size();
	//如果此集合不包含键值映射，则返回 true 。 
    boolean isEmpty();

    //如果此映射包含指定键的映射，则返回true 。
    boolean containsKey(Object key);

    //如果此映射将一个或多个键映射到指定的值，则返回true 。
    boolean containsValue(Object value);

    //返回到指定键所映射的值
    V get(Object key);

    // 将指定的值与该映射中的指定键相关联，并以键值对加入此集合
    V put(K key, V value);

    //如果存在，从该集合中删除一个键的映射。
    V remove(Object key);

    // 将指定集合的所有映射复制到此集合
    void putAll(Map<? extends K, ? extends V> m);

    /从该集合中删除所有的映射
    void clear();

    // 返回此集合中包含的键的Set视图。
    Set<K> keySet();

    //返回此集合中包含的值的Collection视图。
    Collection<V> values();

    //返回此地图中包含的键值对映射的Set视图。 
    Set<Map.Entry<K, V>> entrySet();

    

    // 将指定的对象与此映射进行比较以获得相等性。 如果给定的对象也是一个map，并且两个map代表相同的映射，则返回true 。 
    boolean equals(Object o);

    /返回此集合的哈希码值。 map的哈希码被定义为map entrySet()视图中每个条目的哈希代码的总和。 
    int hashCode();

默认实现的方法

// 返回到指定键所映射的值，如果此映射不包含该键的映射，返回defaultValue。 
    default V getOrDefault(Object key, V defaultValue) {
        V v;
        return (((v = get(key)) != null) || containsKey(key))
            ? v
            : defaultValue;
    }

    //对此映射中的每个条目执行给定的操作，直到所有条目都被处理或操作引发异常。 
    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);
        }
    }

    //将每个条目的值替换为对该条目调用给定函数的结果，直到所有条目都被处理或该函数抛出异常。
    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;
    }

    //仅当当前映射到指定的值时，才能替换指定键的条目。
    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;
    }

    //只有当目标映射到某个值时，才能替换指定键的条目。
    default V replace(K key, V value) {
        V curValue;
        if (((curValue = get(key)) != null) || containsKey(key)) {
            curValue = put(key, value);
        }
        return curValue;
    }

    //如果指定的键尚未与值相关联（或映射到null ），则尝试使用给定的映射函数计算其值，并将其输入到此映射中
    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;
        }
    }

    //计算指定键及其当前映射值的映射（如果没有当前映射，则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;
        }
    }

    //如果指定的键尚未与值相关联或与null相关联，则将其与给定的非空值相关联。 否则，将关联值替换为给定重映射函数的结果，如果结果为null 。
    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;
    }

Map.Entry

Map.Entry是Map声明的一个内部接口，此接口为泛型，定义为Entry<K,V>。它表示Map中的一个实体（一个key-value键值对）。

Entry的引入是为了更方便的输出map键值对。一般情况下，要输出Map中的key 和 value 是先得到key的集合keySet()，然后再迭代（循环）由每个key得到每个value。而Entry可以一次性获得key和value。

Entry内部也提供了一些操作key-value的方法：

interface Entry<K,V> {
        //返回与此Entry相对应的键。
        K getKey();
        
        //返回与此Entry相对应的值。
        V getValue();

        //用指定的值替换与该Entry相对应的值
        V setValue(V value);

        //将指定的对象与此Entry进行比较以获得相等性。
        boolean equals(Object o);

        //返回此映射Entry的哈希码值。
        int hashCode();

        //返回一个比较器 ，按键自然顺序比较Map.Entry 。
        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());
        }

        //返回一个比较值，比较Map.Entry的自然顺序值。
        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());
        }

        //返回一个比较器，比较Map.Entry按键使用给定的Comparator 。
        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());
        }

        //返回一个比较器 ，使用给定的Comparator比较Map.Entry的值。
        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());
        }
    }

HashMap、TreeMap与HashTable

HashMap、TreeMap与HashTable是Map接口的三个常用的实现类。下面依次结合源码对其进行分析。

HashMap

从源码分析哈希表HashMap

HashMap就是我们常说的哈希表。
哈希表的表示：https://blog.csdn.net/weixin_43598687/article/details/119713753

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

HashMap继承至AbstractMap，并且实现了Map, Cloneable, Serializable接口，支持可复制以及序列化操作。

HashMap的底层采用的是数组 + 链表 + 红黑树实现的。使用链地址法来处理冲突，也就是数组加链表的结合，在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。

哈希表的初始容量为16，最大容量为1,073,741,824（1<<30，230），负载因子为0.75，HashMap的容量必须为2n，如果相同哈希值，链表的长度超过8，就从链表转换成红黑树。

/** * The default initial capacity - MUST be a power of two. */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /** * The load factor used when none specified in constructor. */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

构造方法
HashMap也是我们最常用的一种Map结构，在HashMap中提供了多种构造方法，如下：

HashMap(int initialCapacity, float loadFactor)
构造一个空的 HashMap具有指定的初始容量和负载因子。

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

HashMap(int initialCapacity)
构造一个空的 HashMap ，具有指定的初始容量和默认负载系数（0.75）。

public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

HashMap()
构造一个空的 HashMap ，具有默认初始容量和默认负载系数（0.75）。

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

HashMap(Map<? extends K, ? extends V> m)
构造一个新的HashMap与指定的相同的映射Map 。该HashMap与默认负载因数（0.75）和初始容量足以容纳映射在指定Map创建。

public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

HashMap.Node
前面提到Map集合的主干是一个Entry数组，Entry是Map的一个基本单元，每一个Entry包含一个key-value键值对。

Node是HashMap中的一个静态内部类，它实现了Map.Entry接口，一个Node就相当于一个Entry。
Node在HashMap中的定义如下：

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

常用方法

int size()
返回此哈希表中键值映射的数量。

public int size() {
        return size;
    }

boolean isEmpty()
如果此哈希表不包含键值映射，则返回 true 。

public boolean isEmpty() {
        return size == 0;
    }

V get(Object key)
返回到指定键所映射的值。

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

boolean containsKey(Object key)
如果此映射包含指定键的映射，则返回 true 。

public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }

V put(K key, V value)
将指定的值与此映射中的指定键相关联。

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

void putAll(Map<? extends K, ? extends V> m)
将指定map的所有映射复制到此map。

public void putAll(Map<? extends K, ? extends V> m) {
        putMapEntries(m, true);
    }
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            if (table == null) { // pre-size
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            else if (s > threshold)
                resize();
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

V remove(Object key)
从该map中删除指定键的映射（如果存在）。

public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

void clear()
从该map中删除所有的映射。

public void clear() {
        Node<K,V>[] tab;
        modCount++;
        if ((tab = table) != null && size > 0) {
            size = 0;
            for (int i = 0; i < tab.length; ++i)
                tab[i] = null;
        }
    }

boolean containsValue(Object value)
如果此map将一个或多个键映射到指定的值，则返回 true 。

public boolean containsValue(Object value) {
        Node<K,V>[] tab; V v;
        if ((tab = table) != null && size > 0) {
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    if ((v = e.value) == value ||
                        (value != null && value.equals(v)))
                        return true;
                }
            }
        }
        return false;
    }

Set keySet()
返回此map中包含的键的Set视图。

public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new KeySet();
            keySet = ks;
        }
        return ks;
    }

Collection values()
返回此map中包含的值的Collection视图。

public Collection<V> values() {
        Collection<V> vs = values;
        if (vs == null) {
            vs = new Values();
            values = vs;
        }
        return vs;
    }

Set<Map.Entry<K,V>> entrySet()
返回此map中包含的映射的Set视图。

public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
    }

V getOrDefault(Object key, V defaultValue)
返回到指定键所映射的值，如果此映射不包含该键的映射，返回defaultValue。

public V getOrDefault(Object key, V defaultValue) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
    }

V putIfAbsent(K key, V value)
如果指定的键尚未与值相关联（或映射到 null ）将其与给定值相关联并返回 null ，否则返回当前值。

public V putIfAbsent(K key, V value) {
        return putVal(hash(key), key, value, true, true);
    }

boolean remove(Object key, Object value)
仅当指定的键当前映射到指定的值时删除该条目。

public boolean remove(Object key, Object value) {
        return removeNode(hash(key), key, value, true, true) != null;
    }

boolean replace(K key, V oldValue, V newValue)
仅当当前映射到指定的值时，才能替换指定键的条目。

public boolean replace(K key, V oldValue, V newValue) {
        Node<K,V> e; V v;
        if ((e = getNode(hash(key), key)) != null &&
            ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
            e.value = newValue;
            afterNodeAccess(e);
            return true;
        }
        return false;
    }

V replace(K key, V value)
只有当目标映射到某个值时，才能替换指定键的条目。

public V replace(K key, V value) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) != null) {
            V oldValue = e.value;
            e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
        return null;
    }

Object clone()
返回此 HashMap实例的浅拷贝：键和值本身不被克隆。

public Object clone() {
        HashMap<K,V> result;
        try {
            result = (HashMap<K,V>)super.clone();
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
        result.reinitialize();
        result.putMapEntries(this, false);
        return result;
    }

LinkedHashMap

LinkedHashMap是一个使用双向链表维护的HashMap，它是一个将所有Entry节点链入一个双向链表的HashMap。

LinkedHashMap是HashMap的一个子类，并实现了Map接口。

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

accessOrder属性
当accessOrder设置为false时，会按照插入顺序进行排序，当accessOrder为true时，会按照访问顺序（也就是插入和访问都会将当前节点放置到尾部，尾部代表的是最近访问的数据）排序。

构造方法

LinkedHashMap()
构造具有默认初始容量（16）和负载因子（0.75）的空 LinkedHashMap实例。

public LinkedHashMap() {
        super();
        accessOrder = false;
    }

LinkedHashMap(int initialCapacity)
构造具有指定初始容量和默认负载因子（0.75）的空 LinkedHashMap实例。

public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

LinkedHashMap(int initialCapacity, float loadFactor)
构造具有指定初始容量和负载因子的空 LinkedHashMap实例。

public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

LinkedHashMap(int initialCapacity, float loadFactor,boolean accessOrder)
构造一个空的 LinkedHashMap实例，具有指定的初始容量，负载因子和排序方式。

public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

LinkedHashMap(Map<? extends K, ? extends V> m)
构造具有与指定map相同映射的插入序列 LinkedHashMap实例。

public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }

TreeMap

从源码分析TreeMap

TreeMap是基于红黑树实现的一种map集合。
红黑树参考链接：https://blog.csdn.net/weixin_43598687/article/details/121732144

红黑树是天生支持排序的一种数据结构，TreeMap中默认情况下通过Key值的自然顺序进行排序。

public static void main(String[] args) {
        Map<Integer,String> treeMap = new TreeMap<>();

        treeMap.put(3,"three");
        treeMap.put(5,"five");
        treeMap.put(1,"one");
        treeMap.put(2,"two");
        treeMap.put(4,"four");

        System.out.println(treeMap);
    }

可以看到控制台中按TreeMap中key的自然顺序，打印出所有的键值对映射。

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

TreeMap继承至AbstractMap，并且实现了NavigableMap接口, Cloneable, java.io.Serializable，支持可复制以及序列化操作。
由于实现了NavigableMap接口，它也具有了为给定搜索目标报告最接近匹配项的导航方法。
NavigableMap解析：从源码分析SortedMap与NavigableMap

构造方法
在TreeMap中提供了多种构造方法，如下：

TreeMap()
使用其键的自然排序构造一个新的空TreeMap。

public TreeMap() {
        comparator = null;
    }

TreeMap(Comparator<? super K> comparator)
使用指定的比较器对其键排序，构造一个新的空TreeMap。

public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

TreeMap(Map<? extends K, ? extends V> m)
构造一个新的TreeMap，其中包含与给定map相同的映射，根据其键的自然顺序进行排序。

public TreeMap(Map<? extends K, ? extends V> m) {
        comparator = null;
        putAll(m);
    }

TreeMap(SortedMap<K, ? extends V> m)
构造一个包含相同映射并使用与指定排序映射相同顺序的新树映射。

public TreeMap(SortedMap<K, ? extends V> m) {
        comparator = m.comparator();
        try {
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
    }

常用方法

int size()
返回此TreeMap中键值映射的数量。

public int size() {
        return size;
    }

V get(Object key)
返回到指定键所映射的值。

public V get(Object key) {
        Entry<K,V> p = getEntry(key);
        return (p==null ? null : p.value);
    }

boolean containsKey(Object key)
如果此映射包含指定键的映射，则返回 true 。

public boolean containsKey(Object key) {
        return getEntry(key) != null;
    }
    final Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }

V put(K key, V value)
将指定的值与此映射中的指定键相关联。

public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

void putAll(Map<? extends K, ? extends V> map)
将指定map的所有映射复制到此map。

public void putAll(Map<? extends K, ? extends V> map) {
        int mapSize = map.size();
        if (size==0 && mapSize!=0 && map instanceof SortedMap) {
            Comparator<?> c = ((SortedMap<?,?>)map).comparator();
            if (c == comparator || (c != null && c.equals(comparator))) {
                ++modCount;
                try {
                    buildFromSorted(mapSize, map.entrySet().iterator(),
                                    null, null);
                } catch (java.io.IOException cannotHappen) {
                } catch (ClassNotFoundException cannotHappen) {
                }
                return;
            }
        }
        super.putAll(map);
    }

V remove(Object key)
从该map中删除指定键的映射（如果存在）。

public V remove(Object key) {
        Entry<K,V> p = getEntry(key);
        if (p == null)
            return null;

        V oldValue = p.value;
        deleteEntry(p);
        return oldValue;
    }

void clear()
从该map中删除所有的映射。

public void clear() {
        modCount++;
        size = 0;
        root = null;
    }

boolean containsValue(Object value)
如果此map将一个或多个键映射到指定的值，则返回 true 。

public boolean containsValue(Object value) {
        for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
            if (valEquals(value, e.value))
                return true;
        return false;
    }

Comparator<? super K> comparator()
返回用于比较此TreeMap的键的比较器。

public Comparator<? super K> comparator() {
        return comparator;
    }

K firstKey()
返回此TreeMap中当前的第一个（最低）键。

public K firstKey() {
        return key(getFirstEntry());
    }

K lastKey()
返回此TreeMap中当前的最后一个（最高）键。

public K lastKey() {
        return key(getLastEntry());
    }

Map.Entry<K,V> firstEntry()
返回与该TreeMap中的最小键相关联的键值映射，如果TreeMap为空，则返回 null 。

public Map.Entry<K,V> firstEntry() {
        return exportEntry(getFirstEntry());
    }

Map.Entry<K,V> lastEntry()
返回与该TreeMap中的最大键相关联的键值映射，如果TreeMap为空，则返回 null 。

public Map.Entry<K,V> lastEntry() {
        return exportEntry(getLastEntry());
    }

Map.Entry<K,V> pollFirstEntry()
删除并返回与该TreeMap中的最小键相关联的键值映射，如果TreeMap为空，则返回 null 。

public Map.Entry<K,V> pollFirstEntry() {
        Entry<K,V> p = getFirstEntry();
        Map.Entry<K,V> result = exportEntry(p);
        if (p != null)
            deleteEntry(p);
        return result;
    }

Map.Entry<K,V> pollLastEntry()
删除并返回与该TreeMap中的最大键相关联的键值映射，如果TreeMap为空，则返回 null 。

public Map.Entry<K,V> pollLastEntry() {
        Entry<K,V> p = getLastEntry();
        Map.Entry<K,V> result = exportEntry(p);
        if (p != null)
            deleteEntry(p);
        return result;
    }

Set keySet()
返回此map中包含的键的Set视图。

public Set<K> keySet() {
        return navigableKeySet();
    }
    public NavigableSet<K> navigableKeySet() {
        KeySet<K> nks = navigableKeySet;
        return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
    }

Collection values()
返回此map中包含的值的Collection视图。

public Collection<V> values() {
        Collection<V> vs = values;
        if (vs == null) {
            vs = new Values();
            values = vs;
        }
        return vs;
    }

Set<Map.Entry<K,V>> entrySet()
返回此map中包含的映射的Set视图。

public Set<Map.Entry<K,V>> entrySet() {
        EntrySet es = entrySet;
        return (es != null) ? es : (entrySet = new EntrySet());
    }

boolean replace(K key, V oldValue, V newValue)
仅当当前映射到指定的值时，才能替换指定键的条目。

public boolean replace(K key, V oldValue, V newValue) {
        Entry<K,V> p = getEntry(key);
        if (p!=null && Objects.equals(oldValue, p.value)) {
            p.value = newValue;
            return true;
        }
        return false;
    }

V replace(K key, V value)
只有当目标映射到某个值时，才能替换指定键的条目。

public V replace(K key, V value) {
        Entry<K,V> p = getEntry(key);
        if (p!=null) {
            V oldValue = p.value;
            p.value = value;
            return oldValue;
        }
        return null;
    }

Object clone()
返回此 TreeMap实例的浅拷贝：键和值本身不被克隆。

public Object clone() {
        TreeMap<?,?> clone;
        try {
            clone = (TreeMap<?,?>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }

        // Put clone into "virgin" state (except for comparator)
        clone.root = null;
        clone.size = 0;
        clone.modCount = 0;
        clone.entrySet = null;
        clone.navigableKeySet = null;
        clone.descendingMap = null;

        // Initialize clone with our mappings
        try {
            clone.buildFromSorted(size, entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }

        return clone;
    }

HashTable

HashTable的继承实现关系图：

HashTable<K,V>也是一种key-value结构，它继承自Dictionary<K,V>，实现了Map<K,V>, Cloneable, java.io.Serializable接口，也是支持可复制、可序列化的。

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable

HashTable的操作几乎和HashMap一致（下面不在重复），主要的区别在于HashTable为了实现多线程安全，在几乎所有的方法上都加上了synchronized关键字，而这就造成了HashTable操作的效率十分低下，现在几乎已经被弃用了。

【攻克java集合系列（四）】java集合中的Map系列集合全面分析