引言

Map接口是Map类层次结构中的最上层接口，它定义Map的公共行为，例如put、get等。AbstractMap作为Map的实现类，给出了Map接口中一些方法的实现。这篇文章，我们来看Map接口中方法的定义和AbstractMap中对重点方法的实现逻辑。

Map对Key和Value的限制

虽然Map只是一个接口，它的很多实现如HashMap、TreeMap、LinkedHashMap都有不同的特性。但是就Map本身来说，它对于Key和Value是有一个最根本的限制的，这些限制对于每个Map的实现都有效：

  • Key是不能重复的。也就是一个Key最多只能映射到一个Value上面。

key不能重复意味着每个map最多有一个为null的key，具体Map对为null的键怎么处理，需要不同的Map子类来自己实现，你可以允许有一个为null的key，也可以不允许有为null的key。
对于value，Map本身并没有对重复性作出规定，所以两个不同的key可以映射到相同的value，而对于为null的value怎么处理，也需要各个Map子类自己实现。
我们以HashMap为例，来看看它是怎么处理这些情况的：

  1. public static void main(String[] args) {
  2.         Map<String,Object> map = new HashMap<>();
  3.         Object o = new Object();
  4.         map.put("String1",new Object());
  5.         map.put("String1","string1");
  6.         map.put("String2",o);
  7.         map.put("String3",o);
  8.         map.put(null,"a string");
  9.         map.put("string5",null);
  10.         map.put("string6",null);
  11.         map.put(null,"a new string");
  12.         System.out.println(map.get("String1"));
  13.         System.out.println(map.get("String2") == map.get("String3"));
  14.         System.out.println(map.get(null));
  15.     }

在这个例子中，前两个put操作的是同一个key，它可以证明map不能有重复的key出现，如果对同一个key执行put操作，则其原值会被覆盖；第三个和第四个put证明两个key可以映射到一个value；第五个put存入了一个key为null的映射，第六和第七个put存入的两个映射的value都是null，最后一个put修改了key为null的映射的值。我们看输出：

  1. string1
  2. true
  3. a new string

这个例子说明HashMap允许一个key为null的映射，允许多个value为null的映射，不同的key可以映射到相同的value。

Map接口的方法划分

从总体上来看，Map接口将提供的方法划分为了几大类：Query Operations，这类操作包括获取map的大小、根据key查询value等；Modification Operations，这类操作用来对Map进行修改，包括put、remove、putAll等；Views，这类方法用来返回Map的集合视图，例如返回所有key的keySet、返回所有values的values方法和返回所有映射的entrySet方法等。还要其他类型的操作方法，这里我们不重点描述。整体的划分可看下表：

类型 描述 包含方法
Query Operations 查询操作，如返回大小、查询value等 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 视图，返回所有的key、所有的value和所有的映射等。 Set keySet();
Collection values();
Set> entrySet();

这几类方法就大概定义了所有Map中要用到的重要的公共行为。
关于Views类方法，我们需要注意下：

  1. keySet方法返回所有的key，为什么要放到一个set里面呢？因为key是不能重复的，而set保证了这一点。
  2. values方法返回的是所有的value，因为value是可以重复的，所以它的返回值是一个集合而不是set。
  3. entrySet方法返回的是所有的映射。它的返回值是Entry的set，Entry是Map接口的内部类。关于Entry我们马上会介绍。

    通过Entry获取键值对集合

    Entry代表Map中的一个条目也就是一个键值对。我们可以使用map的entrySet方法获取这些条目的集合，也就是获取这些键值对。很重要的一点是：要想得到一个到map条目的引用，我们只能通过迭代这个集合来实现，这是唯一获得map条目引用的方式，也是Entry存在的意义。如果你不是很明白，看这个例子：
    1. public static void main(String[] args) {
    2.      Map<String,Object> map = new HashMap<>();
    3.      map.put("string1",new Object());
    4.      map.put("string2",new Object());
    5.      for (Map.Entry<String, Object> entry : map.entrySet()) {
    6.          System.out.println(entry.getKey());
    7.          System.out.println(entry.getValue());
    8.      }
    9.  }
    我们想获得Map的所有映射，就可以通过调用entrySet方法来实现，然后通过迭代entrySet返回的集合，我们就能拿到每个Entry。
    我们来看Entry的实现：
    在Map接口中，Entry是一个内部的接口：
    1. interface Entry<K,V> {}
    它的两个泛型参数就是Map的泛型参数。
    它提供了一些方法来对键和值进行操作：
    1. K getKey();
    2. V getValue();
    3. V setValue(V value);
    前两个方法分别获取key和value，setValue设置value值。为什么没有setKey呢？因为在Map中，key是不能重复的，为了保证这个限制，所以不会提供setKey方法。注意这里的setValue是有返回值的，它返回的是之前的value。
    因为Entry在Map中只是一个接口，所以没有任何的字段，实际上，每个Entry应该有它所代表的映射的key和value作为自己的属性，实际上，每个Map如HashMap、TreeMap等都会有自己内部的Entry实现，这些我们陆续会看到。

    AbstractMap对方法的实现

    AbstractMap实现了Map接口并对其中的部分方法进行了实现。AbstractMap类也是每个Map如HashMap、TreeMap的父类，所以它实现的方法是这些map中逻辑都一样的方法。我们来看它们的实现逻辑。

    size和isEmpty方法

    ```java public int size() {
    1.  return entrySet().size();
    }

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

  1. size方法返回的是entrySet的size，前面我们知道，entrySet方法会返回map中所有的条目的set。而isEmpty方法则是调用了size方法，判断size是否等于0。所以这两个方法的实现还是依赖与entrySet方法：
  2. ```java
  3. public abstract Set<Entry<K,V>> entrySet();

这个方法在AbstractMap中是一个抽象方法，也就是它的逻辑需要每种map自己去实现。

containsValue和containsKey方法

containsValue用来判断map中是否含有参数指定的value：

  1. public boolean containsValue(Object value) {
  2.         Iterator<Entry<K,V>> i = entrySet().iterator();
  3.         if (value==null) {
  4.             while (i.hasNext()) {
  5.                 Entry<K,V> e = i.next();
  6.                 if (e.getValue()==null)
  7.                     return true;
  8.             }
  9.         } else {
  10.             while (i.hasNext()) {
  11.                 Entry<K,V> e = i.next();
  12.                 if (value.equals(e.getValue()))
  13.                     return true;
  14.             }
  15.         }
  16.         return false;
  17.     }

它也是先调用了entrySet方法获取了所有条目的集合，然后在集合上遍历来查找指定的value。注意value为null的情况，如果value为null，只要entry集合中一个entry的getValue方法返回null，即认为找到。如果value不是null，通过equals方法对比每个entry的value与参数给定的value，找到一个即返回true。
containsKey用来判断map是否含有参数指定的key：

  1. public boolean containsKey(Object key) {
  2.         Iterator<Map.Entry<K,V>> i = entrySet().iterator();
  3.         if (key==null) {
  4.             while (i.hasNext()) {
  5.                 Entry<K,V> e = i.next();
  6.                 if (e.getKey()==null)
  7.                     return true;
  8.             }
  9.         } else {
  10.             while (i.hasNext()) {
  11.                 Entry<K,V> e = i.next();
  12.                 if (key.equals(e.getKey()))
  13.                     return true;
  14.             }
  15.         }
  16.         return false;
  17.     }

这个逻辑与containsValue类似，这里不再赘述。
所以containsKey和containsValue这两个方法的实现也依赖与entrySet。

get方法

get方法根据参数指定的key来找到value：

  1. public V get(Object key) {
  2.         Iterator<Entry<K,V>> i = entrySet().iterator();
  3.         if (key==null) {
  4.             while (i.hasNext()) {
  5.                 Entry<K,V> e = i.next();
  6.                 if (e.getKey()==null)
  7.                     return e.getValue();
  8.             }
  9.         } else {
  10.             while (i.hasNext()) {
  11.                 Entry<K,V> e = i.next();
  12.                 if (key.equals(e.getKey()))
  13.                     return e.getValue();
  14.             }
  15.         }
  16.         return null;
  17.     }

同样需要获取entry集合，然后遍历查找。如果参数key为null，只找到key为null的entry，返回value即可；如果参数key不为null，根据equals方法判断key是否相等，相等即返回value即可。
所以get方法同样依赖entrySet方法。

remove方法和clear方法

remove方法用来删除参数指定的key所在的entry：

  1. public V remove(Object key) {
  2.         Iterator<Entry<K,V>> i = entrySet().iterator();
  3.         Entry<K,V> correctEntry = null;
  4.         if (key==null) {
  5.             while (correctEntry==null && i.hasNext()) {
  6.                 Entry<K,V> e = i.next();
  7.                 if (e.getKey()==null)
  8.                     correctEntry = e;
  9.             }
  10.         } else {
  11.             while (correctEntry==null && i.hasNext()) {
  12.                 Entry<K,V> e = i.next();
  13.                 if (key.equals(e.getKey()))
  14.                     correctEntry = e;
  15.             }
  16.         }
  18.         V oldValue = null;
  19.         if (correctEntry !=null) {
  20.             oldValue = correctEntry.getValue();
  21.             i.remove();
  22.         }
  23.         return oldValue;
  24.     }

它同样获取了entry集合的迭代器，然后找到第一个key为null（参数key==null）或者key==参数key的entry，找到之后通过iterator的remove方法将其删除。
clear方法直接调用的是entrySet返回的entry集合的clear方法，也就是它清空了整个entry集合：

  1. public void clear() {
  2.         entrySet().clear();
  3.     }

put方法和putAll方法

put方法在AbstractMap中没有给出实现，需要每种map自己去实现：

  1. public V put(K key, V value) {
  2.         throw new UnsupportedOperationException();
  3.     }

putAll方法会循环调用put方法将参数map中的每个条目加到当前map中：

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

keySet和values方法

这两个方法分别用来返回key的set和value的集合。在AbstractMap中，这两个方法的实现很巧妙：首先，AbstractMap中有两个成员变量：

  1. transient Set<K>        keySet;
  2. transient Collection<V> values;

分别代表所有的key组成的set和所有values组成的集合。但是这两个成员变量是无状态的，为什么说无状态呢？我们来看keySet方法：

  1. public Set<K> keySet() {
  2.         //首先判断keySet成员变量是否为null，也就是是否被初始化过
  3.         Set<K> ks = keySet;
  4.         //如果没被初始化，先进行初始化
  5.         if (ks == null) {
  6.             //ks是一个AbstractSet，AbstractMap是所有set的父类，但是只实现了几个特定的方法如remove、removeAll，
  7.             //一些其他方法如add没有实现
  8.             ks = new AbstractSet<K>() {
  9.                 //重写了AbstractSet的iterator逻辑 这个iterator的方法都是通过entrySet的iterator
  10.                 //来实现的
  11.                 public Iterator<K> iterator() {
  12.                     return new Iterator<K>() {
  13.                         private Iterator<Entry<K,V>> i = entrySet().iterator();
  15.                         public boolean hasNext() {
  16.                             return i.hasNext();
  17.                         }
  19.                         public K next() {
  20.                             return i.next().getKey();
  21.                         }
  23.                         public void remove() {
  24.                             i.remove();
  25.                         }
  26.                     };
  27.                 }
  28.                 //AbstractSet的size、isEmpty、clear和contains方法都是通过AbstractMap的对应方法
  29.                 //来实现的
  30.                 public int size() {
  31.                     return AbstractMap.this.size();
  32.                 }
  34.                 public boolean isEmpty() {
  35.                     return AbstractMap.this.isEmpty();
  36.                 }
  38.                 public void clear() {
  39.                     AbstractMap.this.clear();
  40.                 }
  42.                 public boolean contains(Object k) {
  43.                     return AbstractMap.this.containsKey(k);
  44.                 }
  45.             };
  46.             keySet = ks;
  47.         }
  48.         return ks;
  49.     }

可以看到整个keySet虽然是一个AbstractSet，但是它的每个操作（返回大小、清空、迭代方法等）都是通过它所属的AbstractMap的对应方法来实现的，它本身没有任何的字段或者说是无状态的。所以keySet只需要初始化一次即可。
values与keySet的实现类似，它的每个操作也是通过所属的AbstractMap对应的方法来实现的，也是无状态的。

  1. public Collection<V> values() {
  2.         Collection<V> vals = values;
  3.         if (vals == null) {
  4.             vals = new AbstractCollection<V>() {
  5.                 public Iterator<V> iterator() {
  6.                     return new Iterator<V>() {
  7.                         private Iterator<Entry<K,V>> i = entrySet().iterator();
  9.                         public boolean hasNext() {
  10.                             return i.hasNext();
  11.                         }
  13.                         public V next() {
  14.                             return i.next().getValue();
  15.                         }
  17.                         public void remove() {
  18.                             i.remove();
  19.                         }
  20.                     };
  21.                 }
  23.                 public int size() {
  24.                     return AbstractMap.this.size();
  25.                 }
  27.                 public boolean isEmpty() {
  28.                     return AbstractMap.this.isEmpty();
  29.                 }
  31.                 public void clear() {
  32.                     AbstractMap.this.clear();
  33.                 }
  35.                 public boolean contains(Object v) {
  36.                     return AbstractMap.this.containsValue(v);
  37.                 }
  38.             };
  39.             values = vals;
  40.         }
  41.         return vals;
  42.     }

根据keySet和values的这种实现方式，我们需要注意

  1. ：keySet实际上是一个AbstractSet，而AbstractSet没有给出add方法的实现，它的add方法是继承自AbstractCollection的：
    1. public boolean add(E e) {
    2.      throw new UnsupportedOperationException();
    3.  }
    所以我们如果对keySet得到的set执行add方法肯定就不行：
    1. public static void main(String[] args) {
    2.      Map<String,Object> map = new HashMap<>();
    3.      map.put("string1",new Object());
    4.      map.put("string2",new Object());
    5.      Set<String> strings = map.keySet();
    6.      strings.add("string3");
    7.  }
    运行结果：
    1. Exception in thread "main" java.lang.UnsupportedOperationException
    2.  at java.util.AbstractCollection.add(AbstractCollection.java:262)
    3.  at person.andy.concurrency.collection.map.MapNullTest.main(MapNullTest.java:13)
    果然报错。同样的道理，我们也不能对values返回的collection（AbstractCollection）执行add方法。
    其实想想也应该不能支持add方法，map毕竟是一个键值对的映射，不能只添加键或者只添加值。
    2.因为重写了iterator，并且给出了next、remove等方法的实现（映射到了entrySet iterator上的对应方法），所以我们可以遍历keySet和values，也可以执行remove方法来删除里面的元素，对keySet和values的删除实际上就是执行的entrySet的删除。看下面的例子:
    1. public static void main(String[] args) {
    2.      Map<String,Object> map = new HashMap<>();
    3.      map.put("string1",new Object());
    4.      map.put("string2",new Object());
    5.      Set<String> strings = map.keySet();
    6.      strings.remove("string1");
    7.      for (Map.Entry<String, Object> entry : map.entrySet()) {
    8.          System.out.println(entry.getKey());
    9.      }
    10.  }
    我们删除了keySet中的一个元素，输出：
    1. string2
    所以说，keySet和values只是提供了一个key和value的集合视图，它们实际的操作是映射到entrySet上的。

    AbstractMap中的Entry

    SimpleEntry

    SimpleEntry实际上就是Map中的Entry的最简单的实现，它只是在Entry接口的基础上增加了key和value这两个字段：
    1. private final K key;
    2. private V value;
    注意这里的key是final即不可变的。它也对getKey、getValue和setValue方法进行了实现，就是简单的get/set的逻辑，这里不再赘述。

    SimpleImmutableEntry

    SimpleImmutableEntry与SimpleEntry不同的是，它的value也是final即不可变的：
    1. private final K key;
    2. private final V value;
    因为value不可变，所以set方法不能设置value：
    1. public V setValue(V value) {
    2.          throw new UnsupportedOperationException();
    3.      }
    它抛出了一个UnsupportedOperationException。

    小结

    这篇文章，我们分析了Map结构体系中的最上层接口Map接口的方法定义和划分，还分析了AbstractMap对Map接口中几个方法的实现。可以看到，虽然AbstractMap实现了Map中的大部分方法，但是这些方法都依赖与entrySet，而entrySet方法需要每种map自己去实现。所以我们在分析每种map的实现时，entrySet方法的逻辑是需要重点关注的。