Chapter 17 - Exercise 25

(6) Instead of using a Listlterator for each bucket, modify MapEntry so that it is a self-contained singly linked list (each MapEntry should have a forward link to the next MapEntry). Modify the rest of the code in SimpleHashMap.java so that this new approach works correctly.


这题的关键是:为了更好地定义AbstractMap的行为,Map接口的entrySet()是明确面向Set的。其他方法可以直接面向内部定义的Set类实例的。而内部定义的Set和Entry功能可以比Set接口和Map.Entry接口强很多。

这题保留了两个版本。

版本1

版本2。没有用数组做组件,而是直接用LinkedSet。这样更简便直接,省去了从数组转到LinkedSet的麻烦。

Exercise25.java


package com.ciaoshen.thinkinjava.newchapter17;
import java.util.*;

public class Exercise25 {
    private static class LinkedMap<K,V> extends AbstractMap<K,V> {
        private LinkedSet nodeSet = new LinkedSet();
        // 只有entrySet()是面向Set<Map.Entry<K,V>>接口的。
        public Set<Map.Entry<K,V>> entrySet() { return nodeSet; }
        // 其他所有方法都可以直接面向功能更强大的LinkedSet。
        public V put(K k,V v) {
            return nodeSet.put(new Node<K,V>(k,v));
        }
        private static class Node<K,V> implements Map.Entry<K,V> { // no visitor for "next" field
            private K key;
            private V value;
            private Node<K,V> next;
            private Node() {}
            private Node(K k, V v) {
                key = k;
                value = v;
                next = null;
            }
            public K getKey() {
                return key;
            }
            public V getValue() {
                return value;
            }
            public V setValue(V v) {
                V oldValue = value;
                value = v;
                return oldValue;
            }
            public boolean equals(Object o) { // only compare key
                if (o == this) { return true; }
                if ( ! ( o instanceof Node ) ) {
                    return false;
                }
                @SuppressWarnings({"rawtypes","unchecked"})
                Node<K,V> n = (Node)o;
                return n.key.equals(key);
            }
            public int hashCode() { // only calculate key
                return 31 * 17 + key.hashCode();
            }
            public String toString() {
                return "N[" + key + "," + value + "]";
            }
        }
        /**
         *  Map.Entry<K,V>接口太弱,不支持链表操作。
         * 但又不能用上界通配符<? extends Map.Entry<K,V>>来泛化接口匹配范围,
         * 因为根据PECP原则,上界通配符细化粒度以后,LinkedSet无法插入元素,add()方法无法执行。
         * 这里的解决方案是:
         *      LinkedList不支持add()方法,新增一个支持链表操作的put()方法。
         */
        private class LinkedSet extends AbstractSet<Map.Entry<K,V>> {
            private Node<K,V> head = new Node<K,V>();
            private int size;
            public int size() { return size; }
            public Iterator<Map.Entry<K,V>> iterator() {
                return new Iterator<Map.Entry<K,V>>() {
                    private Node<K,V> cursor = head; // last node returned by next() method
                    private Node<K,V> previous = cursor; // previous node of last Node returned by next()
                    public boolean hasNext() {
                        return cursor.next != null;
                    }
                    public Map.Entry<K,V> next() {
                        if (cursor.next == null) {
                            throw new NoSuchElementException();
                        }
                        Node<K,V> next = cursor.next;
                        previous = cursor;
                        cursor = next;
                        return next;
                    }
                    public void remove() {
                        if (cursor == previous) {
                            throw new IllegalStateException();
                        }
                        previous.next = cursor.next;
                        cursor.next = null;
                        cursor = previous;
                        size--;
                    }
                };
            }
            // Set<Map.Entry<K,V>>接口的add()方法太弱,必须接受Map.Entry<K,V>接口的参数。
            // 不支持链表操作,所以废弃。
            public boolean add(Map.Entry<K,V> node) {
                throw new UnsupportedOperationException("add() method of Set interface is too weak!");
            }
            // 面向Node<K,V>的put()方法,是add()方法的增强版。支持链表操作。
            public V put(Node<K,V> node) {
                V result = null;
                Iterator<Map.Entry<K,V>> ite = iterator();
                while (ite.hasNext()) {
                    Map.Entry<K,V> entry = ite.next();
                    if (node.equals(entry)) { // replace = remove + addFirst
                        ite.remove();
                        result = entry.getValue();
                    }
                }
                node.next = head.next;
                head.next = node;
                size++;
                return result;
            }
        }
    }
    public static void main(String[] args) {
        int max = 128;
        int min = 32;
        int size = 10;
        Random r = new Random();
        Map<Integer,Character> ascii = new LinkedMap<>();
        for (int i = 0; i < size; i++) {
            int index = r.nextInt(max-min) + min;
            ascii.put(index,(char)index);
        }
        System.out.println(ascii);
        loopAsciiRange:
        for (int i = 0; i < max; i++) { // remove the smallest element
            if (ascii.containsKey(i)) {
                ascii.remove(i);
                System.out.println(new LinkedMap.Node<Integer,Character>(i,(char)i) + " is removed!");
                break loopAsciiRange;
            }
        }
        System.out.println(ascii);
    }
}


版本2

很早之前第一遍做习题时候的解法。用了数组做内部组件。

LinkedMapEntryV2.java

带指向下一个节点指针的(类单向链表)Map.Entry节点,不需要完整地实现LinkedList的全部功能,甚至不需要实现Iterator接口内部类。只需要提供几个简单的访问next节点的方法就可以了。



package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;

public class LinkedMapEntryV2<K,V> implements Map.Entry<K,V> {
    private K key;
    private V value;
    private LinkedMapEntryV2<K,V> next;
    public LinkedMapEntryV2(){
        key=null;
        value=null;
        next=null;
    }
    public LinkedMapEntryV2(K key, V value) {
        this.key = key;
        this.value = value;
        next=null;
    }
    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());
    }
    @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; }

	/**
	 *	需要的三个简单的对next节点的访问方法。
	 */
    public boolean hasNext(){return next==null;}
    public LinkedMapEntryV2<K,V> next(){return next;}
    public void setNext(LinkedMapEntryV2<K,V> entry){next=entry;}
}


SimpleHashMap25V2.java


package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;

public class SimpleHashMap25V2<K,V> extends AbstractMap<K,V> {

    static final int SIZE = 997;
    @SuppressWarnings(value={"unchecked","rawtypes"})
    LinkedMapEntryV2<K,V>[] buckets = new LinkedMapEntryV2[SIZE];

    public V put(K key, V value) {
        V oldValue = null;
        int index = Math.abs(key.hashCode()) % SIZE;
        if(buckets[index] == null){
            buckets[index] = new LinkedMapEntryV2<K,V>(key,value);
            return null;
        }
        LinkedMapEntryV2<K,V> cursor = buckets[index];
        while(true) {
            if(cursor.getKey().equals(key)){
                oldValue=cursor.getValue();
                cursor.setValue(value);
                break;
            }
            if(cursor.hasNext()){
                cursor=cursor.next();
            }else{
                cursor.setNext(new LinkedMapEntryV2<K,V>(key,value));
            }
        }
        return oldValue;
    }

    public V get(Object key) {
        int index = Math.abs(key.hashCode()) % SIZE;

        if(buckets[index] == null){return null;}

        LinkedMapEntryV2<K,V> cursor = buckets[index];
        while(cursor!=null) {
            if(cursor.getKey().equals(key)){
                return cursor.getValue();
            }
            cursor=cursor.next();
        }
        return null;
    }

    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> set= new HashSet<Map.Entry<K,V>>();
        for(LinkedMapEntryV2<K,V> cursor : buckets) {
            if(cursor!=null){
                set.add(cursor);
            }
        }
        return set;
    }

    public static void main(String[] args) {
        SimpleHashMap25V2<String,String> m = new SimpleHashMap25V2<String,String>();
        m.putAll(Countries.capitals(25));
        System.out.println(m);
        System.out.println(m.get("ERITREA"));
        System.out.println(m.entrySet());
    }
}


Maps.java


package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import java.io.*;

public class Maps {
    public static void printKeys(Map<Integer,String> map) {
        System.out.print("Size = " + map.size() + ", ");
        System.out.print("Keys: ");
        System.out.println(map.keySet()); // Produce a Set of the keys
    }
    public static void test(Map<Integer,String> map) {
        System.out.println(map.getClass().getSimpleName());
        map.putAll(new CountingMapDataOrig(25));
        // Map has ‘Set’ behavior for keys:
        map.putAll(new CountingMapDataOrig(25));
        printKeys(map);
        // Producing a Collection of the values:
        System.out.print("Values: ");
        System.out.println(map.values());
        System.out.println(map);
        System.out.println("map.containsKey(11): " + map.containsKey(11));
        System.out.println("map.get(11): " + map.get(11));
        System.out.println("map.containsValue(\"F0\"): "
              + map.containsValue("F0"));
        Integer key = map.keySet().iterator().next();
        System.out.println("First key in map: " + key);
        map.remove(key);
        printKeys(map);
        map.clear();
        System.out.println("map.isEmpty(): " + map.isEmpty());
        map.putAll(new CountingMapData(25));
        // Operations on the Set change the Map:
        map.keySet().removeAll(map.keySet());
        System.out.println("map.isEmpty(): " + map.isEmpty());
    }
    public static void main(String[] args) {
    }
}


Exercise25.java


package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import java.io.*;

public class Exercise25{
    public static void main(String[] args){
        SimpleHashMap25V2<Integer,String> map=new SimpleHashMap25V2<Integer,String>();
        map.putAll(new CountingMapData(60));
        Maps.test(map);
    }
}



Need Java Developers? Hire Me »

I know Java. Talk is cheap, watch my code.

I live in CANADA now.