如何正确实现Map的entrySet方法

如何正确实现Map的entrySet方法

看来你是准备自己实现 map了 ,


不烦参考下 jdk  hashmap 是怎么实现  java.util.HashMap.entrySet() 的 




  public Set> entrySet() {
return entrySet0();
    }
    private Set> entrySet0() {
        Set> es = entrySet;
        return es != null ? es : (entrySet = new EntrySet());
    }
    private final class EntrySet extends AbstractSet> {
        public Iterator> iterator() {
            return newEntryIterator();
        }
        public boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry) o;
            Entry candidate = getEntry(e.getKey());
            return candidate != null && candidate.equals(e);
        }
        public boolean remove(Object o) {
            return removeMapping(o) != null;
        }
        public int size() {
            return size;
        }
        public void clear() {
            HashMap.this.clear();
        }
    } 






通过继承AbstractMap我们可以很容易实现自己的Map，我们只需要实现唯一的抽象的entrySet()方法。以下是来自《Jav编程思想》(第四版第17章的例子)，继承AbstractMap实现了自己的SlowMap。另外还应该注意，如果要创建自己的Map，还必须同时定义Map.Entry的实现。
 
总结起来实现自定义Map需要以下两个步骤：
1.    继承AbstractMap需要实现entrySet()方法
2.    实现自己的Map.Entry
 
//: containers/MapEntry.java  
// A simple Map.Entry for sample Map implementations.  
import java.util.*;  
  
public class MapEntry implements Map.Entry {  
  private K key;  
  private V value;  
  public MapEntry(K key, V value) {  
    this.key = key;  
    this.value = value;  
  }  
  public K getKey() { return key; }  
  public V getValue() { return value; }  
  public V setValue(V v) {  
    V result = value;  
    value = v;  
    return result;  
  }  
  public int hashCode() {  
    return (key==null ? 0 : key.hashCode()) ^  
      (value==null ? 0 : value.hashCode());  
  }  
  public boolean equals(Object o) {  
    if(!(o instanceof MapEntry)) return false;  
    MapEntry me = (MapEntry)o;  
    return  
      (key == null ?  
       me.getKey() == null : key.equals(me.getKey())) &&  
      (value == null ?  
       me.getValue()== null : value.equals(me.getValue()));  
  }  
  public String toString() { return key + "=" + value; }  
} ///:~  
  
  
  
//: containers/SlowMap.java  
// A Map implemented with ArrayLists.  
import java.util.*;  
import net.mindview.util.*;  
  
public class SlowMap extends AbstractMap {  
  private List keys = new ArrayList();  
  private List values = new ArrayList();  
  public V put(K key, V value) {  
    V oldValue = get(key); // The old value or null  
    if(!keys.contains(key)) {  
      keys.add(key);  
      values.add(value);  
    } else  
      values.set(keys.indexOf(key), value);  
    return oldValue;  
  }  
  public V get(Object key) { // key is type Object, not K  
    if(!keys.contains(key))  
      return null;  
    return values.get(keys.indexOf(key));  
  }  
  public Set> entrySet() {  
    Set> set= new HashSet>();  
    Iterator ki = keys.iterator();  
    Iterator vi = values.iterator();  
    while(ki.hasNext())  
      set.add(new MapEntry(ki.next(), vi.next()));  
    return set;  
  }  
  public static void main(String[] args) {  
    SlowMap m= new SlowMap();  
    m.putAll(Countries.capitals(15));  
    System.out.println(m);  
    System.out.println(m.get("BULGARIA"));  
    System.out.println(m.entrySet());  
  }  
} //:~ 以上是一个参考实现。这个解决方案看起来很简单并且没什么问题，但这并不是一个恰当的实现。主要问题是它创建了键和值的副本。entrySet()的恰当实现应该在Map中提供视图，而不是副本，并且这个视图允许对原始的映射表进行修改，而副本则不行。
 
可以参考源码来学习正确的entrySet()应该如何实现。首先先看Map中entrySet()的声明
public interface Map {  
      
    Set> entrySet();  
}注释文档明确指出，entrySet()返回的Set应该是Map所代表的映射表的一个View。对Map的修改应该会反映到这个Set，反过来对这个Set的修改也会反映到Map。特别地，当在这个Set上进行迭代的过程中，如果修改了Map(除非是通过这个Set的迭代器进行remov()e或setValue()操作)，那么迭代过程产生的结果是不确定的。 
 
再看HashMap中entrySet()方法的实现
public Set> entrySet() {  
urn entrySet0();  
}  
  
private Set> entrySet0() {  
    Set> es = entrySet;  
    return es != null ? es : (entrySet = new EntrySet());  
}  
  
private final class EntrySet extends AbstractSet> {  
    public Iterator> iterator() {  
        return newEntryIterator();  
    }  
    public boolean contains(Object o) {  
        if (!(o instanceof Map.Entry))  
            return false;  
        Map.Entry e = (Map.Entry) o;  
        Entry candidate = getEntry(e.getKey());  
        return candidate != null && candidate.equals(e);  
    }  
    public boolean remove(Object o) {  
        return removeMapping(o) != null;  
    }  
    public int size() {  
        return size;  
    }  
    public void clear() {  
        HashMap.this.clear();  
    }  
} EntrySet是HashMap的一个内部类，它继承自AbstractSet，必须需要实现iterator()和size()两个抽象方法。而HashMap的entrySet()不过是返回了EntrySet的一个实例。
注意，与我们之前定义的SlowMap的entrySet()相比，这里的entrySet()实现中没有进行任何创建副本的操作。不难发现，remove()和clear()等方法，最终会调用到EntrySet所在的外部对象(即一个HashMap实例)的相关方法，从而实现对Map的修改应该会反映到这个Set，反过来对这个Set的修改也会反映到Map。当然，除了直接在entrySet()方法返回的Set对象上直接进行操作，还可以获取这个Set的迭代器，通过迭代器来修改Map和对应的Set。这类修改，同样也应当需要实现对Map的修改应该会反映到这个Set，反过来对这个Set的修改也会反映到Map。这里涉及到HashMap.EntryIterator类，内容较多，后面接着分析