2016-10-19 00:26:14 +0000   |     java data structure view encapsulation   |   Viewed times   |    

我这里有一个山寨的Map,叫CopyMap。负责存储键-值对的是两个ArrayList。实现的原理很简单,继承了AbstractMap。然后实现了必要的put(),get()和entrySet()方法。

public class CopyMap<K,V> extends AbstractMap<K,V> {
    private List<K> keys = new ArrayList<K>();
    private List<V> values = new ArrayList<V>();
    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<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> set= new HashSet<Map.Entry<K,V>>();
        Iterator<K> ki = keys.iterator();
        Iterator<V> vi = values.iterator();
        while(ki.hasNext()){
            set.add(new MapEntry<K,V>(ki.next(), vi.next()));
        }
        return set;
    }
}

在entrySet()方法中,用到的MapEntry在另一个文件MapEntry.java中。实现了Map.Entry接口。

public class MapEntry<K,V> implements Map.Entry<K,V> {
    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 K setKey(K k) {
        K result = key;
        key = k;
        return result;
    }
    public int hashCode() {
        return (key==null ? 0 : key.hashCode()) ^
        (value==null ? 0 : value.hashCode());
    }
    @SuppressWarnings("rawtypes")
    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; }
}

按理说这个山寨Map虽然效率很低,但功能不应该有太大问题。但实际上,很简单的测试就发现很大的问题。

    public static void main(String[] args) {
        CopyMap<Integer,String> m= new CopyMap<Integer, String>();
        for(int i=50;i<70;i++){
            m.put(i, new String(new char[]{(char)i}));
        }
        System.out.println(m);
        System.out.println(m.entrySet());

        Integer key = m.keySet().iterator().next();
        System.out.println("Now I remove the first key in map: " + key);
        m.remove(key);
        System.out.println(m.entrySet());
    }

测试中,我们把整数50-70按顺序存入key列表。然后把这个数字在ASCII码表中对应的字符存入value列表。然后打印出整个Map。输出应该是按顺序打印出ASCII码表中第50-70号编码。然后再尝试删除Map中的首元素。

{52=4, 50=2, 63=?, 51=3, 53=5, 65=A, 68=D, 61==, 64=@, 54=6, 55=7, 56=8, 57=9, 58=:, 62=>, 66=B, 59=;, 67=C, 60=<, 69=E}
[55=7, 50=2, 51=3, 52=4, 53=5, 54=6, 56=8, 68=D, 57=9, 61==, 66=B, 67=C, 65=A, 63=?, 64=@, 58=:, 62=>, 59=;, 60=<, 69=E]
Now I remove the first key in map: 50
[52=4, 50=2, 51=3, 63=?, 53=5, 54=6, 69=E, 55=7, 56=8, 57=9, 58=:, 67=C, 59=;, 61==, 60=<, 62=>, 66=B, 68=D, 64=@, 65=A]

但测试结果打印的顺序很奇怪。包括entrySet()方法返回set之后打印的顺序也不一样。而且首元素也没有被删除。

这里的问题其实出在entrySet()方法里。因为它返回的set是一个CopyMap的HashSet“副本”。其中每个元素在堆区都是新对象,有一个全新的地址。而且通过插入HashSet,元素顺序也被打乱了。而且之后对CopyMap的任何操作都不会反馈到entrySet返回的set里。这就是为什么remove()方法看上去没有删除首元素的原因。

    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> set= new HashSet<Map.Entry<K,V>>();
        Iterator<K> ki = keys.iterator();
        Iterator<V> vi = values.iterator();
        while(ki.hasNext()){
            set.add(new MapEntry<K,V>(ki.next(), vi.next()));
        }
        return set;
    }

实际更合理的做法是通过Iterator提供一个Map本体的“视图”。也就是返回的元素必须指向Map中元素的原始地址。这样对Map的操作都能在视图中得到反馈。

实现“视图”的方法也很简单。下面这个ViewMap就是一个简单的例子。为entrySet()方法返回Set,创建了一个内部类EntrySet。在其中又定义了一个匿名内部迭代器,实现Iterator接口。这个迭代器不额外创建新对象,从头到尾只使用同一个Entry负责返回Map中元素的引用。相当于提供“视图”的一个“透镜”。

public class ViewMap<K,V> extends AbstractMap<K,V> {
    private List<K> keys = new ArrayList<K>();
    private List<V> values = new ArrayList<V>();
    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<Map.Entry<K,V>> entrySet() {
        return new EntrySet();
    }

    private class EntrySet extends AbstractSet<Map.Entry<K,V>>{
        public Iterator<Map.Entry<K,V>> iterator(){
            return new Iterator<Map.Entry<K,V>>(){
                private Iterator<K> iteKey=keys.iterator();
                private Iterator<V> iteValue=values.iterator();

                private MapEntry<K,V> entry=new MapEntry<K,V>(null,null);	//始终只有这一个entry。它就是提供“视图”的那个“透镜”。
                public boolean hasNext(){
                    return iteKey.hasNext() && iteValue.hasNext();
                }
                public Map.Entry<K,V> next(){
                    entry.setKey(iteKey.next());
                    entry.setValue(iteValue.next());
                    return entry;
                }
                public void remove(){
                    iteKey.remove();
                    iteValue.remove();
                }
            };
        }

        public int size(){return Math.min(keys.size(),values.size());}
    }
}

再做测试的时候一切正常:

{50=2, 51=3, 52=4, 53=5, 54=6, 55=7, 56=8, 57=9, 58=:, 59=;, 60=<, 61==, 62=>, 63=?, 64=@, 65=A, 66=B, 67=C, 68=D, 69=E}
[50=2, 51=3, 52=4, 53=5, 54=6, 55=7, 56=8, 57=9, 58=:, 59=;, 60=<, 61==, 62=>, 63=?, 64=@, 65=A, 66=B, 67=C, 68=D, 69=E]
Now I remove the first key in map: 50
[51=3, 52=4, 53=5, 54=6, 55=7, 56=8, 57=9, 58=:, 59=;, 60=<, 61==, 62=>, 63=?, 64=@, 65=A, 66=B, 67=C, 68=D, 69=E]

Java中因为不像C或C++这样区分值和指针,很容易忽略实际返回的是一份拷贝还是引用。但两者实际效果天差地别。

不过“视图”和“副本”不能简单地区分谁好谁坏,还是要看具体使用场景。相比“副本”,“视图”允许对原始数据进行修改。尤其是在并发的场景中,更需要注意。