Java 集合体系之 Map 源码分析

前言

大家好，在之前的文章中，我们分析了 List 接口下的实现类 ArrayList 和 LinkedList 的源码。但是其中还有一个实现类 Vector 并没有说到，该类的实现与 ArrayList 基本相同，都是采用数组实现，区别就是其中的大量方法，如 add()、get() 等都是采用 synchronized 进行修饰，保证了线程安全。而 ArrayList 我们之前就分析过了，所以这里就不对 Vector 进行分析了，大家有兴趣可以自己看看源码。

下面我们该进入今天的主题了：来分析 Map 接口的源码。
“诶！你这跳转也太大了吧！Set 接口怎么还没分析就跳到 Map 了！”
别心急嘛，谁叫 HashSet 和 TreeSet 的内部实现都分别是由 HashMap 和 TreeMap 实现的呢？不先分析 Map 没办法呐… 好了，快进入正题吧。

概述

Java 中的 Map 接口和 Collection 接口一样，都是同一等级的根接口。Map 表示的是一个键（key）值（Value）对的映射，其中键是唯一的，每个键可以映射最多一个值。该接口取代了 Dictionary 抽象类。

需要注意的是，如果我们把可变对象作为 Map 的键，则必须要非常小心了，因为有可能会导致对象更改后查找不到对应的 value 了。这是因为，像 Map 的实现类，如 HashMap，是以 key 的哈希值来存储和查找键值对的（在后面的文章中会进行深深入分析），而一个可变对象在创建后其哈希值是可能被改变的。为了解决这种问题，我们最好是用 String、Integer 等不可变对象来作为 key，或者我们重写类的 hasCode() 、equals() 方法，用类的成员变量来进行计算。例如：

public class Person {
   
    private String id;
    public Person(String id) {
        this.id = id;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        if (id != null ? !id.equals(person.id) : person.id != null) return false;
        return true;
    }
    @Override
    public int hashCode() {
        return id != null ? id.hashCode() : 0;
    }
}

另外，我们虽然可以将 Map 作为 Map 的值，但是应避免将 Map 作为 Map 的键，因为 Map 比较复杂，比较难定义 hashCode() 与 equals() 方法。

Map 所有通用的实现类应该提供两个“标准”的构造函数：

• 一个无参数无返回值的空构造函数。
• 一个具有 Map 类型单个参数的构造函数，它创建一个具有参数相同键值的新 Map。

虽然没有强制要求这样做，但是我们要是自定义 Map 实现类时最好都按照这样来。

结构

上图是 Map 集合的整体 UML 图。在以后的文章，我们再来一个个分析 Map 接口下面的实现类、接口。

再来看看 Map 接口中都定义了一些什么方法：

其中，从 getOrDefault() 方法开始的方法，都是从 Java8 开始引入的新特性：默认方法。下面我们来开始从头开始一个一个分析。

源码分析

查询操作

/**
 * 返回此 map 中键值映射的数量。如果 map 包含多于 Integer.MAX_VALUE 的元素，返回 Integer.MAX_VALUE。
 */
int size();

/**
 * 如果此 map 中不包含键值映射，返回 true，否则返回 false。
 */
boolean isEmpty();

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

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

/**
 * 返回指定键映射的值，如果此映射中不包含该键的映射，则返回 null。
 */
V get(Object key);

修改操作

/**
 * 将指定的值于此 map 中指定的键相关联。
 * 如果 map 中已经存在该键，那么将会替换值。
 */
V put(K key, V value);

/**
 * 如果此 map 中存在指定 key 的映射，那么删除这个映射，并返回对于的值。
 * 如果不存在指定 key 的映射，那么返回 null。（如果此 map 允许 null 值
 * ，那么返回 null 并不一定表示该 map 不存在指定 key 的映射）
 */
V remove(Object key);

批量操作

/**
 * 将指定 map 中的所有映射复制到此 map。
 * 如果在操作过程中修改了指定的 map，则此操作的行为是未定义的。
 */
void putAll(Map<? extends K, ? extends V> m);

/**
 * 从此 map 中删除所有的映射。
 */
void clear();

查看

/**
 * 返回此 map 中包含所有键的 Set 集合。
 * 该集合由 map 支持，因此对 map 的更改将反映在集合中，反之亦然。
 * 如果在集合的迭代过程中修改了 map（除了用迭代器自己的删除操作之外），迭代的结果是未定义的。
 * 该集合支持删除元素，可以通过 Iteration.remove，Set.remove，removeAll，retainAll
 * 和 clear 操作从 map 中删除相应的映射。它不支持 add 或 addAll 操作。
 */
Set<K> keySet();

/**
 * 返回此 map 中包含所有值的 Collection 集合。
 * 该集合由 map 支持，因此对 map 的更改将反映在集合中，反之亦然。
 * 如果在集合的迭代过程中修改了 map（除了用迭代器自己的删除操作之外），迭代的结果是未定义的。
 * 该集合支持删除元素，可以通过 Iteration.remove，Collection.remove，removeAll，retainAll
 * 和 clear 操作从 map 中删除相应的映射。它不支持 add 或 addAll 操作。
 */
Collection<V> values();

/**
 * 返回此 map 中包含所有映射（Map.Entry）的 Set 集合。
 * 该集合由 map 支持，因此对 map 的更改将反映在集合中，反之亦然。
 * 如果在集合的迭代过程中修改了 map（除了用迭代器自己的删除操作，或
 * 通过迭代器返回的映射中的 setValue 操作之外），迭代的结果是未定义的。

 * 该集合支持删除元素，可以通过 Iteration.remove，Set.remove，removeAll，retainAll
 * 和 clear 操作从 map 中删除相应的映射。它不支持 add 或 addAll 操作。
 */
Set<Map.Entry<K, V>> entrySet();

Entry 是 Map 接口当中的一个内部接口，表示的是一个键值对的映射。其源码如下：

/**
 * map 条目（键值对）。通过 Map.entrySet() 方法可以获取在 Set 集合中其所有的映射条目。
 * 因为是 Set 集合，所以该映射条目也是唯一的。要想获取映射条目的引用唯一的方法就是通过集合的迭代器。
 * 这些 Map.Entry 对象仅在迭代期间有效。如果在迭代器返回条目之后修改了底层映射，
 * 除了通过映射条目上的 setValue 操作，则映射条目的行为是不确定的。
 */
interface Entry<K,V> {
    /**
     * 返回与此条目想对应的键。
     *