Java常用数据结构之Map-AbstractMap-白红宇

前言

Map集合是用来存储<Key, Value>键值对数据的，是日常开发中使用最多的数据结构之一。Map集合相对List集合来说结构会稍微复杂一些，所以Map系列会分开写。本文主要分析AbstractMap。

类图

Map接口中定义了各种基本方法，而键值对数据实际是保存在Entry中的。AbstractMap类和AbstractList类一样，都是一种模板类，提供了Map的基本实现。开发人员如果想实现自己的Map，只需要继承AbstractMap类，实现特定方法即可。

源码分析

唯一的抽象方法

整个AbstractMap类中只有一个抽象方法：

public abstract Set
    
     
      > entrySet();复制代码

也就是说所有的子类都必须实现entrySet()方法。纵观AbstractMap中的成员方法内部实现，基本都依赖于entrySet()方法，它返回了Map所保存的键值对。

重要的成员方法

AbstractMap有个默认抛UnsupportedOperationException异常的方法：

public V put(K key, V value) {        throw new UnsupportedOperationException();    }复制代码

整个put方法直接影响了：

public void putAll(Map
     m) {        for (Map.Entry
     e : m.entrySet())            put(e.getKey(), e.getValue());    }复制代码

也就是说Map默认是不支持修改的，子类如果想实现可变的Map，则需要重写put方法。

有put就应该有remove，来看看remove方法：

public V remove(Object key) {        // 使用到了entrySet()获取保存的数据        Iterator
    
     
      > i = entrySet().iterator();        Entry
      
        correctEntry = null;        // 通过迭代器找到要remove的值        if (key==null) {            while (correctEntry==null && i.hasNext()) {                Entry
       
         e = i.next();                if (e.getKey()==null)                    correctEntry = e;            }        } else {            while (correctEntry==null && i.hasNext()) {                Entry
        
          e = i.next();                if (key.equals(e.getKey()))                    correctEntry = e;            }        }        V oldValue = null;        if (correctEntry !=null) {            oldValue = correctEntry.getValue();            i.remove(); // 调用迭代器的remove方法        }        return oldValue;    }复制代码

Map的remove方法使用到了entrySet()所返回Set的迭代器的remove方法。

所以如果你想实现自己的Map结构：

1.当要实现一个不可变的Map时，需要继承AbstractMap，然后实现entrySet() 方法，这个方法返回一个保存所有key-value映射的Set。通常这个Set不支持add()和remove() 方法，Set对应的迭代器也不支持remove()方法。

2. 当要实现一个可变的 Map时，需要在上述操作外，重写put()方法，而且entrySet()返回的Set 的迭代器需要实现remove()方法。

重要的成员变量

AbstractMap只有两个成员变量：

transient Set
    
             keySet; // 不可序列化    transient Collection
     
       values; // 不可序列化复制代码

注意：从jdk1.8开始，这两个变量不再使用volatile修饰，因为调用这两个变量的方法不是同步的，增加volatile也不能保证线程安全。（本文用的是jdk11）

这里看一下怎么获取keySet：

public Set
    
      keySet() {        Set
     
       ks = keySet;        if (ks == null) {            // 自定义一个Set并且实现迭代器            ks = new AbstractSet
      
       () {                public Iterator
       
         iterator() {                    return new Iterator
        
         () {                        // 使用Entry的Set集合的迭代器                        private Iterator
         
          
           > i = entrySet().iterator(); public boolean hasNext() { return i.hasNext(); } public K next() { return i.next().getKey(); } public void remove() { i.remove(); } }; } 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; }复制代码

这里写的很巧妙，没用采用遍历Entry的方式，而是实现了一个自定义Set集合。这个集合再重写iterator方法，直接调用Entry集合的迭代器。values也做了同样的处理。

两个内部类

AbstractMap有两个内部类SimpleEntry<K,V>和SimpleImmutableEntry<K,V>，它们都实现了Entry<K,V>和Serializable。

SimpleEntry：表示值可变的键值对。

private final K key; // 不可变    private V value;复制代码

提供了相应的setValue方法：

public V setValue(V value) {            V oldValue = this.value;            this.value = value;            return oldValue; // 注意返回的是旧值        }复制代码

来看看equals方法：

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());        }            private static boolean eq(Object o1, Object o2) {        // 因为实际中o1很可能是String类型，所以这里使用了equals，而不是==        return o1 == null ? o2 == null : o1.equals(o2);    }复制代码

SimpleImmutableEntry：表示不可变的键值对。

private final K key; // 不可变    private final V value; // 不可变复制代码

它的setValue方法直接抛出异常：

public V setValue(V value) {            throw new UnsupportedOperationException();        }复制代码

总结

AbstractMap的核心方法是entrySet()，子类必须实现；

Entry是存储键值对的数据结构，子类根据Map的特点，构造不同的Entry；

参考资料

Java集合中的AbstractMap抽象类

Java 集合深入理解(15):AbstractMap

jdk8 api文档

前言

类图