Java源码分析 AbstractMap的keySet()方法

叁歲伎倆 2023-05-30 10:47 3阅读 0赞

### 文章目录 ###

*  通过继承AbstractMap来实现一个Map
 *  分析AbstractMap的keySet()方法
 *  分析总结

# 通过继承AbstractMap来实现一个Map #

本章例子来自java编程思想小节——17.2.3 使用Abstract类——其中的Countries类。为了方便测试，将书中代码进行略微修改。该例子通过继承AbstractMap来实现了一个自己的Map，同时Map的数据放在了一个静态变量——体现了“享元设计模式”。  
虽然本章例子和`AbstractMap`的`keySet()`方法没有直接关系，但体现了继承`AbstractMap`时只需要实现`entrySet()`方法即可，对于理解`keySet()`方法是很有帮助的。

package com;
    import java.util.*;
    
    public class Countries { 
        public static final String[][] DATA = { 
                // Africa
                { "ALGERIA","Algiers"}, { "ANGOLA","Luanda"},
                { "BENIN","Porto-Novo"}, { "BOTSWANA","Gaberone"},
                { "BURKINA FASO","Ouagadougou"},
        };
        // Use AbstractMap by implementing entrySet()
        private static class FlyweightMap extends AbstractMap<String,String> { 
            private static class Entry implements Map.Entry<String,String> { 
                int index;
                Entry(int index) {  this.index = index; }
                public boolean equals(Object o) { 
                    return DATA[index][0].equals(o);
                }
                public String getKey() {  return DATA[index][0]; }
                public String getValue() {  return DATA[index][1]; }
                public String setValue(String value) { 
                    throw new UnsupportedOperationException();
                }
                public int hashCode() { 
                    return DATA[index][0].hashCode();
                }
            }
            // Use AbstractSet by implementing size() & iterator()
            static class EntrySet extends AbstractSet<Map.Entry<String,String>> { 
                private int size;
                EntrySet(int size) { 
                    if(size < 0)
                        this.size = 0;
                        // Can't be any bigger than the array:
                    else if(size > DATA.length)
                        this.size = DATA.length;
                    else
                        this.size = size;
                }
                public int size() {  return size; }
                private class Iter implements Iterator<Map.Entry<String,String>> { 
                    // Only one Entry object per Iterator:
                    private Entry entry = new Entry(-1);
                    public boolean hasNext() { 
                        return entry.index < size - 1;
                    }
                    public Map.Entry<String,String> next() { 
                        entry.index++;
                        return entry;
                    }
                    public void remove() { 
                        throw new UnsupportedOperationException();
                    }
                }
                public Iterator<Map.Entry<String,String>> iterator() { 
                    return new Iter();
                }
            }
            private static Set<Map.Entry<String,String>> entries = new EntrySet(DATA.length);
            public Set<Map.Entry<String,String>> entrySet() { 
                return entries;
            }
        }
        // Create a partial map of 'size' countries:
        static Map<String,String> select(final int size) { 
            return new FlyweightMap() { 
                public Set<Map.Entry<String,String>> entrySet() { 
                    return new EntrySet(size);
                }
            };
        }
        static Map<String,String> map = new FlyweightMap();
        public static Map<String,String> capitals() { 
            return map; // The entire map
        }
        public static Map<String,String> capitals(int size) { 
            return select(size); // A partial map
        }
        static List<String> names = new ArrayList<String>(map.keySet());
        // All the names:
        public static List<String> names() {  return names; }
        // A partial list:
        public static List<String> names(int size) { 
            return new ArrayList<String>(select(size).keySet());
        }
        public static void main(String[] args) { 
            System.out.println(capitals(10));
            System.out.println(names(10));
            System.out.println(new HashMap<String,String>(capitals(3)));
            System.out.println(new LinkedHashMap<String,String>(capitals(3)));
            System.out.println(new TreeMap<String,String>(capitals(3)));
            System.out.println(new Hashtable<String,String>(capitals(3)));
            System.out.println(new HashSet<String>(names(6)));
            System.out.println(new LinkedHashSet<String>(names(6)));
            System.out.println(new TreeSet<String>(names(6)));
            System.out.println(new ArrayList<String>(names(6)));
            System.out.println(new LinkedList<String>(names(6)));
            System.out.println(capitals().get("BENIN"));
        }
    } /* Output: {ALGERIA=Algiers, ANGOLA=Luanda, BENIN=Porto-Novo, BOTSWANA=Gaberone, BURKINA FASO=Ouagadougou} [ALGERIA, ANGOLA, BENIN, BOTSWANA, BURKINA FASO] {BENIN=Porto-Novo, ANGOLA=Luanda, ALGERIA=Algiers} {ALGERIA=Algiers, ANGOLA=Luanda, BENIN=Porto-Novo} {ALGERIA=Algiers, ANGOLA=Luanda, BENIN=Porto-Novo} {ALGERIA=Algiers, ANGOLA=Luanda, BENIN=Porto-Novo} [BENIN, BOTSWANA, ANGOLA, BURKINA FASO, ALGERIA] [ALGERIA, ANGOLA, BENIN, BOTSWANA, BURKINA FASO] [ALGERIA, ANGOLA, BENIN, BOTSWANA, BURKINA FASO] [ALGERIA, ANGOLA, BENIN, BOTSWANA, BURKINA FASO] [ALGERIA, ANGOLA, BENIN, BOTSWANA, BURKINA FASO] Porto-Novo *///:~

*  Countries类的静态变量`DATA`，作为实现的Map的真正数据存储。它作为一个二维数组，每个一维数组的长度都为2，0元素作为key，1元素作为value。
 *  `FlyweightMap`就是本例实现的Map的名字，它作为一个静态内部类放在Countries类里面，且继承了抽象类`extends AbstractMap<String,String>`，而且你会发现实现一个Map很简单，只需要你实现`entrySet()`就够了。类似的，实现一个Set也很简单，只需要实现`size() & iterator()`就行，正如`FlyweightMap`里面的`EntrySet`静态内部类。
 *  `FlyweightMap`为了实现`entrySet()`（其在Map.java接口里的签名为`Set<Map.Entry<K, V>> entrySet();`），在Countries类定义中定义了静态内部类`EntrySet`，其继承了`AbstractSet<Map.Entry<String,String>>`，刚好可以向上转型为`Set<Map.Entry<K, V>>`。但`Map.Entry`是一个接口，需要有具体的实现类，所以在Countries类定义中又定义了静态内部类`Entry`，其实现了`Map.Entry<String,String>`。
 *  `EntrySet`现在需要`size() & iterator()`。它继承了`AbstractSet<Map.Entry<String,String>>`。通过成员变量size和构造器，实现了`size()`。`iterator()`的签名为`Iterator<E> iterator();`，`EntrySet`中定义了一个成员内部类`Iter`实现了`Iterator<Map.Entry<String,String>>`，之所以是成员内部类，是因为set的迭代器必然应该持有外部类set的引用，换句话说，产生一个迭代器之前必然已经有了一个set对象。`iterator()`的方法实现逻辑也很合理，`return new Iter();`，这样每次都会新的迭代器对象，它们持有同一个外部类set对象的引用。

按照上面理清的思路，我们按照具体源码来分析：

private static class Entry implements Map.Entry<String,String> { 
                int index;
                Entry(int index) {  this.index = index; }
                public boolean equals(Object o) { 
                    return DATA[index][0].equals(o);
                }
                public String getKey() {  return DATA[index][0]; }
                public String getValue() {  return DATA[index][1]; }
                public String setValue(String value) { 
                    throw new UnsupportedOperationException();
                }
                public int hashCode() { 
                    return DATA[index][0].hashCode();
                }
            }

`Map.Entry`接口需要实现的接口很多。虽然`Entry`类必须要表现出key和对应的value，但上面的实现来看，`Entry`类并没有真正存储key的数据和value的数据，它只是保存了一个index，进而能从静态变量`DATA`中得到数据，这就体现了享元设计模式。对于`setValue`方法，由于不希望key对应的value被改变，所以这里没有实现，直接抛出`UnsupportedOperationException`。

private class Iter implements Iterator<Map.Entry<String,String>> { 
                    // Only one Entry object per Iterator:
                    private Entry entry = new Entry(-1);
                    public boolean hasNext() { 
                        return entry.index < size - 1;
                    }
                    public Map.Entry<String,String> next() { 
                        entry.index++;
                        return entry;
                    }
                    public void remove() { 
                        throw new UnsupportedOperationException();
                    }
                }
                public Iterator<Map.Entry<String,String>> iterator() { 
                    return new Iter();
                }

有了之前实现好的`Entry`类，这里就可以直接使用了。`Iter`类拥有一个`Entry`对象，作为迭代器访问数据的视图，而且`Entry`对象的index成员总是会被初始化为-1，这是合理的，观察`hasNext()`的逻辑，访问了外部类对象的size成员（因为`Iter`类是成员内部类才可以），当外部类set的长度size为0时，size - 1为-1，这样就算是初始的迭代器的`hasNext()`也会返回false。当外部类set的长度size为1时，size - 1为0，这样迭代器第一次判断`hasNext()`时能返回true，但迭代器`next()`后，就只能返回false了。

`next()`的实现逻辑也很简单，只需要让`entry.index++`就可以了，这样就能代表迭代器往后移动了。

定义好`Iter`类也是为了实现`iterator()`方法。

static class EntrySet extends AbstractSet<Map.Entry<String,String>> { 
    			//省略
            }
            private static Set<Map.Entry<String,String>> entries = new EntrySet(DATA.length);
            public Set<Map.Entry<String,String>> entrySet() { 
                return entries;
            }

定义好`EntrySet`类也是为了实现`entrySet()`方法，只是这里通过返回一个静态变量来实现。

// Create a partial map of 'size' countries:
        static Map<String,String> select(final int size) { 
            return new FlyweightMap() { 
                public Set<Map.Entry<String,String>> entrySet() { 
                    return new EntrySet(size);//这里不需写成FlyweightMap.EntrySet()
                }
            };
        }

select方法可以返回一个只有部分数据的Map。创建了FlyweightMap的匿名内部类，并且override了`entrySet()`方法，通过形参size传递给`EntrySet`的构造器，达到目的。注意调用`EntrySet`的构造器，不需要写成`FlyweightMap.EntrySet()`，因为匿名内部类本质就是继承，而继承后`EntrySet`作为`FlyweightMap`的静态内部类，当然也是属于`FlyweightMap`的静态成员了，所以这里就直接访问了父类`FlyweightMap`的静态成员了（这里是直接访问了静态成员的构造器）。

public class test { 
        static class A { 
            void doSomething() { }
            static class B { }
        }
    
        static void select() { 
            //new B();//编译错误
            new A.B();
        }
    
        static void select1() { 
            new A() { 
                @Override
                void doSomething() { 
                    new B();//继承了A，就可以直接使用父类A的静态成员B了，只不过B是一个静态内部类
                }
            };
        }
    }

上面这个例子可以解释“调用`EntrySet`的构造器，不需要写成`FlyweightMap.EntrySet()`”的原因。

System.out.println(new HashMap<String,String>(capitals(3)));

capitals方法也会返回一个FlyweightMap对象，但这里会调用到HashMap的构造器：

//HashMap.java
        public HashMap(Map<? extends K, ? extends V> m) { 
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            putMapEntries(m, false);
        }
        
        final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { 
            int s = m.size();
            if (s > 0) { 
                if (table == null) {  // pre-size
                    float ft = ((float)s / loadFactor) + 1.0F;
                    int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                             (int)ft : MAXIMUM_CAPACITY);
                    if (t > threshold)
                        threshold = tableSizeFor(t);
                }
                else if (s > threshold)
                    resize();
                for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { 
                    K key = e.getKey();
                    V value = e.getValue();
                    putVal(hash(key), key, value, false, evict);//这里会把传入的map的键值对放入新构造的HashMap里
                }
            }
        }

# 分析AbstractMap的keySet()方法 #

前面已经讲过，`FlyweightMap`继承`AbstractMap<String,String>`后只需要实现`entrySet()`方法，同样，`EntrySet`继承`AbstractSet<Map.Entry<String,String>>`后只需要实现`size() & iterator()`方法。之所以我们需要实现的地方这么少，是因为`AbstractXXX`抽象类已经帮我们实现了许多方法，比如`AbstractMap`抽象类里面就已经实现了`Map`接口里的很多方法，同样，`AbstractSet`抽象类里面也已经实现了`Set`接口里的很多方法。

static List<String> names = new ArrayList<String>(map.keySet());

很明显，本文的代码并没有实现`keySet()`方法，实际上它的实现已经在`AbstractMap`里写好了：

//AbstractMap.java file
    //省略
        transient Set<K>        keySet;
        transient Collection<V> values;
        
        public Set<K> keySet() { 
            Set<K> ks = keySet;
            if (ks == null) { 
                ks = new AbstractSet<K>() { 
                    public Iterator<K> iterator() { 
                        return new Iterator<K>() { 
                            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();
                            }
                        };
                    }
    
                    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;
        }
    //省略

*  首先这里设计成了一种单例模式，`keySet()`方法返回是一个`AbstractSet`的匿名内部类，这个匿名内部类是持有着外部类map对象的引用的，这样保证了一个map只对应一个key的set。
 *  `AbstractSet`的匿名内部类需要重写实现`iterator()`方法，方法内部则是返回一个`Iterator`的匿名内部类，它也是持有了外部类对象的引用的，所以这里，它直接调用了`entrySet()`方法，这是它的外部类对象（`AbstractSet`的匿名内部类）的外部类对象（外部类map对象）的方法。
 *  观察`Iterator`的匿名内部类的实现，它有一个成员也是迭代器，而且是`entrySet()`的迭代器，有了`entrySet()`的迭代器后，它自己的方法实现都全靠自己的迭代器成员了。有点像装饰器模式，因为成员本来是entry的迭代器，但包装以后变成了key的迭代器。
 *  除了`iterator()`方法外，`size()`方法也是必须要实现的。`return AbstractMap.this.size();`，原来是调用持有的外部类map对象的`size()`方法，它的实现就在AbstractMap的源码里：`public int size() { return entrySet().size(); }`。好家伙，和`iterator()`方法一样，原来`size()`方法的实现也是依靠了`entrySet()`方法的返回值的。
 *  从上面分析看来，`size() & iterator()`方法的重写实现，都是依靠了外部类对象的`entrySet()`方法返回的entryset，但`entrySet()`方法在`AbstractMap`里面并没有实现，它需要被`AbstractMap`的使用者来实现。
 *  之前说过继承`AbstractSet<Map.Entry<String,String>>`后只需要实现`size() & iterator()`方法，但源码里还有另外三个方法也重写实现了。这三个方法本来不是必须实现的，因为`AbstractCollection`里面已经有实现。
 *  `isEmpty()`方法重写实现了，实现逻辑是`return AbstractMap.this.isEmpty()`，调用的外部类对象的方法，从`AbstractMap`源码里找到该方法的实现：`public boolean isEmpty() { return size() == 0; }`，此时调用的层次已经到了`AbstractMap`，从`AbstractMap`源码里找到`size()`方法的实现：`public int size() { return entrySet().size(); }`。所以这里也是依靠了`entrySet()`方法的返回值的。
 *  这里如果不重写`isEmpty()`方法，由于`AbstractSet`继承了`AbstractCollection`，那么`isEmpty()`方法的实现就在继承的`AbstractCollection`里面：`public boolean isEmpty() { return size() == 0; }`，这样的话调用的是`AbstractSet`重写的`size()`方法，不过最终都会调用到`AbstractMap`子类实现的`entrySet()`方法。重不重写`isEmpty()`方法这两种情况的调用过程如下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70]
 *  从上图可以看出，重不重写`isEmpty()`方法最终调用的方法都是`AbstractMap`子类实现的`entrySet()`方法，绿色虚线下的调用过程两种情况都是一样的了，但重写了`isEmpty()`方法后，能让调用链更早地调用到外部类的实现上（注意红色字）。我觉得之所以要重写，是因为keyset的设计逻辑只是作为entryset的一种视图，最终实现还是得依赖于entryset，既然最终实现都是来自于`AbstractMap`子类实现的`entrySet()`方法，那么更早地调用到外部类的方法上也是更合理的。
 *  `clear()`方法也重写实现了，实现逻辑是`AbstractMap.this.clear()`，调用的外部类对象的方法，从`AbstractMap`源码里找到该方法的实现：`public void clear() { entrySet().clear(); }`，原来是直接调用`entrySet()`的clear方法。这里如果不重写`clear()`方法，由于`AbstractSet`继承了`AbstractCollection`，那么`clear()`方法的实现就在继承的`AbstractCollection`里面：

public void clear() { 
            Iterator<E> it = iterator();
            while (it.hasNext()) { 
                it.next();
                it.remove();
            }
        }

*  那么直接调用`entrySet()`的clear方法到底是什么样的实现呢，从本文例子代码里可以看到静态内部类`EntrySet`继承`AbstractSet`时只重写了`size() & iterator()`方法，所以其实`entrySet()`的clear方法就是`AbstractCollection`里面clear方法。
 *  `clear()`方法重写和不重写这两种情况，最终调用的clear都是entryset的clear（1.重写时，直接用entry了，`public void clear() { entrySet().clear(); }`；2.不重写时，第一句`Iterator<E> it = iterator()`，由于`iterator()`已经重写，那么`iterator()`会返回keyset的迭代器，然而keyset的迭代器是通过包装entryset的迭代器来的，所以实际也是调用entryset的clear）。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 1]
 *  `contains()`方法也重写实现了，实现逻辑是`return AbstractMap.this.containsKey(k)`，调用的外部类对象的方法，从`AbstractMap`源码里找到该方法的实现。其内部实现主要依靠了`entrySet()`的迭代器。

public boolean containsKey(Object key) { 
            Iterator<Map.Entry<K,V>> i = entrySet().iterator();
            if (key==null) { 
                while (i.hasNext()) { 
                    Entry<K,V> e = i.next();
                    if (e.getKey()==null)
                        return true;
                }
            } else { 
                while (i.hasNext()) { 
                    Entry<K,V> e = i.next();
                    if (key.equals(e.getKey()))
                        return true;
                }
            }
            return false;
        }

*  这里如果不重写`contains()`方法，由于`AbstractSet`继承了`AbstractCollection`，那么`contains()`方法的实现就在继承的`AbstractCollection`里面。里面调用了`iterator()`，由于`iterator()`之前已经重写过了（返回针对于key的迭代器，区别只是key的迭代器在取值时多执行了句`getKey()`），那么不重写`contains()`方法的情况调用`contains()`方法也能返回正确的结果。

public boolean contains(Object o) { 
            Iterator<E> it = iterator();
            if (o==null) { 
                while (it.hasNext())
                    if (it.next()==null)
                        return true;
            } else { 
                while (it.hasNext())
                    if (o.equals(it.next()))
                        return true;
            }
            return false;
        }

# 分析总结 #

*  从上面分析可以看出，`keySet()`方法里面的`AbstractSet`匿名内部类，除了必须实现的`size() & iterator()`方法，其实另外三个方法不需要重写也能得到同样的效果。
 *  但keySet只是被设计成EntrySet的一种视图，keySet的方法实现都依赖于对EntrySet的调用。所以对另外三个方法`isEmpty() & clear() & contains()`的重写可以让“keySet只是EntrySet的一种视图”这个逻辑更加清晰，让这三个方法也直接依赖于EntrySet。
 *  但不重写也能达到相同效果是建立在AbstractMap的实现逻辑和AbstractCollection实现逻辑一样的条件上的（因为不重写就会调用到继承于AbstractCollection的实现），如果实现逻辑都不一样，而且因为keySet的方法实现都应该依赖于外部类map对象的实现，所以这里**必须重写`isEmpty() & clear() & contains()`，且重写后的逻辑必须是直接调用到外部类map对象的实现**。
 *  `keySet()`方法的逻辑和成员`transient Set<K> keySet;`配合使用，使得keySet这个set对象成为一种**单例模式**。
 *  重写的`iterator()`方法里面的`Iterator`的匿名内部类，用到了**装饰器模式**，这个`Iterator`的匿名内部类继承了`Iterator`的同时，还拥有一个`Iterator`类型的成员，而且所有方法实现都依赖于这个成员。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191110112254295.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191110131027940.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FubGlhbjUyMw==,size_16,color_FFFFFF,t_70