java集合源码分析（五）：Map与AbstractMap

概述

Map 接口是 java 中两大集合接口之一，相对于 Collection，Map 接口结构规定了所有键值对形式的集合容器。同时，它与 Collection 的子接口 Set 又密切相关，Map 一部分实现依赖于 Set 集合，而 Set 集合的一些实现也依赖于 Map。

Map 接口下有四个主要实现类 TreeMap，HashMap，LinkedMap，Hashtable。基于以上四大实现类，这是他们的类关系图：

Map 接口的类关系图

与其相关的还有 Dictionary 类，这是一个已过时的早期键值对集合接口，后期的新集合都基于 Map 接口实现，唯一依赖与他的 Hashtable 因为性能原因也很少被使用，因此这个类是一个过时类。

这是关于 java 集合类源码的第五篇文章。往期文章：

1. java集合源码分析（一）：Collection 与 AbstractCollection
   
2. java集合源码分析（二）：List与AbstractList
3. java集合源码分析（三）：ArrayList
4. java集合源码分析（四）：LinkedList

一、Map 接口

image-20201207201537859

Map 接口就是所有键值对类型集合接口的最上层接口，他规定了一个所有 Map 类型集合应该实现的抽象方法，同时提供了一个用于视图操作的默认接口类 Entry。

1.抽象方法

查询操作

• size()：获取键值对数量；
• isEmpty()：是否为空；
• containsKey(Object key)：是否存在对应的 key；
• containsValue(Object value)：是否存在对应的 value；
• get(Object key)：根据 key 获取 value；

更改操作

• put(K key, V value)：添加一对键值对；
• remove(Object key)：根据 key 删除相应键值对；
• putAll(Map<? extends K, ? extends V> m)：合并 Map 集合；
• clear()：清空集合；

视图操作

Map 是一种很特殊的集合，他表示的是一系列键值对的映射关系，因而无法像 Collection 集合一样直接看做一种元素的集合。为此，Map 定义了实现类必须可以通过以下三种方法返回特定的三个视图以方便操作：

• Set<K> keySet()：返回一个由 key 组成的 Set 集合视图；
• Collection<V> values()：返回一个由 value 组成的 Collection 集合视图；
• entrySet()：返回一个由 key-value 对组成的 Set 视图；

其中，entrySet返回的元素其实就是 Map 的内部接口 Entry 的实现类，一个 Entry 对象表示一对 key 和 value。

2.默认方法

接口的默认方法是 JDK8 新特性之一，因此此类方法全为 JDK8 新增方法。

这类方法的特点是参数多为函数式结构，并且大部分不会被实现类重写。我们可以通过 lambda 表达式去调用。

• getOrDefault(Object key, V defaultValue)：获取 key 对应的 value，若不存在则返回 defaultValue；
• forEach(BiConsumer<? super K, ? super V> action)：遍历处理集合中的键值对；
• replaceAll(BiFunction<? super K, ? super V, ? extends V> function)：替换集合中的键值对；
• putIfAbsent(K key, V value)：仅当对应键值对不存在或 value 为 null 时新增；
• remove(Object key, Object value)：仅当对应键值存在并且 value 不为 null 时删除；
• replace(K key, V oldValue, V newValue)：仅当对应键值对存在，value 不为 null 且 value 等于指定 value 时（除非传入 null）替换旧 value；
• computeIfAbsent(K key,Function<? super K, ? extends V> mappingFunction)：如果当前键值对不存在，则将通过传入方法处理 key 得到的 value 与 key 一起添加到集合；
• computeIfPresent(K key,BiFunction<? super K, ? super V, ? extends V> remappingFunction)：如果当前键值对存在，则将原先的 value 更新为通过传入方法处理后的 value。如果处理后得到 null，则删除对应的键值对。
• compute(K key,BiFunction<? super K, ? super V, ? extends V> remappingFunction)：如果当前键值对存在，并且根据传入方法处理后得到的新 value 不为null，则更新键值对，否则则删除键值对。
• merge(K key, V value,BiFunction<? super V, ? super V, ? extends V> remappingFunction)：如果当前键值对不存在，则新 value 等于当前值，否则由根据传入方法处理得到。若新 value 不为 null，则更新键值对，否则就删除键值对。

3.equals和hashcode

在 Map 中，由于多数比较基于 equals() 和 hashCode() 方法，因此 Map 集合要求实现类重写实现这两个方法，其中：

equals() 要求以 m1.entrySet().equals(m2.entrySet()) 的形式实现两个 Map 集和的比较；

而 hashCode()则与 Collection 的 equals()类似，要求 Map 集合的 hashcode 应当为集合内所有 entrySet()的 hashcode 之和。

二、Entry 接口

Entry 是 Map 的一个内部接口类。跟一般的接口不太一样，Entry 的实现类实际上是作为 Map 中键值对对象使用的，即一对 key 和 value 就作为一个 Entry 对象。Entry 实际上是对 Map 实现类中使用的键值对对象的一种约束。根据 JavaDoc 的说明：

Map.entrySet方法返回 Map 的集合视图，该 Map 的元素属于此类。

这些 Map.Entry 对象仅在迭代期间有效。

他提供了九个基本的方法：

• getKey()：获取 key；
• getValue：获取 value；
• comparingByKey()：根据 key 排序；
• comparingByValue()：根据 value 排序；
• comparingByKey(Comparator<? super K> cmp)：根据 key 排序；
• comparingByValue(Comparator<? super V> cmp)：根据 value 排序。

我们也可以把 Entry 看成 Map 集合中的一种视图，只不过它只局限于一对键值对。

三、AbstractMap 抽象类

AbstractMap 与 AbstractList 一样，都是为于接口提供基本实现的抽象类。根据 JavaDoc，我们可以简单的了解一下它：

此类提供Map接口的基本实现，以最大程度地减少实现此接口所需的工作。

要实现不可修改的Map，程序员仅需要扩展此类并为 entrySet 方法提供实现，该方法将返回 Map 映射的 set-view。

通常，返回的集合将依次在 AbstractSet 之上实现。 此集合不支持add或remove方法，并且其迭代器不支持remove方法。

要实现可修改的Map，程序员必须另外重写此类的put方法（否则将引发UnsupportedOperationException ），并且entrySet（）。iterator（）返回的迭代器必须另外实现其 remove 方法。

1.成员变量

AbstractMap 内部拥有两个成员变量 keySet和 values：

// key的集合视图
transient Set<K> keySet;

// values的集合视图
transient Collection<V> values;

值得一提的是，针对获取 keySet 的同名抽象方法 keySet()的注释上，指明了：

这些字段中的每个字段都被初始化为在第一次请求此视图时包含相应视图的实例。 视图是无状态的，因此没有理由创建多个视图。

同样，实现也必须只读取一次该字段，如：

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

可见，keySet 获取实例是一个很典型的单例模式。

2.内部类

之前我们说，Map 接口提供的内部类接口 Entry，是为实现类的键值对对象提供约束。在 AbstractMap 中，就提供了两个实现了 Entry 接口的内部类 SimpleEntry 和 SimpleImmutableEntry。

SimpleEntry

SimpleEntry 是一个基于 Map 接口的内部接口类 Entry 的实现。他可以看成是集合中一对键值对对象的映射——或者说，视图。

当初始化时，需要传入 key 和 value 赋值给同名的成员变量，并且 key 会被 final 修饰，因而 key 不可更改，而 value 可以更改。

基于以上的原理，当 value 是引用类型，并且去修改它的时候，修改会真实的反应到外部类的 values 对应的那个 value 中，但是如果要做替换，则只能替换当前 SimpleEntry 对象中的 value。

public static class SimpleEntry<K,V> implements Entry<K,V>, java.io.Serializable{
    private static final long serialVersionUID = -8499721149061103585L;

    // key不可变
    private final K key;
    private V value;

    public SimpleEntry(K key, V value) {
        this.key   = key;
        this.value = value;
    }

    public SimpleEntry(Entry<? extends K, ? extends V> entry) {
        this.key   = entry.getKey();
        this.value = entry.getValue();
    }

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }
	
    // 更新值
    public V setValue(V value) {
        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }

    // 重写equals方法，要求key与value都需要相等
    public boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>)o;
        return eq(key, e.getKey()) && eq(value, e.getValue());
    }

    public int hashCode() {
        return (key   == null ? 0 :   key.hashCode()) ^
            (value == null ? 0 : value.hashCode());
    }

    public String toString() {
        return key + "=" + value;
    }

}

SimpleImmutableEntry

SimpleImmutableEntry 与 SimpleEntry 没什么不同，只不过多了和他名字一样的特性：“不可变”。

相对于 SimpleEntry，SimpleImmutableEntry 的 value 也被 final 修饰，并且调用它的 setValue()方法会抛出 UnsupportedOperationException异常。

public static class SimpleImmutableEntry<K,V> implements Entry<K,V>, java.io.Serializable {
    private final K key;
    private final V value;

    public V setValue(V value) {
        throw new UnsupportedOperationException();
    }

}

五、AbstractMap 的视图

1.四个视图

Map的三个视图

我们知道，由于 Map 是一个键值对集合，因此它实际存放的是 key 与 value，还有他们的映射关系。单个操作的时候很好操作，要么根据 key 找 value，要么直接 找 key 或者 value。但是当迭代的时候，我们就需要区分，是要迭代全部的 key，还是迭代全部的 value，还是要同时迭代全部的 key + value。因此，就有了 Map 的三个视图：

• key 视图 keySet：用于存放 key 的 Set 集合；
• value 视图 values：用于存放 value 的 Collection 集合；
• key-value 视图 entrySet：用于存放 key-value 的视图 Entry 的 Set 集合。

entrySet 比较不好理解，它里面放的是 Entry，一个 Entry 就代表一对键值对，因此，Entry 其实也可以理解为一个视图，这个视图只局限于一对键值对。

而 entrySet 装了集合里面全部的 Entry 视图，所以它也可以理解为一个表示整个 Map 容器中所有 key-value 的视图。或者简单粗暴的理解为entrySet = keySet + values。

由于 Entry 代表了键值对集合，因此也可以把 Map 集合以“Entry 对象的 Set 集合”——也就是 entrySet——表示。因此，在 Map 的实现类中，Entry 是一个很特别的类，他在很多的方法里都被作为参数使用。

2.视图类的实现

虽然定义好了视图类，但是 Map 接口并没有提供关于 keySet，values，Entry 与 entrySet 的实现。 但是定义了用于获取三个视图的方法 keySet()，values()和 enrtySet()。

AbstractMap 在上述基础上，提供了 keySet 和 values 作为成员变量，entrySet 变量需要由实现类自己去提供。

因此，如果一个实现类要实现 Map 接口，AbstractMap，理论上需要提供7个关于视图的实现类：

• KeySet 视图实现类，以及它的迭代器类;
• Values 视图实现类，以及它的迭代器；
• Entry 视图实现类；
• EntrySet 类，以及它的迭代器；

而在 AbstractMap 中，不提供 Entry 和 EntrySet 的实现，并且让 entrySet() 方法仍然保持抽象状态。

但是以匿名内部类的形式实现了 KeySet 和 Values 视图，并且让两者的迭代器都使用 entrySet()方法返回的 EntrySet 实现类提供的迭代器。

也就是说，如果一个类要实现 Map 接口，那么通过继承 AbstractMap，它只需要再提供3个实现类就可以了：

• EntrySet 实现类，以及它的迭代器；
• Entry 视图实现类。

3.keySet()

keySet()方法用于获取集合内部存放 key 的 Set 集合 keySet。他直接返回了一个继承并且实现了 AbstractSet 抽象方法 iterator() 的匿名内部类，并且直接使用 EntrySet 的迭代器。

public Set<K> keySet() {
    // 获取 keySet
    Set<K> ks = keySet;
    // 如果keySet为null，就创建一个自定义的 AbstractSet
    if (ks == null) {
        ks = new AbstractSet<K>() {
            // 实现了AbstractSet中的iterator()方法
            public Iterator<K> iterator() {
                // 返回一个自定义的迭代器类
                return new Iterator<K>() {
                    
                    // 获取entrySet返回的Set集合的迭代器，以下方法全部基于改迭代器实现
                    private Iterator<Entry<K,V>> i = entrySet().iterator();
                    
                    public boolean hasNext() {
                        return i.hasNext();
                    }

                    public K next() {
                        return i.next().getKey();
                    }

                    public void remove() {
                        i.remove();
                    }
                };
            }
			
            // 以下方法全部都调用AbstractMap的实现
            
            public int size() {
                return AbstractMap.this.size();
            }

            public boolean isEmpty() {
                return AbstractMap.this.isEmpty();
            }

            public void clear() {
                AbstractMap.this.clear();
            }

            public boolean contains(Object k) {
                return AbstractMap.this.containsKey(k);
            }
        };
        keySet = ks;
    }
    return ks;
}

也就是说，AbstractMap 中使用的 keySet 相当于一个单例的 AbstractSet 内部实现类，这类的迭代器就是 entrySet()方法返回的 Set 集合的迭代器；而其他的方法直接使用外部类 AbstractMap 的：

keySet 方法的实现

4.values()

AbstractMap 的 values()方法和 keySet()类似。它返回一个继承了 AbstractCollection 抽象类的匿名内部类：

public Collection<V> values() {
    Collection<V> vals = values;
    if (vals == null) {
        vals = new AbstractCollection<V>() {
            // 使用entrySet().iterator()获取的迭代器
            public Iterator<V> iterator() {
                return new Iterator<V>() {
                    private Iterator<Entry<K,V>> i = entrySet().iterator();

                    public boolean hasNext() {
                        return i.hasNext();
                    }

                    public V next() {
                        return i.next().getValue();
                    }

                    public void remove() {
                        i.remove();
                    }
                };
            }

            // 直接使用AbstractMap提供的方法
            
            public int size() {
                return AbstractMap.this.size();
            }

            public boolean isEmpty() {
                return AbstractMap.this.isEmpty();
            }

            public void clear() {
                AbstractMap.this.clear();
            }

            public boolean contains(Object v) {
                return AbstractMap.this.containsValue(v);
            }
        };
        values = vals;
    }
    return vals;
}

五、AbstractMap 的方法

1.不支持的实现

如类注释所说，AbstractMap 不支持 put()

public V put(K key, V value) {
    throw new UnsupportedOperationException();
}

因此经过已经实现了部分逻辑，但是 putAll()在实现 put()方法之前也无法使用：

public void putAll(Map<? extends K, ? extends V> m) {
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
        put(e.getKey(), e.getValue());
}

2.实现的方法

查询操作

public int size() {
    return entrySet().size();
}

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

更改操作

//  get
public V get(Object key) {
    Iterator<Entry<K,V>> i = entrySet().iterator();
    // 指定要获取的key是否为null
    if (key==null) {
        while (i.hasNext()) {
            Entry<K,V> e = i.next();
            // 返回对应的value
            if (e.getKey()==null)
                return e.getValue();
        }
    } else {
        while (i.hasNext()) {
            Entry<K,V> e = i.next();
            if (key.equals(e.getKey()))
                return e.getValue();
        }
    }
    return null;
}

// remove
public V remove(Object key) {
    // 获取entrySet的迭代器
    Iterator<Entry<K,V>> i = entrySet().iterator();
    Entry<K,V> correctEntry = null;
    // 指定要删除的key是否为null
    if (key==null) {
        while (correctEntry==null && i.hasNext()) {
            Entry<K,V> e = i.next();
            // 找出key为null的那对键值对
            if (e.getKey()==null)
                correctEntry = e;
        }
    } else {
        while (correctEntry==null && i.hasNext()) {
            Entry<K,V> e = i.next();
            // 找出指定键值对
            if (key.equals(e.getKey()))
                correctEntry = e;
        }
    }

    V oldValue = null;
    if (correctEntry !=null) {
        // 根据key获取value
        oldValue = correctEntry.getValue();
        // 删除该键值对
        i.remove();
    }
    return oldValue;
}

// clear
public void clear() {
    entrySet().clear();
}

3.equals / hashCode

集合容器基本都会重写 equals() 和 hashCode()方法，AbstractMap 亦然。

equals

public boolean equals(Object o) {
    // 是否同一个对象
    if (o == this)
        return true;

    // 是否实现Map接口
    if (!(o instanceof Map))
        return false;
    Map<?,?> m = (Map<?,?>) o;
    // 是否长度相同
    if (m.size() != size())
        return false;

    try {
        // 遍历自己的键值对
        Iterator<Entry<K,V>> i = entrySet().iterator();
        while (i.hasNext()) {
            Entry<K,V> e = i.next();
            K key = e.getKey();
            V value = e.getValue();
            // value是否为null
            if (value == null) {
                // 是否在比较的集合中key存在，并且对应的value是null
                if (!(m.get(key)==null && m.containsKey(key)))
                    return false;
            } else {
                // 若value不为null，比较是否value一致
                if (!value.equals(m.get(key)))
                    return false;
            }
        }
    } catch (ClassCastException unused) {
        return false;
    } catch (NullPointerException unused) {
        return false;
    }

    return true;
}

hashCode

AbstractMap 的 hashcode 是集合内所有 entrySet 对象的 hashcode 之和。

public int hashCode() {
    int h = 0;
    Iterator<Entry<K,V>> i = entrySet().iterator();
    while (i.hasNext())
        h += i.next().hashCode();
    return h;
}

4.toSring

public String toString() {
    Iterator<Entry<K,V>> i = entrySet().iterator();
    if (! i.hasNext())
        return "{}";

    StringBuilder sb = new StringBuilder();
    sb.append('{');
    for (;;) {
        Entry<K,V> e = i.next();
        K key = e.getKey();
        V value = e.getValue();
        sb.append(key   == this ? "(this Map)" : key);
        sb.append('=');
        sb.append(value == this ? "(this Map)" : value);
        if (! i.hasNext())
            return sb.append('}').toString();
        sb.append(',').append(' ');
    }
}

5.clone

protected Object clone() throws CloneNotSupportedException {
    AbstractMap<?,?> result = (AbstractMap<?,?>)super.clone();
    result.keySet = null;
    result.values = null;
    return result;
}

六、总结

Map接口

Map 接口规定了所有键值对类型的集合容器。他底下有 Hashtable，HashMap，TreeMap，以及 HashMap 的子类 LinkedMap 四个主要的实现类。

与他类似的还有 Dictionary 接口，Hashtable 实现了该接口。这是一个已经过时的键值对容器接口。

AbstractMap 抽象类为 Map 接口提供了大部分的实现。处理 Hashtable 外，其他三个主要实现类都继承了他。

在 Map 接口中，提供了键值对视图的接口 Entry，并且规定实现类需要实现 entrySet()，keySet()，values() 三个抽象方法，以返回 Entry 的 Set 集合视图，key 的 Set 集合视图以及 value 的 Collection 集合视图。

AbstractMap

在 AbstractMap 中，实现了 keySet()，values() 方法，并且提供了相应的成员变量 keySet 和 values 。但是没有提供 EntrySet 的实现类，也没有实现 entrySet() 方法。

用于获取 key 的keySet() 方法会返回一个 AbstractSet 的匿名实现类，迭代器通过 entrySet()获取实现类实现的 EntrySet 类的迭代器， 而其他方法直接使用 AbstractMap 的。用于获取 value 的values()方法也是如此，只不过返回的是一个 AbstractCollection 的匿名实现类。

针对 Entry 接口，AbstractMap 提供了 SimpleEntry 与 SimpleImmutableEntry 两个类，相对前者，后者的 value 被 final 修饰，并且调用 setValue() 方法会抛出 UnsupportedOperationException 异常，因而是不可变的。