Java 8 容器源码-Map整体架构

前面已经学习了List的实现类并做了总结，接下来学习Map的实现类。原本想学习Set，可仔细一想，Set的某些实现类如HashSet实现是基于HashMap的，TreeSet的实现也依赖于TreeMap。所以就决定先学习Map。本文主要介绍Map的整体结构，并简单介绍结构中的接口和抽象类。

Map的整体结构

Map是一种把键对象和值对象映射的集合，它的每一个元素都包含一对键对象和值对象。 Map没有继承Collection接口。

• AbstractMap：实现了Map接口的抽象类。Map的基本实现，其他Map的实现类可以通过继承AbstractMap来减少编码量。
• SortedMap：继承Map。保证按照键的升序排列的映射，对entrySet、keySet和values方法返回的结果进行迭代时，顺序就会反映出来。
• NavigableMap：继承SortedMap，含有返回特定条件最近匹配的导航方法。
• HashMap：Map接口基于哈希表的实现，是使用频率最高的用于键值对处理的数据类型。它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，特点是访问速度快，遍历顺序不确定，线程不安全，最多允许一个key为null，允许多个value为null。可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap类。
• HashTable：Hashtable和HashMap从存储结构和实现来讲有很多相似之处，不同的是它承自Dictionary类，而且是线程安全的，另外Hashtable不允许key和value为null。并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以使用HashMap，需要线程安全的场合可以使用ConcurrentHashMap。
• LinkedHashMap： LinkedHashMap继承了HashMap，是Map接口的哈希表和链接列表实现。它维护着一个双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。
• WeakedHashMap： 以弱键实现的基于哈希表的Map。在WeakHashMap中，当某个键不再正常使用时，将自动移除其条目。
• TreeMap ： Map接口基于红黑树的实现。

Map

部分顶部注释

An object that maps keys to values. A map cannot contain duplicate keys;each key can map to at most one value.

Map是键值对的映射。map中不能含有重复的key，每个key最多只能映射到一个value。

This interface takes the place of the Dictionary class, which was a totally abstract class rather than an interface.

Map接口代替了抽象类Dictionary。

The Map interface provides three collection views, which allow a map’s contents to be viewed as a set of keys, collection of values,or set of key-value mappings. The order of a map is defined as the order in which the iterators on the map’s collection views return their elements. Some map implementations, like the TreeMap class, make specific guarantees as to their order; others, like the HashMap class, do not.

Map接口提供了三种集合视图，允许以键集、值集或键-值映射关系集的形式查看某个映射的内容。map的顺序定义在map的集合视图的迭代器中。一些Map接口的实现，如TreeMap，保证了顺序，而其他的Map实现，如HashMap，则不保证。

定义

public interface Map<K,V>

方法声明

• Query Operations

  • int size();
  • boolean isEmpty();
  • boolean containsKey(Object key);
  • boolean containsValue(Object value);
  • V get(Object key);

• Modification Operations

  • V put(K key, V value);
  • V remove(Object key);
  • void putAll(Map<? extends K, ? extends V>m);
  • void clear();

• Views

  • Set keySet();
  • Collection values();
  • Set<Map.Entry<K, V>> entrySet();

• Comparison and hashing

  • boolean equals(Object o);
  • int hashCode();

• Defaultable methods

  • default V getOrDefault(Object key, V defaultValue) {}
  • default void forEach(BiConsumer<? super K, ? super V> action) {}
  • default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {//省略方法体}
  • default V putIfAbsent(K key, V value) {//省略方法体}
  • default boolean remove(Object key, Object value) {//省略方法体}
  • default boolean replace(K key, V oldValue, V newValue) {//省略方法体}
  • default V replace(K key, V value) {//省略方法体}
  • default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {//省略方法体}
  • default V computeIfPresent(K key, BiFunction<? super K, ? super V, ? - extends V> remappingFunction) {//省略方法体}
  • default V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {//省略方法体}
  • default V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {//省略方法体}

内部接口

interface Entry<K,V> {}

AbstractMap

部分顶部注释

This class provides a skeletal implementation of the Map interface, to minimize the effort required to implement this interface.

AbstractMap提供了Map的基本实现，通过继承AbstractMap，可以将实现Map的代码最简化。

定义

public abstract class AbstractMap<K,V> implements Map<K,V>

方法

• 构造方法

  • protected AbstractMap() {}

• Query Operations

  • public int size() {}
  • public boolean isEmpty() {//方法体}
  • public boolean containsValue(Object value) {//方法体}
  • public boolean containsKey(Object key) {//方法体}
  • public V get(Object key) {//方法体}

• Modification Operations

  • public V put(K key, V value) {//方法体}
  • public V remove(Object key) {//方法体}
  • Bulk Operations
  • public void putAll(Map<? extends K, ? extends V> m) {//方法体}
  • public void clear() {//方法体}

• // Views

  • transient Set keySet;
  • transient Collection values;
  • public Set keySet() {//方法体}
  • public Collection values() {//方法体}
  • public abstract Set<Entry<K,V>> entrySet();

• Comparison and hashing

  • public boolean equals(Object o) {//方法体}
  • public String toString() {//方法体}
  • protected Object clone() throws CloneNotSupportedException {//方法体}
  • private static boolean eq(Object o1, Object o2) {//方法体}

内部类

                public static class SimpleEntry<K,V>
                        implements Entry<K,V>, java.io.Serializable{//内容}
            
                public static class SimpleImmutableEntry<K,V>
                        implements Entry<K,V>, java.io.Serializable{//内容}

SortedMap

部分顶部注释

A Map that further provides a total ordering on its keys.The map is ordered according to the Comparable natural ordering of its keys, or by a Comparator typically provided at sorted map creation time. This order is reflected when iterating over the sorted map’s collection views (returned by the entrySet, keySet and values methods).

大意为SortedMap保证按照键的升序排列的映射，对entrySet、keySet和values方法返回的结果进行迭代时，顺序就会反映出来。

定义

public interface SortedMap<K,V> extends Map<K,V>

方法

• 获取用来排序的comparator

  • Comparator<? super K> comparator();

• 获取键-值对的子集

  • SortedMap<K,V> subMap(K fromKey, K toKey);
  • SortedMap<K,V> headMap(K toKey);
  • SortedMap<K,V> tailMap(K fromKey);

• 查找方法

  • K firstKey();
  • K lastKey();

• 获取键集、值集、键值对集

  • Set keySet();
  • Collection values();
  • Set<Map.Entry<K, V>> entrySet();

NavigableMap

部分顶部注释

A SortedMap extended with navigation methods returning the closest matches for given search targets.

大意为NavigableMap继承SortedMap，含有返回特定条件最近匹配的导航方法。

定义

            public interface NavigableMap<K,V> extends SortedMap<K,V>

方法

• 操作键-值对和键

  • Map.Entry<K,V> lowerEntry(K key);
  • K lowerKey(K key);
  • Map.Entry<K,V> floorEntry(K key);
  • K floorKey(K key);
  • Map.Entry<K,V> ceilingEntry(K key);
  • K ceilingKey(K key);
  • Map.Entry<K,V> higherEntry(K key);
  • K higherKey(K key);
  • Map.Entry<K,V> firstEntry();
  • Map.Entry<K,V> lastEntry();
  • Map.Entry<K,V> pollFirstEntry();
  • Map.Entry<K,V> pollLastEntry();

• 返回一个NavigableMap

  • NavigableMap<K,V> descendingMap();

• 获取键集

  • NavigableSet navigableKeySet();
  • NavigableSet descendingKeySet();

• 获取键-值对的子集

  • NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,K toKey, boolean toInclusive);
  • NavigableMap<K,V> headMap(K toKey, boolean inclusive);
  • NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
  • SortedMap<K,V> subMap(K fromKey, K toKey);
  • SortedMap<K,V> headMap(K toKey);
  • SortedMap<K,V> tailMap(K fromKey);

NavigableMap除了继承SortedMap的方法外，它的提供的功能可以分为4类：

• 操作键-值对的方法。lowerEntry、floorEntry、ceilingEntry 和 higherEntry 方法，它们分别返回与小于、小于等于、大于等于、大于给定键的键关联的 Map.Entry 对象。firstEntry、pollFirstEntry、lastEntry 和 pollLastEntry 方法，它们返回和/或移除最小和最大的映射关系（如果存在），否则返回 null。
• 提供操作键的方法。lowerKey、floorKey、ceilingKey 和 higherKey 方法，它们分别返回与小于、小于等于、大于等于、大于给定键的键。
• 获取键集。navigableKeySet、descendingKeySet分别获取正序/反序的键集。
• 获取键-值对集的子集。