2016-09-09 12:06:45 +0000   |     java thinking in java data structure container view iterator fly weight   |   Viewed times   |    

容器的填充

实现容器抽象类

例子是一个“享元模式(FlyWeight)”。顾名思义,Fly Weight,就是用在有大量对象的组件里,为了节省内存空间的大小。指导思想,就是把巨量的对象从代码中剥离出来,单独储存,供大家访问。

这里实现享元模式的动机就是要把Map里的数据从Map里分离出来。演示Map里如果没有实际数据,也是可以依靠外部数据源工作的。

当然现有的容器类不能和它兼容。需要重新构造专用容器。但也不需要完全重头开始造轮子。可以继承类库提供的容器抽象类。代码如下:

public class MyCountries {
    /**
     *  数据二维数组
     */
    public static final String[][] DATA = {
    // Africa
    {"ALGERIA","Algiers"}, {"ANGOLA","Luanda"},
    //一万个国家名和首都的pair... ...
    {"URUGUAY","Montevideo"}, {"VENEZUELA","Caracas"},
    };

    /**
     * 套嵌MAP
     * 实现 AbstractMap 要实现 entrySet()。因为AbstractMap没有实现Map接口定义的entrySet方法。
     */
    public static class CountriesMap extends AbstractMap<String,String>{

        /**
         * MAP内部二层套嵌类Entry 实现 Map.Entry 套嵌泛型类。这里为了支持享元,要重写两个方法:getKey()和getValue()。
         * 享元模式:Entry只要一个index字段。Entry所有内容根据这个index到享元里找。
         */
        public static class Entry implements Map.Entry<String,String>{
            private int index;
            public Entry(int index){
                this.index=index;
            }
            public String getKey(){return DATA[index%DATA.length][0];}
            public String getValue(){return DATA[index%DATA.length][1];}
            public boolean equals(Object o){return getKey()==((Entry)o).getKey();}
            public int hashCode(){return getValue().hashCode();}
            public String setValue(String value){
                throw new UnsupportedOperationException();  //只读,不支持改数据
            }
        }


        /**
         * 二层套嵌 Set
         * 实现只读 AbstractSet 要实现 size() & iterator()。 因为AbstractSet继承自AbstractCollection。但AbstractCollection中定义了size() & iterator()方法,但没有实现。
         * 享元模式:只保留一个size字段。Set的所有内容根据这个size从享元中找。
         */
        public static class EntrySet extends AbstractSet<Map.Entry<String,String>>{
            private int size;
            public EntrySet(){
                this.size=DATA.length;
            }
            public EntrySet(int size){
                if(size<0){
                    this.size=0;
                }else if(size>DATA.length){
                    this.size=DATA.length;
                }else{
                    this.size=size;
                }
            }
            public int size(){
                return size;
            }

            /**
             * Set 内部三层套嵌迭代器
             */
            private class EntryIterator implements Iterator<Map.Entry<String,String>>{
                private Entry e=new Entry(0);
                public boolean hasNext(){
                    return e.index<size-1;
                }
                public Map.Entry<String,String> next(){
                    e.index++;
                    return e;
                }
                public void remove(){
                    throw new UnsupportedOperationException();
                }
                public void reset(){e.index=0;}
            }

            public Iterator<Map.Entry<String,String>> iterator(){
                return new EntryIterator();
            }

        }

        //定义好了套嵌Set之后,写entrySet()方法
        public Set<Map.Entry<String,String>> entrySet(){
            return new EntrySet(DATA.length);
        }

    }

    //神奇的匿名内部类,重写entrySet()方法。
    public static Map<String,String> select(final int size){
        return new CountriesMap(){
            @Override
            public Set<Map.Entry<String,String>> entrySet(){
                return new EntrySet(size);
            }
        };
    }


    //返回整个Map
    static Map<String,String> map=new CountriesMap();
    public static Map<String,String> capitals(){
        return map;
    }

    //返回部分Map
    public static Map<String,String> capitals(int size){
        return select(size);
    }

    //返回所有国家名的List
    public static List<String> names(){
        return new ArrayList<String>(map.keySet());
    }

    //返回部分国家名的List
    public static List<String> names(int size){
        return new ArrayList<String>(capitals(size).keySet());
    }
}
看看keySet( )方法的源代码,看它是怎么实现的

简单讲就是利用AbstractSet里的Iterator,逐个获取元素的Key键值。

    public Set<K> keySet() {
        if (keySet == null) {
            keySet = 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();
                        }
                    };
                }

                //AbstractSet接口的其他方法
				//... ...
            };
        }
        return keySet;
    }

这里用了一个代理模式,内部的委托类就是我们实现了的entrySet()方法和iterator()方法。

所以这这个Map实现地非常轻量级,仅仅是设置了一个到储存数据的二维数组的一个索引,就实现了对数据的查询功能。

用匿名内部类覆盖某方法,有奇效

内部类这一章,只注意到了匿名内部类的一种使用场景:实现某个interface。

但实际上匿名内部类的语法表达的是一个“继承”的概念。看select()方法的代码:

    //神奇的匿名内部类,重写entrySet()方法。
    public static Map<String,String> select(final int size){
        return new CountriesMap(){
            @Override
            public Set<Map.Entry<String,String>> entrySet(){
                return new EntrySet(size);
            }
        };
    }

这里“new CountriesMap()”表达的是:

这里仅仅是重写了entrySet()方法,就能够返回数据表不同大小的子块。这算是匿名内部类比较经典的应用场景了。

Collection接口

不多说,放张图,这几个方法是要记住的。总的来说,以一个List表为代表的一组容器,最典型的操作就这么几样:

这些都是经过时间检验的“工程经验”

collection

注意一下迭代器光标Cursor位置: cursor

可选操作

可选操作是个坑。它是指比如在Collection接口中,以下几个方法,

它们是可选方法。但仅仅是在官方文档的方法解释后面加了两个字“(optional operation)”而已。

它的实现方式非常隐蔽,当我们用“Arrays.asList()”方法把一个数组转换成一个List的时候,看起来返回的数据类型是ArrayList,但注意这不是java.util.ArrayList,而是Arrays内部一个同名的套嵌类java.util.Arrays.ArrayList。在这个“山寨”ArrayList里以上列出来的方法只是假装实现了一下,抛出一个UnsupportedOperationException而已。贴一下部分源代码:

下面是java.util.Arrays中套嵌ArrayList的代码开头部分。很明显,它继承自抽象类AbstractList

    private static class ArrayList<E> extends AbstractList<E>
        implements RandomAccess, java.io.Serializable
    {
        private static final long serialVersionUID = -2764017481108945198L;
        private final E[] a;

        ArrayList(E[] array) {
            if (array==null)
                throw new NullPointerException();
            a = array;
        }
		//... ...
		//... ...
	}

而抽象类AbstractList里,以上列出来的几个方法根本没有实现,只是抛出UnsupportedOperationException

    public void add(int index, E element) {
        throw new UnsupportedOperationException();
    }

    public E remove(int index) {
        throw new UnsupportedOperationException();
    }
	//... ...
	//... ...

可选操作是坑?还是良好的设计?

书上对此的解释是:

我表示,很难接受这样的解释。这真的很坑。要么索性就重新取个名字,干嘛要取一样的名字骗我们呢。网上都把这个错误列为《Java程序员们最常犯的10个错误》之首了好吗,真的不能原谅。

类似这样的“未获支持的操作”的坑,还有Collections.unmodifiableList()方法返回的Collection。除了以上列出来的方法,它还禁掉了一个List.set()方法,因为它返回的容器不仅仅是固定大小,还完全不能修改。

List<String> list = Arrays.asList("A B C D E F G H I J K L".split(" "));
Collections.unmodifiableList(new ArrayList<String>(list));

书上更深层的解释是:

因为上面两个例子,就省去了FixSizeList和UnmodifiableList两个接口。

AbstractCollection抽象类

翻一下AbstractCollection抽象类的源码。看到它是完全不依赖于任何数据而独立存在的。对它的简单描述应该是这样:

  1. 是个空壳,没有数据。
  2. 所有定义的操作全都指向一个假象的数据体。
  3. 操作和数据之间唯二的发生关系的途径是通过:get()size()两个方法。而这两个方法是抽象方法,留给用户自己定义。
  4. 大致的思路就是以size()为界,用Iterator遍历元素。然后假设get()方法能返回元素。能完成几乎所有读取,查找,转换操作。
  5. 然后写操作的add()方法是未定义操作UnsupportedOperationException。

所以AbstractCollection是完全没有实体的。

List

工程模型和Collection是一致的,操作也分成:读取元素,检查元素,改变元素,迭代器,类型转换,这几大类。不赘述。

需要注意:List有个更强大的迭代器ListIterator。 遍历能往前,往后,双向移动。还有写操作add(),set()。看下图, listIterator

单向链表设计思路

比较重要的几个点,方便以后回顾比较:

  1. 节点的数据结构很清楚:一部分放数据,一部分是指向下一个节点的指针。
  2. 个人比较喜欢:前后两个固定的头节点head和尾节点tail。只站桩,无数据。
  3. 其中,只有头节点是必须的。无头节点的话,对第一个元素的操作会和其他元素不同,代码复杂化。
  4. 尾节点可以没有。可以让最后一个元素指向null。加尾节点是为了在末尾插入新元素更高效。不然就得从head遍历到最后一个元素,再插入。
  5. head.next指向第一个节点,tail.next指向最后一个节点。当链表为空,head.next=tail。 tail.next=head。
  6. cursor光标表示上一个next()方法返回的节点。
  7. previous引用盯住cursor。表示cursor的前一个节点。为了remove()的时候能找到前一个节点的向后引用。
  8. 每一次调用next(),只能用remove()方法删除一次当前节点。删除完,光标退回上一节点。
  9. 只有两种情况,previous和cursor指向同一个节点:要么初始阶段还没有调用过next()。要么next()返回的上一个节点被remove()方法删掉。
  10. previous和cursor永远不可能指向tail。

关于LinkedList头节点的总结:

  1. 头节点是不储存元素信息的纯功能性节点。用来停放指针。
  2. 单纯从功能上讲,单个头节点head就够了。不需要尾节点。
  3. 没有head头节点的话,大部分操作对第一个元素和后续元素,实现都不同。导致逻辑复杂。容易出bug。编程目标是不出错,不是为了挑战脑力。
  4. 不需要专门的桩子尾节点。但需要一个tail指针,指向末尾元素,方便从末尾插入新元素。
  5. 双头节点版本:一个头节点head,一个尾节点tail。也没什么不好。反而逻辑清楚。
  6. JDK里的官方LinkedList是没有头节点的版本。不知道为什么。难道是节约内存?

Set

Set主要有两个点:

  1. 内部元素唯一性。
  2. 维持特定的元素排序。不同类型Set的排序方式不同。

其中:

  1. HashSet:以散列值对set容量取余后决定的下标。没有规律。
  2. TreeSet:保持降序。
  3. LinkedHashSet:保持插入顺序。

Set对内部元素的要求

希望放入Set中的元素类型必须先实现一些特定方法:

  1. 所有实现Set接口的类,都要求内部元素实现equals()方法。为了保证唯一性。
  2. HashSet系的还要实现hashCode()方法。
  3. 以TreeSet为代表的SortedSet系需要内部元素实现Comparable接口。也就是实现compareTo()方法。

没有实现特定方法,存到Set里就会乱套。但编译器不会报错。因为默认的equals()和hashCode()虽然是错的,但是能运行的。

自定义Set

可以继承AbstractSet抽象类。因为AbstractSet继承自AbstractCollection抽象类。加在一起,基本实现了Set接口。但有几个关键方法还需要自己定义:

比如下面是AbstractCollection里add()方法的源码。直接抛出异常。

    public boolean add(E e) {
        throw new UnsupportedOperationException();
    }

队列(Queue)

队列的基本特点就是:先进先出(FIFO)。队列,顾名思义。

PriorityQueue是维持特定排序的Queue。

双端队列(Deque)

Deque(Double End Queue)顾名思义,可以在头和尾两个方向实现Queue的抽插。

但Deque在实际工程中用的少。是因为现实生活中没有东西和这个模型对应。比如List对应“列表”。Set对应“集合”。Map对应“字典”。Queue对应“队列”。但没有什么东西需要从两段存取。

映射(Map)

都有哪些Map?贴一张图。 map

最常用的还是HashMap,效率最高。

自定义Map

自定义Map可以继承AbstractMap。但必须自己实现几个方法:

自定义Map的关键在于定义一个键值对的Pair:叫Map.Entry<K,V>的内部类接口。也可以用一个独立的类来实现这个接口。这个数据结构把Map里的一个“键-值”对捏合成单个元素。

然后定义一个“entrySet()”方法,返回一个Map.Entry元素的集合Set<Map.Entry<K,V>>mapEntry

Map接口的大多数方法,AbstractMap都实现了。但这个entrySet()方法是抽象方法,需要自己定义。因为,大多数的方法都是通过entrySet()方法把Map转换成Set来完成的。

public abstract Set<Entry<K,V>> entrySet();

实现etnrySet()的时候,返回的Set应该是原本Map的“视图”,不要返回“副本”。也就是直接返回Map内部数据的引用,而不是一份拷贝。要返回“视图”,可以返回一个没有实体数据,但带有一个Iterator的Set。具体实现,参见本章练习题16。

另外一个需要自己定义的方法是put()。下面是AbstractMap里put()方法的源代码,

    public V put(K key, V value) {
        throw new UnsupportedOperationException();
    }

唯一性

Map和Set的唯一性,由hashCode()equals()两个方法来判定。逻辑上不冲突,因为equals()判断为真的两个键值,hashCode()返回值必须相等。这是对hashCode()方法的基本设计要求。

下面是HashMap里put()方法的源码。

    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {	//注意这一行
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

注意if (e.hash == hash && ((k = e.key) == key || key.equals(k)))这个就是根据equal()和hashCode()两个函数返回值判定唯一性的判定语句。

另外,对equals()函数多说两句。判定值相等,虽然简单,但必须满足下面5个逻辑条件:

  1. 自反性。x=x必须为true。
  2. 对称性。如果x=y为true,y=x也必须返回true。
  3. 传递性。如果x=y,y=z。那么x=z必须返回true。
  4. 一致性。在x和y都没变的情况下。每次测试x=y必须返回一样的结果。
  5. 任何不是null的x。x.equals(null)必须返回false。

散列值(hashCode())

关于散列值,参见之前的一篇:《Java HashMap的哈希值是怎么计算的?》。 这里简单强调几个基本逻辑层次

  1. HashMap的基本理念是:通过对内部数组直接下标访问,做到get()普通情况O(1).
  2. 下标访问的原理:对key键值执行hashCode()函数,生成散列值(一般比较大),然后对内部数组大小取余运算,获得数组下标。
  3. hashCode()在Object根类就定义了。几乎每个类都重写了这个方法。
  4. 自己写hashCode()要符合两个基本逻辑:第一,同一个对象每次的散列值必须相等。第二,两个equals()判定值相等的对象,散列值也要相等。

简单容器测试框架

非常简单的一个模块化封装实践,主要记住思路:

  1. testframework.Test.java: 框架模块1:封装测试类
  2. testframework.TestParam.java: 框架模块2:封装测试参数。
  3. testframework.Tester.java: 框架模块3:运行测试工具包。
  4. testframework.gen.*: 框架模块4:模拟数据生成器包。

最终实现的功能是:

  1. 可以自定义扩展测试类(Test.java定义)。
  2. 给一种容器,和一个参数包,自动对容器执行不同参数的全套测试。

关于垃圾回收再唐僧几句

GC不是什么都管

GC只负责回收内存。那什么东西GC不负责回收?native方法开辟的资源,比如如native memory(DirectByteBuffer)、file(FileInputStream)之类,GC是不管的,必须自己关掉。所以常见的图形,IO都必须自己关。

finalize( )方法作为GC的补充

既然GC有些东西不管,那也要有办法释放。这可以用finalize()方法。GC在释放被复写finalize()方法的对象的时候,会先调用其finalize()方法。

finalize( )方法靠不住,不要用

GC在回收对象之前,是会先调用finalize()方法。但GC本身执行时机不确定。调用System.gc()方法只是“建议”系统进行垃圾回收,但具体执不执行,还是JVM说了算。说白了,我们对垃圾回收这件事,没有控制权。

而且,触发GC以后,执行finalize()方法,系统是交给Finalizer来做。而且Finalizer坐在另一个Finalizer Daemon Thread线程里。而且此线程优先级比主线程低得多。什么时候执行finalize()不确定。

具体,参考《JAVA虚引用为什么在重载finalize后不会被置入引用队列?》专题。

finalize( )只能被调用一次

任何对象的finalize()只能被调用一次。

引用的不同强度

关于弱引用方面不错的一篇文章: 《深入探讨 java.lang.ref 包》

四种不同强度reference的定义: 1.普通引用:没什么好说的。 2.软引用(SoftReference):系统资源紧张的时候,系统会删除软引用。优先删除长久没用的引用。 3.弱引用(WeakReference):GC的时候删除清理弱引用。 4.虚引用(PhantomReference):通过虚引用无法获得对象。

ReferenceQueue

当软引用,弱引用,虚引用被系统清除以后,如果绑定了ReferenceQueue,这些引用会被加入ReferenceQueue。

虚引用(PhantomReference)构造函数必须传入一个ReferenceQueue作为参数。

    public PhantomReference(T referent, ReferenceQueue<? super T> q) {
        super(referent, q);
    }

软引用和弱引用可以选择在构造函数传入ReferenceQueue或者不传入。

不同强度引用被加入ReferenceQueue的时机不同:

  1. 当一个对象只维持着WeakReference,直接被加入ReferenceQueue。然后等待被GC销毁。
  2. 当一个对象只维持着PhantomReference,GC先销毁对象,然后把这个虚引用加入ReferenceQueue。

WeakHashMap

  1. 内部类Entry直接继承WeakReference。
  2. 键值Key被包装成WeakReference的referent。
  3. 当Key被销毁回收,整个Entry都被销毁。

WeakHashMap有个坑:Entry的Key是可以被系统收回。但Key指向的对象被系统回收以后,整个Entry的引用是靠expungeStaleEntries()方法从Map里删除的。但expungeStaleEntries()方法只有在getTable(), size(), 和resize()方法执行的时候被调用。

模仿WeakHashMap的结构,但不写expungeStaleEntries()方法,

class WeakPair extends WeakReference<String>{
    private static ReferenceQueue<String> rq=new ReferenceQueue<String>();
    private Integer bucket;
    public WeakPair(String s, Integer i){
        super(s,rq);
        bucket=i;
    }
    public String getInfo(){
        return get();
    }
    public Integer getBucket(){
        return bucket;
    }
    public static ReferenceQueue<String> getQueue(){return rq;}
    public String toString(){return get()+"@"+bucket;}
}

填充List,然后触发GC,

        Generator<String> gen=new RandomGenerator.String();
        List<WeakPair> list=new ArrayList<WeakPair>();
        for(int i=0;i<10;i++){
            list.add(new WeakPair(gen.next(),i));
        }
        System.out.println(list);
        System.gc();
        Thread.sleep(500);
        ReferenceQueue<String> rq=WeakPair.getQueue();
        System.out.println(list);

只有WeakReference的字段部分被回收,而不是整个WeakPair被回收。

[hiGBEVQ@0, FVhKmED@1, fiRCVzX@2, UOsEWSp@3, egASflb@4, ViKBfJl@5, PaoWYpQ@6, FoUpkau@7, GtRluvU@8, NsyhpYx@9]

[null@0, null@1, null@2, null@3, null@4, null@5, null@6, null@7, null@8, null@9]

一种极端的情况是,有很多个WeakHashMap。每个只插入一个很占内存的Entry。一直不对WeakHashMap做任何其他操作。就算主动System.gc()还是会OOM。

public static void main(String[] args) throws Exception {  
    List<WeakHashMap<byte[][], byte[][]>> maps = new ArrayList<WeakHashMap<byte[][], byte[][]>>();  
    for (int i = 0; i < 1000; i++) {  
        WeakHashMap<byte[][], byte[][]> d = new WeakHashMap<byte[][], byte[][]>();  
        d.put(new byte[1000][1000], new byte[1000][1000]);  
        maps.add(d);  
        System.gc();  
        System.err.println(i);  
    }  
}  

练习

本章习题依赖的工具有:

MyCountries.java

我自己重新写的一个“国家-首都”填充器。也是基于享元模式。

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

public class MyCountries {
    /**
     *  数据二维数组
     */
    public static final String[][] DATA = {
    // Africa
    {"ALGERIA","Algiers"}, {"ANGOLA","Luanda"},
    {"BENIN","Porto-Novo"}, {"BOTSWANA","Gaberone"},
    {"BURKINA FASO","Ouagadougou"},
    {"BURUNDI","Bujumbura"},
    {"CAMEROON","Yaounde"}, {"CAPE VERDE","Praia"},
    {"CENTRAL AFRICAN REPUBLIC","Bangui"},
    {"CHAD","N’djamena"}, {"COMOROS","Moroni"},
    {"CONGO","Brazzaville"}, {"DJIBOUTI","Dijibouti"},
    {"EGYPT","Cairo"}, {"EQUATORIAL GUINEA","Malabo"},
    {"ERITREA","Asmara"}, {"ETHIOPIA","Addis Ababa"},
    {"GABON","Libreville"}, {"THE GAMBIA","Banjul"},
    {"GHANA","Accra"}, {"GUINEA","Conakry"},
    {"BISSAU","Bissau"},
    {"COTE D’IVOIR (IVORY COAST)","Yamoussoukro"},
    {"KENYA","Nairobi"}, {"LESOTHO","Maseru"},
    {"LIBERIA","Monrovia"}, {"LIBYA","Tripoli"},
    {"MADAGASCAR","Antananarivo"}, {"MALAWI","Lilongwe"},
    {"MALI","Bamako"}, {"MAURITANIA","Nouakchott"},
    {"MAURITIUS","Port Louis"}, {"MOROCCO","Rabat"},
    {"MOZAMBIQUE","Maputo"}, {"NAMIBIA","Windhoek"},
    {"NIGER","Niamey"}, {"NIGERIA","Abuja"},
    {"RWANDA","Kigali"},
    {"SAO TOME E PRINCIPE","Sao Tome"},
    {"SENEGAL","Dakar"}, {"SEYCHELLES","Victoria"},
    {"SIERRA LEONE","Freetown"}, {"SOMALIA","Mogadishu"},
    {"SOUTH AFRICA","Pretoria/Cape Town"},
    {"SUDAN","Khartoum"},
    {"SWAZILAND","Mbabane"}, {"TANZANIA","Dodoma"},
    {"TOGO","Lome"}, {"TUNISIA","Tunis"},
    {"UGANDA","Kampala"},
    {"DEMOCRATIC REPUBLIC OF THE CONGO (ZAIRE)",
    "Kinshasa"},
    {"ZAMBIA","Lusaka"}, {"ZIMBABWE","Harare"},
    // Asia
    {"AFGHANISTAN","Kabul"}, {"BAHRAIN","Manama"},
    {"BANGLADESH","Dhaka"}, {"BHUTAN","Thimphu"},
    {"BRUNEI","Bandar Seri Begawan"},
    {"CAMBODIA","Phnom Penh"},
    {"CHINA","Beijing"}, {"CYPRUS","Nicosia"},
    {"INDIA","New Delhi"}, {"INDONESIA","Jakarta"},
    {"IRAN","Tehran"}, {"IRAQ","Baghdad"},
    {"ISRAEL","Jerusalem"}, {"JAPAN","Tokyo"},
    {"JORDAN","Amman"}, {"KUWAIT","Kuwait City"},
    {"LAOS","Vientiane"}, {"LEBANON","Beirut"},
    {"MALAYSIA","Kuala Lumpur"}, {"THE MALDIVES","Male"},
    {"MONGOLIA","Ulan Bator"},
    {"MYANMAR (BURMA)","Rangoon"},
    {"NEPAL","Katmandu"}, {"NORTH KOREA","P’yongyang"},
    {"OMAN","Muscat"}, {"PAKISTAN","Islamabad"},
    {"PHILIPPINES","Manila"}, {"QATAR","Doha"},
    {"SAUDI ARABIA","Riyadh"}, {"SINGAPORE","Singapore"},
    {"SOUTH KOREA","Seoul"}, {"SRI LANKA","Colombo"},
    {"SYRIA","Damascus"},
    {"TAIWAN (REPUBLIC OF CHINA)","Taipei"},
    {"THAILAND","Bangkok"}, {"TURKEY","Ankara"},
    {"UNITED ARAB EMIRATES","Abu Dhabi"},
    {"VIETNAM","Hanoi"}, {"YEMEN","Sana’a"},
    // Australia and Oceania
    {"AUSTRALIA","Canberra"}, {"FIJI","Suva"},
    {"KIRIBATI","Bairiki"},
    {"MARSHALL ISLANDS","Dalap-Uliga-Darrit"},
    {"MICRONESIA","Palikir"}, {"NAURU","Yaren"},
    {"NEW ZEALAND","Wellington"}, {"PALAU","Koror"},
    {"PAPUA NEW GUINEA","Port Moresby"},
    {"SOLOMON ISLANDS","Honaira"}, {"TONGA","Nuku’alofa"},
    {"TUVALU","Fongafale"}, {"VANUATU","< Port-Vila"},
    {"WESTERN SAMOA","Apia"},
    // Eastern Europe and former USSR
    {"ARMENIA","Yerevan"}, {"AZERBAIJAN","Baku"},
    {"BELARUS (BYELORUSSIA)","Minsk"},
    {"BULGARIA","Sofia"}, {"GEORGIA","Tbilisi"},
    {"KAZAKSTAN","Almaty"}, {"KYRGYZSTAN","Alma-Ata"},
    {"MOLDOVA","Chisinau"}, {"RUSSIA","Moscow"},
    {"TAJIKISTAN","Dushanbe"}, {"TURKMENISTAN","Ashkabad"},
    {"UKRAINE","Kyiv"}, {"UZBEKISTAN","Tashkent"},
    // Europe
    {"ALBANIA","Tirana"}, {"ANDORRA","Andorra la Vella"},
    {"AUSTRIA","Vienna"}, {"BELGIUM","Brussels"},
    {"BOSNIA","-"}, {"HERZEGOVINA","Sarajevo"},
    {"CROATIA","Zagreb"}, {"CZECH REPUBLIC","Prague"},
    {"DENMARK","Copenhagen"}, {"ESTONIA","Tallinn"},
    {"FINLAND","Helsinki"}, {"FRANCE","Paris"},
    {"GERMANY","Berlin"}, {"GREECE","Athens"},
    {"HUNGARY","Budapest"}, {"ICELAND","Reykjavik"},
    {"IRELAND","Dublin"}, {"ITALY","Rome"},
    {"LATVIA","Riga"}, {"LIECHTENSTEIN","Vaduz"},
    {"LITHUANIA","Vilnius"}, {"LUXEMBOURG","Luxembourg"},
    {"MACEDONIA","Skopje"}, {"MALTA","Valletta"},
    {"MONACO","Monaco"}, {"MONTENEGRO","Podgorica"},
    {"THE NETHERLANDS","Amsterdam"}, {"NORWAY","Oslo"},
    {"POLAND","Warsaw"}, {"PORTUGAL","Lisbon"},
    {"ROMANIA","Bucharest"}, {"SAN MARINO","San Marino"},
    {"SERBIA","Belgrade"}, {"SLOVAKIA","Bratislava"},
    {"SLOVENIA","Ljuijana"}, {"SPAIN","Madrid"},
    {"SWEDEN","Stockholm"}, {"SWITZERLAND","Berne"},
    {"UNITED KINGDOM","London"}, {"VATICAN CITY","---"},
    // North and Central America
    {"ANTIGUA AND BARBUDA","Saint John’s"},
    {"BAHAMAS","Nassau"},
    {"BARBADOS","Bridgetown"}, {"BELIZE","Belmopan"},
    {"CANADA","Ottawa"}, {"COSTA RICA","San Jose"},
    {"CUBA","Havana"}, {"DOMINICA","Roseau"},
    {"DOMINICAN REPUBLIC","Santo Domingo"},
    {"EL SALVADOR","San Salvador"},
    {"GRENADA","Saint George’s"},
    {"GUATEMALA","Guatemala City"},
    {"HAITI","Port-au-Prince"},
    {"HONDURAS","Tegucigalpa"}, {"JAMAICA","Kingston"},
    {"MEXICO","Mexico City"}, {"NICARAGUA","Managua"},
    {"PANAMA","Panama City"}, {"ST. KITTS","-"},
    {"NEVIS","Basseterre"}, {"ST. LUCIA","Castries"},
    {"ST. VINCENT AND THE GRENADINES","Kingstown"},
    {"UNITED STATES OF AMERICA","Washington, D.C."},
    // South America
    {"ARGENTINA","Buenos Aires"},
    {"BOLIVIA","Sucre (legal)/La Paz(administrative)"},
    {"BRAZIL","Brasilia"}, {"CHILE","Santiago"},
    {"COLOMBIA","Bogota"}, {"ECUADOR","Quito"},
    {"GUYANA","Georgetown"}, {"PARAGUAY","Asuncion"},
    {"PERU","Lima"}, {"SURINAME","Paramaribo"},
    {"TRINIDAD AND TOBAGO","Port of Spain"},
    {"URUGUAY","Montevideo"}, {"VENEZUELA","Caracas"},
    };


    /**
     * 套嵌MAP
     * 实现 AbstractMap 要实现 entrySet()。因为AbstractMap没有实现Map接口定义的entrySet方法。
     */
    public static class CountriesMap extends AbstractMap<String,String>{

        /**
         * MAP内部二层套嵌类Entry 实现 Map.Entry 套嵌泛型类。这里为了支持享元,要重写两个方法:getKey()和getValue()。
         * 享元模式:Entry只要一个index字段。Entry所有内容根据这个index到享元里找。
         */
        public static class Entry implements Map.Entry<String,String>{
            private int index;
            public Entry(int index){
                this.index=index;
            }
            public String getKey(){return DATA[index%DATA.length][0];}
            public String getValue(){return DATA[index%DATA.length][1];}
            public boolean equals(Object o){return getKey()==((Entry)o).getKey();}
            public int hashCode(){return getValue().hashCode();}
            public String setValue(String value){
                throw new UnsupportedOperationException();  //只读,不支持改数据
            }
            public String toString(){return "("+getKey()+","+getValue()+")";}
            public int getIndex(){return index;}
        }


        /**
         * 二层套嵌 Set
         * 实现只读 AbstractSet 要实现 size() & iterator()。 因为AbstractSet继承自AbstractCollection。但AbstractCollection中定义了size() & iterator()方法,但没有实现。
         * 享元模式:只保留一个size字段。Set的所有内容根据这个size从享元中找。
         */
        public static class EntrySet extends AbstractSet<Map.Entry<String,String>>{
            private int size;
            public EntrySet(){
                this.size=DATA.length;
            }
            public EntrySet(int size){
                if(size<0){
                    this.size=0;
                }else if(size>DATA.length){
                    this.size=DATA.length;
                }else{
                    this.size=size;
                }
            }
            public int size(){
                return size;
            }

            /**
             * Set 内部三层套嵌迭代器
             */
            private class EntryIterator implements Iterator<Map.Entry<String,String>>{
                private int index=0;
                public boolean hasNext(){
                    return index<size-1;
                }
                public Map.Entry<String,String> next(){
                    return new Entry(index++);
                }
                public void remove(){
                    throw new UnsupportedOperationException();
                }
                public void reset(){index=0;}
            }

            public Iterator<Map.Entry<String,String>> iterator(){
                return new EntryIterator();
            }

        }

        //定义好了套嵌Set之后,写entrySet()方法
        public Set<Map.Entry<String,String>> entrySet(){
            return new EntrySet(DATA.length);
        }

    }

    //神奇的匿名内部类,重写entrySet()方法。
    public static Map<String,String> select(final int size){
        return new CountriesMap(){
            @Override
            public Set<Map.Entry<String,String>> entrySet(){
                return new EntrySet(size);
            }
        };
    }


    //返回整个Map
    static Map<String,String> map=new CountriesMap();
    public static Map<String,String> capitals(){
        return map;
    }

    //返回部分Map
    public static Map<String,String> capitals(int size){
        return select(size);
    }

    //返回所有国家名的List
    public static List<String> names(){
        return new ArrayList<String>(map.keySet());
    }

    //返回部分国家名的List
    public static List<String> names(int size){
        return new ArrayList<String>(capitals(size).keySet());
    }
}

RandomGenerator.java

随机填充器。主要用来生成随机String,Integer等。

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

public class RandomGenerator{
    private static Random rand=new Random();

    //Boolean
    public static class Boolean implements Generator<java.lang.Boolean>{
        public java.lang.Boolean next(){
            return rand.nextBoolean();
        }
    }
    //Integer
    public static class Integer implements Generator<java.lang.Integer>{
        public java.lang.Integer next(){
            return rand.nextInt();
        }
    }
    //Long
    public static class Long implements Generator<java.lang.Long>{
        public java.lang.Long next(){
            return rand.nextLong();
        }
    }
    //Short
    public static class Short implements Generator<java.lang.Short>{
        public java.lang.Short next(){
            return (short)rand.nextInt((int)java.lang.Short.MAX_VALUE);
        }
    }
    //Float
    public static class Float implements Generator<java.lang.Float>{
        public java.lang.Float next(){
            return rand.nextFloat();
        }
    }
    //Double
    public static class Double implements Generator<java.lang.Double>{
        public java.lang.Double next(){
            return rand.nextDouble();
        }
    }
    //Byte
    public static class Byte implements Generator<java.lang.Byte>{
        private byte[] b=new byte[1];
        public java.lang.Byte next(){
            rand.nextBytes(b);
            return b[0];
        }
    }

    //Charactor
    private static final char[] CS=("abcdefghijklmnopqrstuvwxyz"+"ABCDEFGHIJKLMNOPQRSTUVWXYZ").toCharArray();
    public static class Character implements Generator<java.lang.Character>{
        public java.lang.Character next(){
            return CS[rand.nextInt(CS.length)];
        }
    }


    //String
    public static class String implements Generator<java.lang.String>{
        private int size=7;
        private Generator<java.lang.Character> c=new Character();
        public String(){}
        public String(int size){this.size=size;}
        public java.lang.String next(){
            StringBuilder sb=new StringBuilder();
            for(int i=0;i<size;i++){
                sb.append(c.next());
            }
            return sb.toString();
        }
    }

    /**
     *  测试
     */
    public static void main(java.lang.String[] args){
        RandomGenerator.String s=new RandomGenerator.String();
        System.out.println(s.next());
    }
}

Exercise 1

class CountriesComparator implements Comparator<Map.Entry<String,String>>{
    public int compare(Map.Entry<String,String> entry1, Map.Entry<String,String> entry2){
        return entry1.getKey().compareTo(entry2.getKey());
    }
}

public class Exercise1{
    public static void main(String[] args){
        /**
         *  ArrayList版本
         */
        List<Map.Entry<String,String>> al=new ArrayList<Map.Entry<String,String>>(MyCountries.capitals(10).entrySet());
        //System.out.println(al);
        /**
         *  LinkedList版本
         */
        List<Map.Entry<String,String>> ll=new LinkedList<Map.Entry<String,String>>(MyCountries.capitals(15).entrySet());
        //System.out.println(ll);

        /**
         *  排序再乱序
         */
        Collections.sort(al, new CountriesComparator());
        System.out.println(al);
        Collections.shuffle(al);
        System.out.println(al);
        Collections.sort(al, new CountriesComparator());
        System.out.println(al);
        Collections.shuffle(al);
        System.out.println(al);
    }
}

Exercise 2

Exercise 2: (2) Produce a Map and a Set containing all the countries that begin with ‘A’. 在MyCountries.java里增加一个countriesBeginWithXXX()方法。

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

public class MyCountries {

	//之前的代码... ...

    //返回国家名以“subName”开头的国家map
    public static Map<String,String> countriesBeginWithXXX(String subName){
        Map<String,String> hm=new HashMap<String,String>();
        Set<Map.Entry<String,String>> set=map.entrySet();
        for(Map.Entry<String,String> entry:set){
            if(entry.getKey().indexOf(subName)==0){
                hm.put(entry.getKey(),entry.getValue());
            }
        }
        return hm;
    }
}
Exercise2.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;

public class Exercise2{
    public static void main(String[] args){
        /**
         *  "A"字母打头国家的Map
         */
        System.out.println(MyCountries.countriesBeginWithXXX("A"));

        /**
         *  "A"字母打头国家的Set
         */
        System.out.println(MyCountries.countriesBeginWithXXX("A").entrySet());
    }
}

Exercise 3

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

public class Exercise3{
    public static void main(String[] args){
        /**
         *  AbstractSet版本: 按插入顺序
         */
        System.out.println("");
        System.out.println("##########################################");
        System.out.println(">>>>>>>>>      AbstractSet      <<<<<<<<<");
        System.out.println("##########################################");
        for(int i=0;i<5;i++){
            Set<Map.Entry<String,String>> set=MyCountries.capitals(20).entrySet();
            System.out.println(set);
        }

        /**
         *  HashSet版本:不保持插入顺序
         */
        System.out.println("");
        System.out.println("######################################");
        System.out.println(">>>>>>>>>      HashSet      <<<<<<<<<");
        System.out.println("######################################");
        for(int i=0;i<5;i++){
            Set<Map.Entry<String,String>> set=new HashSet<Map.Entry<String,String>>(MyCountries.capitals(20).entrySet());
            System.out.println(set);
        }

        /**
         *  LinkedHashSet版本:保持插入顺序
         */
        System.out.println("");
        System.out.println("############################################");
        System.out.println(">>>>>>>>>      LinkedHashSet      <<<<<<<<<");
        System.out.println("############################################");
        for(int i=0;i<5;i++){
            Set<Map.Entry<String,String>> set=new LinkedHashSet<Map.Entry<String,String>>(MyCountries.capitals(20).entrySet());
            System.out.println(set);
        }

        /**
         *  TreeSet版本: 按照ABCD顺序
         */
        System.out.println("");
        System.out.println("######################################");
        System.out.println(">>>>>>>>>      TreeSet      <<<<<<<<<");
        System.out.println("######################################");
        for(int i=0;i<5;i++){
            Set<Map.Entry<String,String>> set=new TreeSet<Map.Entry<String,String>>(MyCountries.capitals(20).entrySet());
            System.out.println(set);
        }

    }
}
MyCountries.java

在MyCountries.CountriesMap.Entry套嵌类里,要加一个compareTo()方法,以实现Comparable接口。

public class MyCountries {

	//之前的代码 ... ...

        public static class Entry implements Map.Entry<String,String>, Comparable<Entry>{
            private int index;
            public Entry(int index){
                this.index=index;
            }
            public String getKey(){return DATA[index%DATA.length][0];}
            public String getValue(){return DATA[index%DATA.length][1];}
            public boolean equals(Object o){return getKey()==((Entry)o).getKey();}
            public int hashCode(){return getValue().hashCode();}
            public String setValue(String value){
                throw new UnsupportedOperationException();  //只读,不支持改数据
            }
            public String toString(){return "("+getKey()+","+getValue()+")";}
            public int getIndex(){return index;}
            public int compareTo(Entry e){
                return this.getKey().compareTo(e.getKey());
            }
        }

	//之后的代码 ... ...

Exercise 4

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

class CollectionInit{
    //读文件切词
    public static List<String> readFile(String inFile){
        try{
            BufferedReader in=new BufferedReader(new FileReader(inFile));
            String s;
            List<String> words=new ArrayList<String>();
            while(true){
                try{
                    s=in.readLine();
                    if(s==null){break;}
                    words.addAll(Arrays.asList(s.replaceAll("\\p{Punct}","").split("\\s")));
                }catch(Exception e){
                    System.out.println(e);
                }
            }
            return words;
        }catch(Exception e){
            System.out.println(e);
            return null;
        }
    }
}

public class Exercise4{
    public static void main(String[] args){
        List<String> list=CollectionInit.readFile("/Users/Wei/java/com/ciaoshen/thinkinjava/chapter17/Text.txt");
        System.out.println(list);
    }
}

Exercise 5

public class CountingMapData extends AbstractMap<Integer,String> { private int size; private static String[] chars = “A B C D E F G H I J K L M N O P Q R S T U V W X Y Z”.split(“ “); public CountingMapData(int size) { if(size < 0) this.size = 0; this.size = size; } private static class Entry implements Map.Entry<Integer,String> { int index; Entry(int index) { this.index = index; } public boolean equals(Object o) { return Integer.valueOf(index).equals(o); } public Integer getKey() { return index; } public String getValue() { return chars[index % chars.length] + Integer.toString(index / chars.length); } public String setValue(String value) { throw new UnsupportedOperationException(); } public int hashCode() { return Integer.valueOf(index).hashCode(); } }

private static class EntrySet extends AbstractSet<Map.Entry<Integer,String>> {
    private int size;
    public EntrySet(int size){
        this.size=size;
    }
    public int size(){return size;}

    private class Iter implements Iterator<Map.Entry<Integer,String>>{
        int index=0;
        public boolean hasNext(){
            return index<size;
        }
        public Map.Entry<Integer,String> next(){
            return new Entry(index++);
        }
        public void remove(){
            throw new UnsupportedOperationException();
        }
    }

    public Iterator<Map.Entry<Integer,String>> iterator(){
        return new Iter();
    }
}
public Set<Map.Entry<Integer,String>> entrySet() {
    return new EntrySet(size);
}

public static void main(String[] args) {
    System.out.println(new CountingMapData(60));
} } ```

Exercise 6

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

class UnsupportedList extends AbstractList<String>{
    private String[] staticStr="A B C D E F G H I J".split(" ");
    public String get(int index){
        return staticStr[index];
    }
    public int size(){return staticStr.length;}
}

public class Exercise6 {

    public static void main(String[] args) {
        List<String> list=new UnsupportedList();
        Unsupported.test(list);
    }
}

Exercise 7

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

public class Exercise7{

    /**
     *Step 1
     */
    public static void printTwoList(){
        List<String> al=new ArrayList<String>(MyCountries.names());
        List<String> ll=new LinkedList<String>(MyCountries.names());

        Iterator<String> iteAl=al.iterator();
        Iterator<String> iteLl=ll.iterator();

        while(iteAl.hasNext()){
            System.out.print("["+iteAl.next()+"]");
            if(iteAl.hasNext()){
                System.out.print(",");
            }
        }

        System.out.println("\n\n");

        while(iteLl.hasNext()){
            System.out.print("["+iteLl.next()+"]");
            if(iteLl.hasNext()){
                System.out.print(",");
            }
        }
    }

    /**
     *Step 2
     */
    public static void insertion(){
        List<String> al=new ArrayList<String>(MyCountries.names());
        List<String> ll=new LinkedList<String>(MyCountries.names());

        ListIterator<String> listIteAl=al.listIterator();
        ListIterator<String> listIteLl=ll.listIterator();

        while(listIteAl.hasNext() && listIteLl.hasNext()){
            listIteLl.add(listIteAl.next());
            String s=listIteLl.next();
        }

        System.out.println(ll);
    }

    /**
     *Step 3
     */
    public static void inverseInsertion(){
        List<String> al=new ArrayList<String>(MyCountries.names());
        List<String> ll=new LinkedList<String>(MyCountries.names());

        ListIterator<String> listIteAl=al.listIterator(al.size());
        ListIterator<String> listIteLl=ll.listIterator();

        while(listIteAl.hasPrevious() && listIteLl.hasNext()){
            listIteLl.add(listIteAl.previous());
            String s=listIteLl.next();
        }

        System.out.println(ll);
    }


    public static void main(String[] args){
        printTwoList();
        insertion();
        inverseInsertion();
    }
}

Exercise 8

Exercise 8: (7) Create a generic, singly linked list class called SList, which, to keep things simple, does not implement the List interface. Each Link object in the list should contain a reference to the next element in the list, but not the previous one (LinkedList, in contrast, is a doubly linked list, which means it maintains links in both directions). Create your own SListIterator which, again for simplicity, does not implement ListIterator. The only method in SList other than toString( ) should be iterator( ), which produces an SListIterator. The only way to insert and remove elements from an SList is through SListIterator. Write code to demonstrate SList.

关于LinkedList头节点的总结:

  1. 头节点是不储存元素信息的纯功能性节点。用来停放指针。
  2. 单纯从功能上讲,单个头节点head就够了。不需要尾节点。
  3. 没有head头节点的话,大部分操作对第一个元素和后续元素,实现都不同。导致逻辑复杂。容易出bug。编程目标是不出错,不是为了挑战脑力。
  4. 不需要专门的桩子尾节点。但需要一个tail指针,指向末尾元素,方便从末尾插入新元素。
  5. 双头节点版本:一个头节点head,一个尾节点tail。也没什么不好。反而逻辑清楚。
  6. JDK里的官方LinkedList是没有头节点的版本。不知道为什么。难道是节约内存?
单头节点版本
  1. 单向列表
  2. 单头节点。只有前头节点head,无尾节点tail。
  3. tail只是一个指向最后一个元素的指针。
  4. 前中后2个光标:previous,cursor。cursor指向上一个next()返回的元素。previous指向cursor的前一个元素。
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;

@SuppressWarnings(value={"unchecked", "rawtypes"})
public class SListV2<T>{

    private Node<T> head;
    private Node<T> tail;
    private int size=0;
    public SListV2(){
        head=new Node();
        tail=head;
    }

    private static class Node<T>{
        private T item;
        private Node<T> next;
        public Node(){item=null;next=null;}
        public Node(T t){item=t;next=null;}
        public String toString(){return item.toString();}
    }

    private class SListIterator{
        private Node<T> cursor=head;
        private Node<T> previous=cursor;
        private int index=0;
        //在cursor后面插入新元素
        public void add(T t){
            Node<T> n=new Node<T>(t);
            n.next=tail.next;
            tail.next=n;
            tail=n;
            size++;
        }
        //替换cursor位置元素
        public void set(T t){
            if(cursor==head){
                System.out.println("Not Begun!");
            }else{
                Node<T> n=new Node<T>(t);
                cursor.item=t;
            }
        }
        //从cursor位置开始往后删除
        public void remove(){
            if(cursor==previous){
                System.out.println("Can't remove!");
            }else{
                if(cursor==tail){
                    tail=previous;
                }
                previous.next=cursor.next;
                cursor=previous;
                index--;
                size--;
            }
        }
        //current还没到tail
        public boolean hasNext(){
            return cursor.next!=null;
        }
        //返回cursor的下一个元素
        public Node<T> next(){
            if(hasNext()){
                previous=cursor;
                cursor=cursor.next;
                index++;
                return cursor;
            }else{
                System.out.println("Reach the end!");
                return null;
            }
        }
        public int index(){
            return index;
        }
        public int size(){
            return size;
        }
        public void reset(){
            cursor=head;
            previous=cursor;
            index=0;
        }
    }

    public SListIterator iterator(){
        return new SListIterator();
    }
    public String toString(){
        StringBuilder sb=new StringBuilder();
        SListIterator ite=iterator();
        while(ite.hasNext()){
            sb.append("["+ite.next()+"]");
            if(ite.hasNext()){
                sb.append(",");
            }
        }
        return sb.toString();
    }

    /**
     *  测试
     */
    public static void main(String[] args){
        String[] s="A B C D E F G H I J K L M N O P Q R S T U V W X Y Z".split(" ");
        SListV2<String> list=new SListV2<String>();
        SListV2.SListIterator ite=list.iterator();
        for(int i=0;i<s.length;i++){
            ite.add(s[i]);
        }
        System.out.println(list);
        for(int i=0;i<ite.size();i++){
            System.out.println(ite.next());
        }
        ite.reset();
        int length=ite.size();
        for(int i=0;i<10;i++){
            Node<String> n=ite.next();
            ite.remove();
            ite.remove();
        }
        System.out.println(list);
    }
}
双头节点版本
  1. 单向列表
  2. 双头节点。前头节点head,后尾节点tail。两个节点永远不存放元素。尾节点的next指向最后一个元素。空链表时指向head。
  3. 两个光标:previous,cursor。主要是cursor。previous只负责盯住cursor,并在remove的时候提供前一节点的next指针。 ```java package com.ciaoshen.thinkinjava.chapter17; import java.util.*;

@SuppressWarnings(value={“unchecked”, “rawtypes”}) public class SListV3{

private Node<T> head;
private Node<T> tail;
private int size=0;
public SListV3(){
    head=new Node();
    tail=new Node();
    head.next=tail;
    tail.next=head;
}

private static class Node<T>{
    private T item;
    private Node<T> next;
    public Node(){item=null;next=null;}
    public Node(T t){item=t;next=null;}
    public String toString(){return item.toString();}
}

private class SListIterator{
    private Node<T> cursor=head;
    private Node<T> previous=cursor;
    private int index=0;
    //在tail栓塞前插入新元素
    public void add(T t){
        Node<T> n=new Node<T>(t);
        tail.next.next=n;
        n.next=tail;
        tail.next=n;
        size++;
    }
    //替换当前cursor元素(若当前元素被删,也不能set。)
    public void set(T t){
        if(cursor==previous){
            System.out.println("Cannot set!");
        }else{
            cursor.item=t;
        }
    }
    //只删除上一次next()返回的元素。每次next()只能删除一次。
    public void remove(){
        if(cursor==previous){
            System.out.println("Can't remove!");
        }else{
            if(tail.next==cursor){
                tail.next=previous;
            }
            previous.next=cursor.next;
            cursor=previous;
            index--;
            size--;
        }
    }
    //current还没到tail
    public boolean hasNext(){
        return cursor.next!=tail;
    }
    //返回cursor的下一个元素
    public Node<T> next(){
        if(hasNext()){
            previous=cursor;
            cursor=cursor.next;
            index++;
            return cursor;
        }else{
            System.out.println("Reach the end!");
            return null;
        }
    }
    public int index(){
        return index;
    }
    public int size(){
        return size;
    }
    public void reset(){
        cursor=head;
        previous=cursor;
        index=0;
    }
}

public SListIterator iterator(){
    return new SListIterator();
}
public String toString(){
    StringBuilder sb=new StringBuilder();
    SListIterator ite=iterator();
    while(ite.hasNext()){
        sb.append("["+ite.next()+"]");
        if(ite.hasNext()){
            sb.append(",");
        }
    }
    return sb.toString();
}

/**
 *  测试
 */
public static void main(String[] args){
    String[] s="A B C D E F G H I J K L M N O P Q R S T U V W X Y Z".split(" ");
    SListV3<String> list=new SListV3<String>();
    SListV3.SListIterator ite=list.iterator();
    for(int i=0;i<s.length;i++){
        ite.add(s[i]);
    }
    System.out.println(list);
    for(int i=0;i<ite.size();i++){
        System.out.println(ite.next());
    }
    ite.reset();
    int length=ite.size();
    for(int i=0;i<10;i++){
        Node<String> n=ite.next();
        ite.remove();
        ite.remove();
    }
    System.out.println(list);
} } ```
无头节点版本
  1. 单向列表
  2. 没有栓塞头
  3. head和tail只是两个指针,指向第一个和最后一个元素。
  4. 当链表为空:维持一个空节点。head和tail都指向这个空节点。只有一个元素的时候,head和tail也都指向唯一的这个节点。
  5. 两个光标:previous,cursor。cursor指向上一个next()返回的元素。previous指向cursor的前一个元素。
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;

@SuppressWarnings(value={"unchecked", "rawtypes"})
public class SListV4<T>{

    private Node<T> head;
    private Node<T> tail;
    private int size=0;
    public SListV4(){
        head=new Node();
        tail=head;
    }

    private static class Node<T>{
        private T item;
        private Node<T> next;
        public Node(){item=null;next=null;}
        public Node(T t){item=t;next=null;}
        public Node(T t, Node<T> n){item=t;next=n;}
        public String toString(){return item.toString();}
    }

    private class SListIterator{
        private Node<T> cursor=null;
        private Node<T> previous=null;
        private int index=-1;
        //在tail栓塞前插入新元素
        public void add(T t){
            //空链表
            if(head.item==null){
                head.item=t;
            }else{
                Node<T> n=new Node<T>(t);
                tail.next=n;
                tail=n;
            }
            size++;
        }
        //替换当前cursor元素(若当前元素被删,也不能set。)
        public void set(T t){
            if(cursor==previous){
                System.out.println("Cannot set!");
            }else{
                cursor.item=t;
            }
        }
        //只删除上一次next()返回的元素。每次next()只能删除一次。
        public void remove(){
            if(cursor==previous){
                System.out.println("Can't remove!");
            }else{
                if(cursor==head){
                    cursor.item=null;
                    cursor=null;
                } else {
                    previous.next=cursor.next;
                    cursor=previous;
                }
                index--;
                size--;
            }
        }
        //current还没到tail
        public boolean hasNext(){
            if(cursor==null){
                return (head.item==null && head.next==null)? false:true;
            }else{
                return (cursor.next==null)? false:true;
            }
        }
        //返回cursor的下一个元素
        public Node<T> next(){
            if(hasNext()){
                if(cursor==null && head.item==null){
                    cursor=head.next;
                    previous=head;
                }else if(cursor==null && head.item!=null){
                    cursor=head;
                }else{
                    previous=cursor;
                    cursor=cursor.next;
                }
                index++;
                return cursor;
            }else{
                System.out.println("Reach the end!");
                return null;
            }
        }
        public int index(){
            return index;
        }
        public int size(){
            return size;
        }
        public void reset(){
            cursor=previous=null;
            index=0;
        }
    }

    public SListIterator iterator(){
        return new SListIterator();
    }
    public String toString(){
        StringBuilder sb=new StringBuilder();
        SListIterator ite=iterator();
        while(ite.hasNext()){
            sb.append("["+ite.next()+"]");
            if(ite.hasNext()){
                sb.append(",");
            }
        }
        return sb.toString();
    }

    /**
     *  测试
     */
    public static void main(String[] args){
        String[] s="A B C D E F G H I J K L M N O P Q R S T U V W X Y Z".split(" ");
        SListV4<String> list=new SListV4<String>();
        SListV4.SListIterator ite=list.iterator();
        for(int i=0;i<s.length;i++){
            ite.add(s[i]);
        }
        System.out.println(list);
        for(int i=0;i<ite.size();i++){
            System.out.println(ite.next());
        }
        ite.reset();
        for(int i=0;i<10;i++){
            Node<String> n=ite.next();
            ite.set("XXX");
            System.out.println(list);
            ite.remove();
        }
        System.out.println(list);
    }
}

Exercise 9

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

public class RandomGenerator{
    private static Random rand=new Random();

    //Boolean
    public static class Boolean implements Generator<java.lang.Boolean>{
        public java.lang.Boolean next(){
            return rand.nextBoolean();
        }
    }
    //Integer
    public static class Integer implements Generator<java.lang.Integer>{
        public java.lang.Integer next(){
            return rand.nextInt();
        }
    }
    //Long
    public static class Long implements Generator<java.lang.Long>{
        public java.lang.Long next(){
            return rand.nextLong();
        }
    }
    //Short
    public static class Short implements Generator<java.lang.Short>{
        public java.lang.Short next(){
            return (short)rand.nextInt((int)java.lang.Short.MAX_VALUE);
        }
    }
    //Float
    public static class Float implements Generator<java.lang.Float>{
        public java.lang.Float next(){
            return rand.nextFloat();
        }
    }
    //Double
    public static class Double implements Generator<java.lang.Double>{
        public java.lang.Double next(){
            return rand.nextDouble();
        }
    }
    //Byte
    public static class Byte implements Generator<java.lang.Byte>{
        private byte[] b=new byte[1];
        public java.lang.Byte next(){
            rand.nextBytes(b);
            return b[0];
        }
    }

    //Charactor
    private static final char[] CS=("abcdefghijklmnopqrstuvwxyz"+"ABCDEFGHIJKLMNOPQRSTUVWXYZ").toCharArray();
    public static class Character implements Generator<java.lang.Character>{
        public java.lang.Character next(){
            return CS[rand.nextInt(CS.length)];
        }
    }


    //String
    public static class String implements Generator<java.lang.String>{
        private int size=7;
        private Generator<java.lang.Character> c=new Character();
        public String(){}
        public String(int size){this.size=size;}
        public java.lang.String next(){
            StringBuilder sb=new StringBuilder();
            for(int i=0;i<size;i++){
                sb.append(c.next());
            }
            return sb.toString();
        }
    }
}
Exercise9.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;

public class Exercise9{
    public static void main(String[] args){
        TreeSet<String> ts=new TreeSet<String>();
        RandomGenerator.String gen=new RandomGenerator.String();
        for(int i=0;i<10;i++){
            ts.add(gen.next());
        }
        System.out.println(ts);
    }
}

Exercise 10

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

//内部元素必须实现equals()方法,实现Comparable接口或者有额外的Comparator。
class LinkedSortedSet<E> extends AbstractSet<E> implements SortedSet<E>{
    //基于LinkedList。类似一个高级代理,或装饰器
    private LinkedList<E> ll;

    //额外比较器字段
    private Comparator<? super E> comp;

    //构造器,两个版本:有Comparator和没有Comparator。
    public LinkedSortedSet(){
        ll=new LinkedList<E>();
        comp=null;
    }
    public LinkedSortedSet(Comparator<? super E> c){
        ll=new LinkedList<E>();
        comp=c;
    }

    //靠add()方法维持元素顺序
    @SuppressWarnings("unchecked")
    public boolean add(E element){
        if(!ll.contains(element)){
            if(ll.isEmpty()){
                return ll.add(element);
            }else{
                Iterator<E> ite=ll.iterator();
                int index=0;
                if(comp!=null){
                    //用Comparator比
                    while(ite.hasNext()){
                        if(comp.compare(ite.next(),element)>0){
                            ll.add(index,element);
                            break;
                        }else{
                            index++;
                        }
                    }
                    if(index==ll.size()){
                        ll.addLast(element);
                    }
                    return true;
                }else{
                    //用compareTo()比
                    while(ite.hasNext()){
                        E curr=ite.next();
                        if(((Comparable)curr).compareTo(element)>0){
                            ll.add(index,element);
                            break;
                        }else{
                            index++;
                        }
                    }
                    if(index==ll.size()){
                        ll.add(index,element);
                    }
                    return true;
                }
            }
        }else{
            return false;
        }
    }

    //检测集合中是否有equals(element)的元素。
    public boolean contains(Object o){
        return ll.contains(o);
    }

    //靠构造器带来额外的comparator
    public Comparator<? super E> comparator(){
        return comp;
    }

    //返回首元素
    public E first(){
        return ll.getFirst();
    }

    //返回末尾元素
    public E last(){
        return ll.getLast();
    }

    //返回从首元素到参数toElement元素的子集
    @SuppressWarnings("unchecked")
    public LinkedSortedSet<E> headSet(E toElement){
        LinkedSortedSet<E> lse=new LinkedSortedSet<E>();
        Iterator<E> ite=ll.iterator();
        if(comp!=null){
            //用Comparator比
            while(ite.hasNext()){
                E curr=ite.next();
                if(comp.compare(curr,toElement)<0){
                    lse.add(curr);
                }
            }
        }else{
            //用compareTo()比
            while(ite.hasNext()){
                E curr=ite.next();
                if(((Comparable)curr).compareTo(toElement)<0){
                    lse.add(curr);
                }
            }
        }
        return lse;
    }

    //返回从fromElement到参数toElement元素的子集
    @SuppressWarnings("unchecked")
    public LinkedSortedSet<E> subSet(E fromElement, E toElement){
        LinkedSortedSet<E> lse=new LinkedSortedSet<E>();
        Iterator<E> ite=ll.iterator();
        if(comp!=null){
            //用Comparator比
            while(ite.hasNext()){
                E curr=ite.next();
                if(comp.compare(curr,fromElement)>0 && comp.compare(curr,toElement)<0){
                    lse.add(curr);
                }
            }
        }else{
            //用compareTo()比
            while(ite.hasNext()){
                E curr=ite.next();
                if(((Comparable)curr).compareTo(fromElement)>0 && ((Comparable)curr).compareTo(toElement)<0){
                    lse.add(curr);
                }
            }
        }
        return lse;
    }

    //返回从fromElement到莫为元素的子集
    @SuppressWarnings("unchecked")
    public LinkedSortedSet<E> tailSet(E fromElement){
        LinkedSortedSet<E> lse=new LinkedSortedSet<E>();
        Iterator<E> ite=ll.iterator();
        if(comp!=null){
            //用Comparator比
            while(ite.hasNext()){
                E curr=ite.next();
                if(comp.compare(curr,fromElement)>0){
                    lse.add(curr);
                }
            }
        }else{
            //用compareTo()比
            while(ite.hasNext()){
                E curr=ite.next();
                if(((Comparable)curr).compareTo(fromElement)>0){
                    lse.add(curr);
                }
            }
        }
        return lse;
    }

    //返回迭代器引用
    public Iterator<E> iterator(){return ll.iterator();}

    public String toString(){return ll.toString();}

    public void clear(){ll.clear();}

    public int size(){return ll.size();}
}


public class Exercise10{
    public static void main(String[] args){
        Generator<java.lang.String> gen=new RandomGenerator.String();
        LinkedSortedSet<String> set=new LinkedSortedSet<String>();
        //LinkedSortedSet<String> set=new LinkedSortedSet<String>(java.lang.String.CASE_INSENSITIVE_ORDER);

        String no3=null;
        String no8=null;
        for(int i=0;i<10;i++){
            String s=gen.next();
            System.out.println(s);
            boolean b=set.add(s);
            if(i==2){
                no3=s;
            }
            if(i==7){
                no8=s;
            }
        }
        System.out.println(set);

        System.out.println(set.contains("abcdefg"));
        System.out.println(set.contains(no3));

        System.out.println("X    >>>"+no3);
        System.out.println("Y    >>>"+no8);
        System.out.println("Element befor X >>>"+set.headSet(no3));
        System.out.println("Element after Y >>>"+set.tailSet(no8));
        System.out.println("Element between X & Y >>>"+set.subSet(no3,no8));
    }
}

Exercise 11

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

class Programmer implements Comparable<Programmer>{
    private int level;
    private String name;
    public Programmer(int lev,String name){
        level=lev;
        this.name=name;
    }
    public int getLevel(){return level;}
    public int compareTo(Programmer p){
        return level-p.getLevel();
    }
    public String toString(){return "Lev "+level+"   >>>    "+name;}
}

class ProGen implements Generator<Programmer>{
    Random levRand=new Random();
    Generator<java.lang.String> nameRand=new RandomGenerator.String();
    public Programmer next(){
        return new Programmer(levRand.nextInt(10),nameRand.next());
    }
}

public class Exercise11{
    public static void main(String[] args){
        Queue<Programmer> microsoft=new PriorityQueue<Programmer>();
        Generator<Programmer> gen=new ProGen();

        for(int i=0;i<10;i++){
            microsoft.offer(gen.next());
        }
        System.out.println(microsoft);

        int num=microsoft.size();
        for(int i=0;i<num;i++){
            System.out.println(microsoft.poll());
        }
    }
}

Exercise 12

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

class AssociativeArray<K,V> {
    private Object[][] pairs;
    private int index;
    public AssociativeArray(int length) {
        pairs = new Object[length][2];
    }
    public void put(K key, V value) {
        if(index >= pairs.length)
            throw new ArrayIndexOutOfBoundsException();
        pairs[index++] = new Object[]{ key, value };
    }
    @SuppressWarnings("unchecked")
    public V get(K key) {
        for(int i = 0; i < index; i++)
            if(key.equals(pairs[i][0]))
                return (V)pairs[i][1];
        return null; // Did not find key
    }
    public String toString() {
        StringBuilder result = new StringBuilder();
        for(int i = 0; i < index; i++) {
            result.append(pairs[i][0].toString());
            result.append(" : ");
            result.append(pairs[i][1].toString());
            if(i < index - 1)
                result.append("\n");
        }
        return result.toString();
    }
}


public class Exercise12{

    public static void test(Map<String,String> map){
        map.put("sky", "blue");
        map.put("grass", "green");
        map.put("ocean", "dancing");
        map.put("tree", "tall");
        map.put("earth", "brown");
        map.put("sun", "warm");
        try {
            map.put("extra", "object"); // Past the end
        } catch(ArrayIndexOutOfBoundsException e) {
            System.out.println("Too many objects!");
        }
        System.out.println(map);
        System.out.println(map.get("ocean"));
    }

    public static void main(String[] args){
        //AssociativeArray<String,String> map1 = new AssociativeArray<String,String>(6);
        HashMap<String,String> map2=new HashMap<String,String>();
        TreeMap<String,String> map3=new TreeMap<String,String>();
        LinkedHashMap<String,String> map4=new LinkedHashMap<String,String>();

        Exercise12.test(map2);
        Exercise12.test(map3);
        Exercise12.test(map4);
    }
}

Exercise 13

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

public class Exercise13{

    public static Map<String,Integer> wordsFreq(String address){
        HashMap<String,Integer> dic=new HashMap<String,Integer>();

        //读文件
        try{
            BufferedReader br=new BufferedReader(new FileReader(new File(address)));
            //割词
            String line=br.readLine();
            while(line!=null){
                String[] words=line.split("[\\p{Punct}\\s]+");
                addWords(words,dic);
                line=br.readLine();
            }
        }catch(Exception e){
            System.out.println(e);
        }

        return dic;
    }

    public static void addWords(String[] words, Map<String,Integer> map){
        for(String word:words){
            if(map.containsKey(word)){
                map.put(word,map.get(word)+1);
            }else{
                map.put(word,1);
            }
        }
    }

    public static void main(String[] args){
        Map<String,Integer> map=Exercise13.wordsFreq("/Users/Wei/java/com/ciaoshen/thinkinjava/chapter17/Text.txt");
        System.out.println(map);
    }
}

Exercise 14

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

public class Exercise14{
    public static void printKeys(Map<Object,Object> 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<Object,Object> map) {
        System.out.println(map.getClass().getSimpleName());
        // Map has ‘Set’ behavior for keys:
        map.putAll(new CountingMapData(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 = (Integer)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){
        test(new Properties());
    }
}

Exercise 15

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

public class SlowMap<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;
    }

    private static 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 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; }
    }

    public static void main(String[] args) {
        SlowMap<String,String> m= new SlowMap<String,String>();
        m.putAll(MyCountries.capitals(15));
        System.out.println(m);
        System.out.println(m.get("BULGARIA"));
        System.out.println(m.entrySet());
    }
}
Exercise15.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import java.io.*;

public class Exercise15{

    public static Map<String,Integer> wordsFreq(String address){
        SlowMap<String,Integer> dic=new SlowMap<String,Integer>();

        try{
            //读文件
            BufferedReader br=new BufferedReader(new FileReader(new File(address)));
            //割词
            String line=br.readLine();
            while(line!=null){
                String[] words=line.split("[\\p{Punct}\\s]+");
                addWords(words,dic);
                line=br.readLine();
            }
        }catch(Exception e){
            System.out.println(e);
        }

        return dic;
    }

    public static void addWords(String[] words, Map<String,Integer> map){
        for(String word:words){
            if(map.containsKey(word)){
                map.put(word,map.get(word)+1);
            }else{
                map.put(word,1);
            }
        }
    }

    public static void main(String[] args){
        Map<String,Integer> map=Exercise13.wordsFreq("/Users/Wei/java/com/ciaoshen/thinkinjava/chapter17/Text.txt");
        System.out.println(map);
    }
}

Exercise 16

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

public class SlowMap<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);
                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());}
    }


    public static void main(String[] args) {
        SlowMap<String,String> m= new SlowMap<String,String>();
        m.putAll(MyCountries.capitals(15));
        System.out.println(m);
        System.out.println(m.get("BULGARIA"));
        System.out.println(m.entrySet());
    }
}
MapEntry.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;

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 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; }
}
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) {
    }
}
Exercise16.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;

public class Exercise16{
    public static void main(String[] args){
        Maps.test(new SlowMap<Integer,String>());
    }
}

Exercise 17

大部分不需要实现,AbstractMap都实现了。

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

public class SlowMap<K,V> extends AbstractMap<K,V> implements Map<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);
                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());}
    }

    /**
     *  不需要实现,AbstractMap都实现了。
     */

    //Removes all of the mappings from this map (optional operation).
    //void clear()

    //Returns true if this map contains a mapping for the specified key.
    //boolean containsKey(Object key)

    //Returns true if this map maps one or more keys to the specified value.
    //boolean containsValue(Object value)

    //Compares the specified object with this map for equality.
    //boolean equals(Object o)

    //Returns the hash code value for this map.
    //int hashCode()

    //Returns true if this map contains no key-value mappings.
    //boolean isEmpty()

    //Returns a Set view of the keys contained in this map.
    //Set<K> keySet()

    // Copies all of the mappings from the specified map to this map (optional operation).
    //void putAll(Map<? extends K,? extends V> m)

    //Removes the mapping for a key from this map if it is present (optional operation).
    //V remove(Object key)

    //Returns the number of key-value mappings in this map.
    //int size()

    //Returns a Collection view of the values contained in this map.
    //Collection<V> values()


    public static void main(String[] args) {
        SlowMap<String,String> m= new SlowMap<String,String>();
        m.putAll(MyCountries.capitals(15));
        System.out.println(m);
        System.out.println(m.get("BULGARIA"));
        System.out.println(m.entrySet());
    }
}
MapEntry.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;

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; }
}
Exercise17.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;

public class Exercise17{
    public static void main(String[] args){
        Maps.test(new SlowMapComplete<Integer,String>());
    }
}

Exercise 18

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

public class SlowSet<E> extends AbstractSet<E>{
    private List<E> list=new ArrayList<E>();

    public SlowSet(){}
    public SlowSet(Collection<E> c){list=new ArrayList<E>(c);}

    public boolean add(E element){
        return list.add(element);
    }
    public int size(){return list.size();}
    public Iterator<E> iterator(){return new Ite();}

    private class Ite implements Iterator<E>{
        int index=0;
        public boolean hasNext(){return index<list.size();}
        public E next(){return list.get(index++);}
        public void remove(){
            if(index>0){
                list.remove(index-1);
            }
        }
    }

    public static void main(String[] args){
        SlowSet<String> set=new SlowSet<String>();
        RandomGenerator.String gen=new RandomGenerator.String();

        String s=null;
        String no3=null;
        String no7=null;
        for(int i=0;i<10;i++){
            s=gen.next();
            if(i==2){no3=s;}
            if(i==6){no7=s;}
            set.add(s);
        }
        System.out.println(set);
        System.out.println("Set contains ELement "+no3+"    >>>"+set.contains(no3));
        set.remove(no7);
        System.out.println("After delete Element "+no7+"   >>>"+set);
        System.out.println("Size    >>>"+set.size());
        String[] ss=(String[])(set.toArray());
        System.out.println("Arrays  >>>"+Arrays.toString(ss));
        set.clear();
        System.out.println("Delete All Element!!!");
        System.out.println("Set is Empty now?   >>>"+set.isEmpty());
        System.out.println(set);
    }
}

Exercise 19

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

public class Exercise19{

    public static Map<String,Integer> wordsFreq(String address){
        SimpleHashMap<String,Integer> dic=new SimpleHashMap<String,Integer>();

        try{
            //读文件
            BufferedReader br=new BufferedReader(new FileReader(new File(address)));
            //割词
            String line=br.readLine();
            while(line!=null){
                String[] words=line.split("[\\p{Punct}\\s]+");
                addWords(words,dic);
                line=br.readLine();
            }
        }catch(Exception e){
            System.out.println(e);
        }

        return dic;
    }

    public static void addWords(String[] words, Map<String,Integer> map){
        for(String word:words){
            if(map.containsKey(word)){
                map.put(word,map.get(word)+1);
            }else{
                map.put(word,1);
            }
        }
    }

    public static void main(String[] args){
        Map<String,Integer> map=Exercise19.wordsFreq("/Users/Wei/java/com/ciaoshen/thinkinjava/chapter17/Text.txt");
        System.out.println(map);
    }
}
SimpleHashMap.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;

public class SimpleHashMap<K,V> extends AbstractMap<K,V> {
    // Choose a prime number for the hash table
    // size, to achieve a uniform distribution:
    static final int SIZE = 997;
    // You can’t have a physical array of generics,
    // but you can upcast to one:
    @SuppressWarnings(value={"unchecked","rawtypes"})
    LinkedList<MapEntry<K,V>>[] buckets =
    new LinkedList[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 LinkedList<MapEntry<K,V>>();
        LinkedList<MapEntry<K,V>> bucket = buckets[index];
        MapEntry<K,V> pair = new MapEntry<K,V>(key, value);
        boolean found = false;
        ListIterator<MapEntry<K,V>> it = bucket.listIterator();
        while(it.hasNext()) {
            MapEntry<K,V> iPair = it.next();
            if(iPair.getKey().equals(key)) {
                oldValue = iPair.getValue();
                it.set(pair); // Replace old with new
                found = true;
                break;
            }
        }
        if(!found)
            buckets[index].add(pair);
        return oldValue;
    }
    public V get(Object key) {
        int index = Math.abs(key.hashCode()) % SIZE;
        if(buckets[index] == null) return null;
        for(MapEntry<K,V> iPair : buckets[index])
            if(iPair.getKey().equals(key))
                return iPair.getValue();
        return null;
    }
    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> set= new HashSet<Map.Entry<K,V>>();
        for(LinkedList<MapEntry<K,V>> bucket : buckets) {
            if(bucket == null) continue;
            for(MapEntry<K,V> mpair : bucket)
                set.add(mpair);
        }
        return set;
    }
    public static void main(String[] args) {
        SimpleHashMap<String,String> m =
        new SimpleHashMap<String,String>();
        m.putAll(Countries.capitals(25));
        System.out.println(m);
        System.out.println(m.get("ERITREA"));
        System.out.println(m.entrySet());
    }
}
MapEntry.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;


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; }
}

Exercise 20

只要在SimpleHashMap的put()方法里当找到相同键值的时候,加一个打印语句。

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

public class SimpleHashMap20<K,V> extends AbstractMap<K,V> {
    // Choose a prime number for the hash table
    // size, to achieve a uniform distribution:
    static final int SIZE = 997;
    // You can’t have a physical array of generics,
    // but you can upcast to one:
    @SuppressWarnings(value={"unchecked","rawtypes"})
    LinkedList<MapEntry<K,V>>[] buckets =
    new LinkedList[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 LinkedList<MapEntry<K,V>>();
        LinkedList<MapEntry<K,V>> bucket = buckets[index];
        MapEntry<K,V> pair = new MapEntry<K,V>(key, value);
        boolean found = false;
        ListIterator<MapEntry<K,V>> it = bucket.listIterator();
        while(it.hasNext()) {
            MapEntry<K,V> iPair = it.next();
            if(iPair.getKey().equals(key)) {
                System.out.println("Word >>>["+iPair.getKey()+"]<<< already existe!   Frequence:  "+iPair.getValue()+"    >>> "+value);
                oldValue = iPair.getValue();
                it.set(pair); // Replace old with new
                found = true;
                break;
            }
        }
        if(!found)
            buckets[index].add(pair);
        return oldValue;
    }
    public V get(Object key) {
        int index = Math.abs(key.hashCode()) % SIZE;
        if(buckets[index] == null) return null;
        for(MapEntry<K,V> iPair : buckets[index])
            if(iPair.getKey().equals(key))
                return iPair.getValue();
        return null;
    }
    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> set= new HashSet<Map.Entry<K,V>>();
        for(LinkedList<MapEntry<K,V>> bucket : buckets) {
            if(bucket == null) continue;
            for(MapEntry<K,V> mpair : bucket)
                set.add(mpair);
        }
        return set;
    }
    public static void main(String[] args) {
        SimpleHashMap20<String,String> m = new SimpleHashMap20<String,String>();
        m.putAll(Countries.capitals(25));
        System.out.println(m);
        System.out.println(m.get("ERITREA"));
        System.out.println(m.entrySet());
    }
}
MapEntry.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;


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; }
}
Exercise20.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import java.io.*;

public class Exercise20{

    public static Map<String,Integer> wordsFreq(String address){
        SimpleHashMap20<String,Integer> dic=new SimpleHashMap20<String,Integer>();

        try{
            //读文件
            BufferedReader br=new BufferedReader(new FileReader(new File(address)));
            //割词
            String line=br.readLine();
            while(line!=null){
                String[] words=line.split("[\\p{Punct}\\s]+");
                addWords(words,dic);
                line=br.readLine();
            }
        }catch(Exception e){
            System.out.println(e);
        }

        return dic;
    }

    public static void addWords(String[] words, Map<String,Integer> map){
        for(String word:words){
            if(map.containsKey(word)){
                map.put(word,map.get(word)+1);
            }else{
                map.put(word,1);
            }
        }
    }

    public static void main(String[] args){
        Map<String,Integer> map=Exercise20.wordsFreq("/Users/Wei/java/com/ciaoshen/thinkinjava/chapter17/Text.txt");
        System.out.println(map);
    }
}

Exercise 21

SimpleHashMap21.java
/**
 * SimpleHashMap in the book
 */
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;

public class SimpleHashMap21<K,V> extends AbstractMap<K,V> {
    // Choose a prime number for the hash table
    // size, to achieve a uniform distribution:
    static final int SIZE = 997;
    // You can’t have a physical array of generics,
    // but you can upcast to one:
    @SuppressWarnings(value={"unchecked","rawtypes"})
    LinkedList<MapEntry<K,V>>[] buckets =
    new LinkedList[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 LinkedList<MapEntry<K,V>>();
        LinkedList<MapEntry<K,V>> bucket = buckets[index];
        MapEntry<K,V> pair = new MapEntry<K,V>(key, value);
        boolean found = false;
        ListIterator<MapEntry<K,V>> it = bucket.listIterator();
        int place=-1;
        while(it.hasNext()) {
            place++;
            MapEntry<K,V> iPair = it.next();
            if(iPair.getKey().equals(key)) {
                System.out.println("Word >>>["+iPair.getKey()+"]<<< already existe at place "+place+" in LinkedList!   Frequence:  "+iPair.getValue()+"    >>> "+value);
                oldValue = iPair.getValue();
                it.set(pair); // Replace old with new
                found = true;
                break;
            }
        }
        if(!found)
            buckets[index].add(pair);
        return oldValue;
    }
    public V get(Object key) {
        int index = Math.abs(key.hashCode()) % SIZE;
        if(buckets[index] == null) return null;
        for(MapEntry<K,V> iPair : buckets[index])
            if(iPair.getKey().equals(key))
                return iPair.getValue();
        return null;
    }
    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> set= new HashSet<Map.Entry<K,V>>();
        for(LinkedList<MapEntry<K,V>> bucket : buckets) {
            if(bucket == null) continue;
            for(MapEntry<K,V> mpair : bucket)
                set.add(mpair);
        }
        return set;
    }
    public static void main(String[] args) {
        SimpleHashMap21<String,String> m = new SimpleHashMap21<String,String>();
        m.putAll(Countries.capitals(25));
        System.out.println(m);
        System.out.println(m.get("ERITREA"));
        System.out.println(m.entrySet());
    }
}
MapEntry.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;


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; }
}
Exercise21.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import java.io.*;

public class Exercise21{

    public static Map<String,Integer> wordsFreq(String address){
        SimpleHashMap21<String,Integer> dic=new SimpleHashMap21<String,Integer>();

        try{
            //读文件
            BufferedReader br=new BufferedReader(new FileReader(new File(address)));
            //割词
            String line=br.readLine();
            while(line!=null){
                String[] words=line.split("[\\p{Punct}\\s]+");
                addWords(words,dic);
                line=br.readLine();
            }
        }catch(Exception e){
            System.out.println(e);
        }

        return dic;
    }

    public static void addWords(String[] words, Map<String,Integer> map){
        for(String word:words){
            if(map.containsKey(word)){
                map.put(word,map.get(word)+1);
            }else{
                map.put(word,1);
            }
        }
    }

    public static void main(String[] args){
        Map<String,Integer> map=Exercise21.wordsFreq("/Users/Wei/java/com/ciaoshen/thinkinjava/chapter17/Text.txt");
        System.out.println(map);
    }
}

Exercise 22

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

public class SimpleHashMap22<K,V> extends AbstractMap<K,V> {
    // Choose a prime number for the hash table
    // size, to achieve a uniform distribution:
    static final int SIZE = 997;
    // You can’t have a physical array of generics,
    // but you can upcast to one:
    @SuppressWarnings(value={"unchecked","rawtypes"})
    LinkedList<MapEntry<K,V>>[] buckets =
    new LinkedList[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 LinkedList<MapEntry<K,V>>();
        LinkedList<MapEntry<K,V>> bucket = buckets[index];
        MapEntry<K,V> pair = new MapEntry<K,V>(key, value);
        boolean found = false;
        ListIterator<MapEntry<K,V>> it = bucket.listIterator();
        int place=-1;
        while(it.hasNext()) {
            place++;
            MapEntry<K,V> iPair = it.next();
            if(iPair.getKey().equals(key)) {
                System.out.println("Word >>>["+iPair.getKey()+"]<<< already existe at place "+place+" in LinkedList!   Frequence:  "+iPair.getValue()+"    >>> "+value);
                oldValue = iPair.getValue();
                it.set(pair); // Replace old with new
                found = true;
                break;
            }
        }
        if(!found)
            buckets[index].add(pair);
        return oldValue;
    }
    public V get(Object key) {
        int index = Math.abs(key.hashCode()) % SIZE;
        if(buckets[index] == null) return null;
        for(MapEntry<K,V> iPair : buckets[index])
            if(iPair.getKey().equals(key))
                return iPair.getValue();
        return null;
    }
    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> set= new HashSet<Map.Entry<K,V>>();
        for(LinkedList<MapEntry<K,V>> bucket : buckets) {
            if(bucket == null) continue;
            for(MapEntry<K,V> mpair : bucket)
                set.add(mpair);
        }
        return set;
    }
    public void clear(){
        entrySet().clear();
    }
    public V remove(Object o){
        V v=null;
        for(LinkedList<MapEntry<K,V>> bucket:buckets){
            if(bucket!=null && !bucket.isEmpty()){
                for(MapEntry<K,V> entry:bucket){
                    if(entry.getKey().equals(o)){
                        v=entry.getValue();
                        bucket.remove(entry);
                    }
                }
            }
        }
        return v;
    }

    public static void main(String[] args) {
        SimpleHashMap22<String,String> m = new SimpleHashMap22<String,String>();
        m.putAll(Countries.capitals(25));
        System.out.println(m);
        System.out.println(m.get("ERITREA"));
        System.out.println(m.entrySet());
    }
}
MapEntry.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;


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; }
}
Exercise22.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import java.io.*;

public class Exercise22{

    public static Map<String,Integer> wordsFreq(String address){
        SimpleHashMap22<String,Integer> dic=new SimpleHashMap22<String,Integer>();

        try{
            //读文件
            BufferedReader br=new BufferedReader(new FileReader(new File(address)));
            //割词
            String line=br.readLine();
            while(line!=null){
                String[] words=line.split("[\\p{Punct}\\s]+");
                addWords(words,dic);
                line=br.readLine();
            }
        }catch(Exception e){
            System.out.println(e);
        }

        return dic;
    }

    public static void addWords(String[] words, Map<String,Integer> map){
        for(String word:words){
            if(map.containsKey(word)){
                map.put(word,map.get(word)+1);
            }else{
                map.put(word,1);
            }
        }
    }

    public static void main(String[] args){
        Map<String,Integer> map=Exercise22.wordsFreq("/Users/Wei/java/com/ciaoshen/thinkinjava/chapter17/Text.txt");
        System.out.println(map);

        System.out.println("the >>>"+map.remove("the"));

        System.out.println(map);
    }
}

Exercise 23

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

public class SimpleHashMap23<K,V> extends AbstractMap<K,V> {
    // Choose a prime number for the hash table
    // size, to achieve a uniform distribution:
    static final int SIZE = 997;
    // You can’t have a physical array of generics,
    // but you can upcast to one:
    @SuppressWarnings(value={"unchecked","rawtypes"})
    LinkedList<MapEntry<K,V>>[] buckets = new LinkedList[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 LinkedList<MapEntry<K,V>>();
        LinkedList<MapEntry<K,V>> bucket = buckets[index];
        MapEntry<K,V> pair = new MapEntry<K,V>(key, value);
        boolean found = false;
        ListIterator<MapEntry<K,V>> it = bucket.listIterator();
        int place=-1;
        while(it.hasNext()) {
            place++;
            MapEntry<K,V> iPair = it.next();
            if(iPair.getKey().equals(key)) {
                System.out.println("Word >>>["+iPair.getKey()+"]<<< already existe at place "+place+" in LinkedList!   Frequence:  "+iPair.getValue()+"    >>> "+value);
                oldValue = iPair.getValue();
                it.set(pair); // Replace old with new
                found = true;
                break;
            }
        }
        if(!found)
            buckets[index].add(pair);
        return oldValue;
    }
    public V get(Object key) {
        int index = Math.abs(key.hashCode()) % SIZE;
        if(buckets[index] == null) return null;
        for(MapEntry<K,V> iPair : buckets[index])
            if(iPair.getKey().equals(key))
                return iPair.getValue();
        return null;
    }
    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> set= new HashSet<Map.Entry<K,V>>();
        for(LinkedList<MapEntry<K,V>> bucket : buckets) {
            if(bucket == null) continue;
            for(MapEntry<K,V> mpair : bucket)
                set.add(mpair);
        }
        return set;
    }
    public void clear(){
        entrySet().clear();
    }
    public V remove(Object o){
        V v=null;
        for(LinkedList<MapEntry<K,V>> bucket:buckets){
            if(bucket!=null && !bucket.isEmpty()){
                for(MapEntry<K,V> entry:bucket){
                    if(entry.getKey().equals(o)){
                        v=entry.getValue();
                        bucket.remove(entry);
                    }
                }
            }
        }
        return v;
    }

    //Returns true if this map contains a mapping for the specified key.
    public boolean containsKey(Object key){
        Set<K> keys=keySet();
        return keys.contains(key);
    }

    //Returns true if this map maps one or more keys to the specified value.
    public boolean containsValue(Object value){
        Collection<V> values=values();
        return values.contains(value);
    }

    //Compares the specified object with this map for equality.
    public boolean equals(Object o){
        if(!(o instanceof SimpleHashMap23)){
            return false;
        }
        if(this.buckets.length!=((SimpleHashMap23)o).buckets.length){
            return false;
        }
        for(int i=0;i<this.buckets.length;i++){
            if(!this.buckets[i].equals(((SimpleHashMap23)o).buckets[i])){
                return false;
            }
        }
        return true;
    }

    //Returns the hash code value for this map.
    public int hashCode(){
        int hash=37*SIZE;
        int index=0;
        for(LinkedList<MapEntry<K,V>> bucket:buckets){
            if(bucket!=null && !bucket.isEmpty()){
                for(MapEntry<K,V> entry:bucket){
                    index++;
                    hash=hash+37*index*entry.hashCode();
                }
            }
        }
        return hash;
    }

    //Returns true if this map contains no key-value mappings.
    public boolean isEmpty(){
        return entrySet().isEmpty();
    }

    //Returns a Set view of the keys contained in this map.
    public Set<K> keySet(){
        Set<K> keys=new LinkedHashSet<K>();
        Set<Map.Entry<K,V>> set=entrySet();
        for(Map.Entry<K,V> entry:set){
            keys.add(entry.getKey());
        }
        return keys;
    }

    //Copies all of the mappings from the specified map to this map (optional operation).
    @SuppressWarnings(value={"rawtypes","unchecked"})
    public void putAll(Map<? extends K,? extends V> m){
        for(Map.Entry entry:m.entrySet()){
            put((K)entry.getKey(),(V)entry.getValue());
        }
    }

    //Returns the number of key-value mappings in this map.
    public int size(){
        return entrySet().size();
    }

    //Returns a Collection view of the values contained in this map.
    public Collection<V> values(){
        Collection<V> values=new ArrayList<V>();
        Set<Map.Entry<K,V>> set=entrySet();
        for(Map.Entry<K,V> entry:set){
            values.add(entry.getValue());
        }
        return values;
    }

    public static void main(String[] args) {
        SimpleHashMap23<String,String> m = new SimpleHashMap23<String,String>();
        m.putAll(Countries.capitals(25));
        System.out.println(m);
        System.out.println(m.get("ERITREA"));
        System.out.println(m.entrySet());
    }
}
MapEntry.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;


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; }
}
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) {
    }
}
CountingMapData.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;

public class CountingMapData extends AbstractMap<Integer,String> {
    private int size;
    private static String[] chars = "A B C D E F G H I J K L M N O P Q R S T U V W X Y Z".split(" ");
    public CountingMapData(int size) {
        if(size < 0) this.size = 0;
        this.size = size;
    }
    private static class Entry implements Map.Entry<Integer,String> {
        int index;
        Entry(int index) { this.index = index; }
        public boolean equals(Object o) {
            return Integer.valueOf(index).equals(o);
        }
        public Integer getKey() { return index; }
        public String getValue() {
            return chars[index % chars.length] + Integer.toString(index / chars.length);
        }
        public String setValue(String value) {
            throw new UnsupportedOperationException();
        }
        public int hashCode() {
            return Integer.valueOf(index).hashCode();
        }
    }

    private static class EntrySet extends AbstractSet<Map.Entry<Integer,String>> {
        private int size;
        public EntrySet(int size){
            this.size=size;
        }
        public int size(){return size;}

        private class Iter implements Iterator<Map.Entry<Integer,String>>{
            int index=0;
            public boolean hasNext(){
                return index<size;
            }
            public Map.Entry<Integer,String> next(){
                return new Entry(index++);
            }
            public void remove(){
                throw new UnsupportedOperationException();
            }
        }

        public Iterator<Map.Entry<Integer,String>> iterator(){
            return new Iter();
        }
    }
    public Set<Map.Entry<Integer,String>> entrySet() {
        return new EntrySet(size);
    }

    public static void main(String[] args) {
        System.out.println(new CountingMapData(60));
    }
}
Exercise23.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import java.io.*;

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

Exercise 24

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

public class SimpleHashSet<E> extends AbstractSet<E> implements Set<E>{
    private static final int SIZE=1024;
    @SuppressWarnings(value={"unchecked","rawtypes"})
    private LinkedList<E>[] buckets=new LinkedList[SIZE];

    private class Ite implements Iterator<E>{
        private int index=-1;
        LinkedList<E> bucket=null;
        Iterator<E> ite=null;
        E previous=null;

        public boolean hasNext(){
            if(ite!=null && ite.hasNext()){
                return true;
            }

            int ranger=index;
            while(++ranger<SIZE){
                if(buckets[ranger]!=null){
                    return true;
                }
            }
            return false;
        }

        public E next(){
            if(ite!=null && ite.hasNext()){
                previous=ite.next();
                return previous;
            }
            while(++index<SIZE){
                if(buckets[index]!=null){
                    ite=buckets[index].iterator();
                    previous=ite.next();
                    return previous;
                }
            }
            return null;
        }

        public void remove(){
            if(previous!=null){
                buckets[index].remove(previous);
                previous=null;
                if(buckets[index].isEmpty()){
                    buckets[index]=null;
                }
            }
        }
    }

    public Iterator<E> iterator(){return new Ite();}

    public boolean add(E e){
        int hash=e.hashCode();
        int ticket=Math.abs(hash)%SIZE;
        if(buckets[ticket]!=null){
            if(!buckets[ticket].contains(e)){
                buckets[ticket].add(e);
                return true;
            }else{
                return false;
            }
        }else{
            buckets[ticket]=new LinkedList<E>();
            buckets[ticket].add(e);
            return true;
        }
    }

    public int size(){
        int size=0;
        Iterator<E> ite=iterator();
        while(ite.hasNext()){
            ite.next();
            size++;
        }
        return size;
    }

    /*******
     *  AbstractSet已实现部分
     *******/

    //public int hashCode()


    //public boolean equals(Object o)


    //public boolean removeAll(Collection<?> c)



    /*******
     *  AbstractCollection已实现部分
     *******/

    //public boolean addAll(Collection<? extends E> c)

    //public void clear()

    //public boolean contains(Object o)

    //public boolean containsAll(Collection<?> c)

    //public boolean isEmpty()

    //public boolean remove(Object o)

    //public boolean retainAll(Collection<?> c)

    //public Object[] toArray()

    //public <T> T[] toArray(T[] a)

    public static void main(String[] args){

    }
}
Sets.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import java.lang.reflect.*;


public class Sets{

    public static <E> void test(Set<E> set1, Set<E> set2){

        System.out.println();
        System.out.println(">>>Set1<<<");
        System.out.println("Class Name  >>> "+set1.getClass().getName());
        System.out.println("Size    >>> "+set1.size());
        System.out.println(set1);

        System.out.println();
        System.out.println(">>>Set2<<<");
        System.out.println("Class Name  >>> "+set2.getClass().getName());
        System.out.println("Size    >>> "+set2.size());
        System.out.println(set2);


        System.out.println();
        System.out.println("Set1 equals Set1?   >>> "+set1.equals(set1));
        System.out.println("Set1 equals Set2?   >>> "+set1.equals(set2));
        System.out.println("Set1 hash code = "+set1.hashCode());
        System.out.println("Set2 hash code = "+set2.hashCode());


        System.out.println();
        set1.addAll(set2);
        System.out.println("Union of Set1 and Set2  >>> "+set1);
        System.out.println("Size    >>>  "+set1.size());

        System.out.println("Set1 contains XXXXXX?  "+set1.contains("XXXXXX"));
        Iterator<E> ite=set1.iterator();
        for(int i=0;i<(set1.size()/2-1);i++){
            ite.next();
        }
        E mid=ite.next();

        System.out.println("Middle Element  >>> "+mid);
        set1.remove(mid);
        System.out.println("After removing Middle Element   >>> "+set1);
    }

    public static void main(String[] args){
        Set<String> set1=new LinkedHashSet<String>();
        Set<String> set2=new LinkedHashSet<String>();
        RandomGenerator.String gen=new RandomGenerator.String(1);
        for(int i=0;i<20;i++){
            set1.add(gen.next());
            set2.add(gen.next());
        }
        Sets.test(set1,set2);
    }
}
Exercise24.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import java.io.*;

public class Exercise24{
    public static void main(String[] args){
        Set<String> set1=new SimpleHashSet<String>();
        Set<String> set2=new SimpleHashSet<String>();
        RandomGenerator.String gen=new RandomGenerator.String();
        for(int i=0;i<20;i++){
            set1.add(gen.next());
            set2.add(gen.next());
        }
        Sets.test(set1,set2);
    }
}

Exercise 25

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

这个山寨HashMap的关键点在于对接口的把握:Map接口里的entrySet()是明确面向Map.Entry的。其他方法可以直接面向LinkedMapEntryV2。而LinkedMapEntryV2的功能比Map接口强很多。

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);
    }
}

Exercise 26

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

public class EntryPair<X,Y>{
    private X x;
    private Y y;

    public EntryPair(X inX, Y inY){x=inX; y=inY;}
    public X getX(){return x;}
    public Y getY(){return y;}
    public X setX(X inX){X oldX=x; x=inX; return oldX;}
    public Y setY(Y inY){Y oldY=y; y=inY; return oldY;}

    @SuppressWarnings("unchecked")
    public boolean equals(Object o){return x.equals(((EntryPair<X,Y>)o).getX()) && y.equals(((EntryPair<X,Y>)o).getY());}
    public int hashCode(){return (x==null? 0:x.hashCode()) ^ (y==null? 0:y.hashCode());}
}
CountedString.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;

public class CountedString {
    private static List<EntryPair<Character,String>> created = new ArrayList<EntryPair<Character,String>>();
    private char type;
    private String s;
    private int id = 0;
    public CountedString(char c, String str) {
        type=c;
        s=str;
        EntryPair<Character,String> newEntry=new EntryPair<Character,String>(c,str);
        created.add(newEntry);
        for(EntryPair<Character,String> entry : created){
            if(entry.equals(newEntry)){
                id++;
            }
        }
    }
    public String toString() {
        return "Type: " + type + " String: " + s + " id: " + id + " hashCode(): " + hashCode();
    }
    public int hashCode() {
        int result = 17;
        result = 37 * result + ((Character)type).hashCode();
        result = 37 * result + s.hashCode();
        result = 37 * result + id;
        return result;
    }

    @SuppressWarnings("unchecked")
    public boolean equals(Object o) {
        return o instanceof CountedString &&
        s.equals(((CountedString)o).s) &&
        ((Character)type).equals(((CountedString)o).type) &&
        id == ((CountedString)o).id;
    }
}
Exercise26.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import java.io.*;

public class Exercise26{
    public static void main(String[] args) {
        Map<CountedString,Integer> map = new HashMap<CountedString,Integer>();
        CountedString[] cs = new CountedString[5];
        for(int i = 0; i < cs.length; i++) {
            cs[i] = new CountedString('A',"hi");
            map.put(cs[i], i); // Autobox int -> Integer
        }
        System.out.println(map);
        for(CountedString cstring : cs) {
            System.out.println("Looking up " + cstring);
            System.out.println(map.get(cstring));
        }
    }
}

Exercise 27

但还是存在一定问题:不同的对象,在HashMap里有同样的键值。也就是,部分对象会被其他不同的对象替换掉,因为有相同的键值。练习中,下面4个不同的对象,拥有相同的散列值。

导致前三个对象的信息会丢失,被后面相同散列值的对象覆盖。但如果这就是设计者的用意,那么就不成问题。

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

public class EntryPair<X,Y>{
    private X x;
    private Y y;

    public EntryPair(X inX, Y inY){x=inX; y=inY;}
    public X getX(){return x;}
    public Y getY(){return y;}
    public X setX(X inX){X oldX=x; x=inX; return oldX;}
    public Y setY(Y inY){Y oldY=y; y=inY; return oldY;}

    @SuppressWarnings("unchecked")
    public boolean equals(Object o){return x.equals(((EntryPair<X,Y>)o).getX()) && y.equals(((EntryPair<X,Y>)o).getY());}
    public int hashCode(){return (x==null? 0:x.hashCode()) ^ (y==null? 0:y.hashCode());}
}
CountedString27.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;

public class CountedString27 {
    private static List<EntryPair<Character,String>> created = new ArrayList<EntryPair<Character,String>>();
    private char type;
    private String s;
    private int id = 0;
    public CountedString27(char c, String str) {
        type=c;
        s=str;
        EntryPair<Character,String> newEntry=new EntryPair<Character,String>(c,str);
        created.add(newEntry);
        for(EntryPair<Character,String> entry : created){
            if(entry.equals(newEntry)){
                id++;
            }
        }
    }
    public String toString() {
        return "Type: " + type + " String: " + s + " id: " + id + " hashCode(): " + hashCode();
    }
    //hashCode()和id解绑
    public int hashCode() {
        int result = 17;
        result = 37 * result + ((Character)type).hashCode();
        result = 37 * result + s.hashCode();
        return result;
    }

    @SuppressWarnings("unchecked")
    public boolean equals(Object o) {
        return o instanceof CountedString27 &&
        s.equals(((CountedString27)o).s) &&
        ((Character)type).equals(((CountedString27)o).type);
    }
}
Exercise27.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import java.io.*;

public class Exercise27{
    public static void main(String[] args) {
        Map<CountedString27,Integer> map = new HashMap<CountedString27,Integer>();
        CountedString27[] cs = new CountedString27[5];
        for(int i = 0; i < cs.length; i++) {
            cs[i] = new CountedString27('A',"hi");
            map.put(cs[i], i); // Autobox int -> Integer
        }
        System.out.println(map);
        for(CountedString27 cstring : cs) {
            System.out.println("Looking up " + cstring);
            System.out.println(map.get(cstring));
        }
    }
}

Exercise 28

Tuple.java

这里实现的是Comparable接口。有一个缺点:高级的Tuple和低级的Tuple比较的时候,容易出Bug。

比如TupleFive和TupleTwo比较的时候,如果前两个元素相等,就会开始比较第三个元素。会调用TupleThree的compareTo()方法。就会把TupleTwo强制转型成TupleThree,会出ClassCastException。

所以只能拿低级的和高级的比,或者同级之间比较。

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

public class Tuple {

    public static class TwoTuple<A,B> extends Tuple implements Comparable<Tuple>{
        public final A first;
        public final B second;
        public TwoTuple(A a, B b) { first = a; second = b; }
        public String toString() {
            return "(" + first + ", " + second + ")";
        }
        @SuppressWarnings("unchecked")
        public boolean equals(Object o){
            return first.equals(((TwoTuple<A,B>)o).first) && second.equals(((TwoTuple<A,B>)o).second);
        }
        public int hashCode(){
            int hash=17;
            hash=37*hash+first.hashCode();
            hash=37*hash+second.hashCode();
            return hash;
        }
        @SuppressWarnings("unchecked")
        public int compareTo(Tuple t){
            if(((Comparable<A>)this.first).compareTo(((TwoTuple<A,B>)t).first)==0){
                return ((Comparable<B>)this.second).compareTo(((TwoTuple<A,B>)t).second);
            }else{
                return ((Comparable<A>)this.first).compareTo(((TwoTuple<A,B>)t).first);
            }
        }
    }

    public static class ThreeTuple<A,B,C> extends TwoTuple<A,B>{
        public final C third;
        public ThreeTuple(A a, B b, C c) {
            super(a, b);
            third = c;
        }
        public String toString() {
            return "(" + first + ", " + second + ", " + third +")";
        }
        @SuppressWarnings("unchecked")
        public boolean equals(Object o){
            return super.equals(o) && third.equals(((ThreeTuple<A,B,C>)o).third);
        }
        @Override
        public int hashCode(){
            int hash=super.hashCode();
            hash=37*hash+third.hashCode();
            return hash;
        }
        @SuppressWarnings("unchecked")
        public int compareTo(Tuple t){
            if(super.compareTo(((TwoTuple<A,B>)t))==0){
                return ((Comparable<C>)this.third).compareTo(((ThreeTuple<A,B,C>)t).third);
            }else{
                return super.compareTo((TwoTuple<A,B>)t);
            }
        }
    }

    public static class FourTuple<A,B,C,D> extends ThreeTuple<A,B,C>{
        public final D fourth;
        public FourTuple(A a, B b, C c, D d) {
            super(a, b, c);
            fourth = d;
        }
        public String toString() {
            return "(" + first + ", " + second + ", " +
            third + ", " + fourth + ")";
        }
        @SuppressWarnings("unchecked")
        public boolean equals(Object o){
            return super.equals(o) && fourth.equals(((FourTuple<A,B,C,D>)o).fourth);
        }
        @Override
        public int hashCode(){
            int hash=super.hashCode();
            hash=37*hash+fourth.hashCode();
            return hash;
        }
        @SuppressWarnings("unchecked")
        public int compareTo(Tuple t){
            if(super.compareTo(((ThreeTuple<A,B,C>)t))==0){
                return ((Comparable<D>)this.fourth).compareTo(((FourTuple<A,B,C,D>)t).fourth);
            }else{
                return super.compareTo((ThreeTuple<A,B,C>)t);
            }
        }
    }

    public static class FiveTuple<A,B,C,D,E> extends FourTuple<A,B,C,D> {
        public final E fifth;
        public FiveTuple(A a, B b, C c, D d, E e) {
            super(a, b, c, d);
            fifth = e;
        }
        public String toString() {
            return "(" + first + ", " + second + ", " +
            third + ", " + fourth + ", " + fifth + ")";
        }
        @SuppressWarnings("unchecked")
        public boolean equals(Object o){
            return super.equals(o) && fifth.equals(((FiveTuple<A,B,C,D,E>)o).fifth);
        }
        @Override
        public int hashCode(){
            int hash=super.hashCode();
            hash=37*hash+fifth.hashCode();
            return hash;
        }
        @SuppressWarnings("unchecked")
        public int compareTo(Tuple t){
            if(super.compareTo(((FourTuple<A,B,C,D>)t))==0){
                return ((Comparable<E>)this.fifth).compareTo(((FiveTuple<A,B,C,D,E>)t).fifth);
            }else{
                return super.compareTo((FourTuple<A,B,C,D>)t);
            }
        }
    }


    public static <A,B> Tuple.TwoTuple<A,B> tuple(A a, B b) {
        return new Tuple.TwoTuple<A,B>(a, b);
    }
    public static <A,B,C> Tuple.ThreeTuple<A,B,C> tuple(A a, B b, C c) {
        return new Tuple.ThreeTuple<A,B,C>(a, b, c);
    }
    public static <A,B,C,D> Tuple.FourTuple<A,B,C,D> tuple(A a, B b, C c, D d) {
        return new Tuple.FourTuple<A,B,C,D>(a, b, c, d);
    }
    public static <A,B,C,D,E> Tuple.FiveTuple<A,B,C,D,E> tuple(A a, B b, C c, D d, E e) {
        return new Tuple.FiveTuple<A,B,C,D,E>(a, b, c, d, e);
    }
}
Exercise28.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;

class Amphibian implements Comparable<Amphibian>{
    private String name;
    public Amphibian(String s){name=s;}
    public String toString(){return "Amphibian: "+name;}
    public int compareTo(Amphibian a){return name.compareTo(a.name);}
}
class Vehicle implements Comparable<Vehicle>{
    private String name;
    public Vehicle(String s){name=s;}
    public String toString(){return "Vehicle: "+name;}
    public int compareTo(Vehicle v){return name.compareTo(v.name);}
}

public class Exercise28{

    /**
     *  测试
     */
    static Tuple.TwoTuple<String,Integer> f() {
        return Tuple.tuple("hi", 47);
    }
    @SuppressWarnings("rawtypes")
    static Tuple.TwoTuple f2() { return Tuple.tuple("hi", 47); }
    static Tuple.ThreeTuple<Amphibian,String,Integer> g() {
        return Tuple.tuple(new Amphibian("AmphiToTo"), "hi", 47);
    }
    static Tuple.FourTuple<Vehicle,Amphibian,String,Integer> h() {
        return Tuple.tuple(new Vehicle("VehiJiJi"), new Amphibian("AmphiPaPa"), "hi", 47);
    }
    static Tuple.FiveTuple<Vehicle,Amphibian,String,Integer,Double> k() {
        return Tuple.tuple(new Vehicle("VehiBiuBiu"), new Amphibian("AmphiQQ"), "hi", 47, 11.1);
    }

    public static void main(String[] args) {
        Tuple.TwoTuple<String,Integer> ttsi = Exercise28.f();
        System.out.println(ttsi);
        System.out.println(Exercise28.f2());
        System.out.println(Exercise28.g());
        System.out.println(Exercise28.h());
        System.out.println(Exercise28.k());

        Set<Tuple.FiveTuple<Vehicle,Amphibian,String,Integer,Double>> set=new TreeSet<Tuple.FiveTuple<Vehicle,Amphibian,String,Integer,Double>>();

        set.add(Tuple.tuple(new Vehicle("VehiBiuBiu"), new Amphibian("AmphiQQ"), "hi", 47, 11.1));
        set.add(Tuple.tuple(new Vehicle("VehiBiuBiu"), new Amphibian("AmphiQQ"), "hi", 47, 111.1));
        set.add(Tuple.tuple(new Vehicle("VehiBiuBiu"), new Amphibian("AmphiQQ"), "hi", 1000, 5555.5));
        set.add(Tuple.tuple(new Vehicle("VehiBiuBiu"), new Amphibian("AmphiQQ"), "hello", 433, 1234.5));
        set.add(Tuple.tuple(new Vehicle("VehiBiuBiu"), new Amphibian("AmphiBMW"), "world", 9, 865.8));
        set.add(Tuple.tuple(new Vehicle("VehiGoogle"), new Amphibian("AmphiBenz"), "Java", 765, 11.1));
        System.out.println(set);
    }
}

package com.ciaoshen.thinkinjava.chapter17.testframework

练习29-33,依赖com.ciaoshen.thinkinjava.chapter17.testframework包中部分组件才能运行。这个包就是书中介绍的容器测试框架。具体组件如下:

Test.java
/**
 *  容器测试框架
 *  框架模块1:封装测试类
 */
package com.ciaoshen.thinkinjava.chapter17.testframework;
import java.util.*;

/**
 *  每种测试一个类
 *  有名字,有test()方法
 *  test()方法给个容器,给点参数就能运行
 */

public abstract class Test<C>{
    public String name;

    public Test(String name){this.name=name;}

    public abstract int test(C container, TestParam tp);
}
TestParam.java
/**
 *  容器测试框架
 *  框架模块2:封装测试参数。
 */
package com.ciaoshen.thinkinjava.chapter17.testframework;
import java.util.*;


/**
 *  TestParam类负责批量解析原始数据,生成参数包。
 *  每个参数包有两个参数:size-代表容器大小。loops-代表测试迭代次数。
 *  两个array()方法切割参数包。
 */

public class TestParam{
    public final int size;
    public final int loops;

    public TestParam(int size, int loops){
        this.size=size;
        this.loops=loops;
    }

    public static TestParam[] array(int... values){
        int size=values.length/2;
        TestParam[] result=new TestParam[size];
        int cursor=0;
        for(int i=0;i<size;i++){
            result[i]=new TestParam(values[cursor++],values[cursor++]);
        }
        return result;
    }

    public static TestParam[] array(String... values){
        int[] result=new int[values.length];
        for(int i=0;i<values.length;i++){
            result[i]=Integer.parseInt(values[i]);
        }
        return array(result);
    }
}
Tester.java
/**
 *  容器测试框架
 *  框架模块3:运行测试工具包。
 */
package com.ciaoshen.thinkinjava.chapter17.testframework;
import java.util.*;


/**
 *  Tester类是负责运行Test测试类的单元。
 *  用户调用run()方法。
 */

public class Tester<C> {

    /**
     *  构造函数
     */
    public Tester(C container, List<Test<C>> tests) {
        this.container = container;
        this.tests = tests;
        if(container != null)
            headline = container.getClass().getSimpleName();
    }
    public Tester(C container, List<Test<C>> tests,
                  TestParam[] paramList) {
        this(container, tests);
        this.paramList = paramList;
    }


    /**
     *  基本参数初始化相关域和方法
     */
    public static TestParam[] defaultParams= TestParam.array(10, 5000, 100, 5000, 1000, 5000, 10000, 500);
    private TestParam[] paramList = defaultParams;
    protected C container;
    private List<Test<C>> tests;
    protected C initialize(int size) { return container; }


    /**
     *  输出打印相关域和方法
     */
    private String headline = "";
    public static int fieldWidth = 8;
    private static int sizeWidth = 5;
    private static String sizeField = "%" + sizeWidth + "s";
    private static String stringField() {
        return "%" + fieldWidth + "s";
    }
    private static String numberField() {
        return "%" + fieldWidth + "d";
    }
    public void setHeadline(String newHeadline) {
        headline = newHeadline;
    }
    @SuppressWarnings("rawtypes")
    private void displayHeader() {
        int width = fieldWidth * tests.size() + sizeWidth;
        int dashLength = width - headline.length() - 1;
        StringBuilder head = new StringBuilder(width);
        for(int i = 0; i < dashLength/2; i++)
            head.append('-');
        head.append(' ');
        head.append(headline);
        head.append(' ');
        for(int i = 0; i < dashLength/2; i++)
            head.append('-');
        System.out.println(head);
        // Print column headers:
        System.out.format(sizeField, "size");
        for(Test test : tests)
            System.out.format(stringField(), test.name);
        System.out.println();
    }



    /**
     *  实际运行测试方法
     */
    public static <C> void run(C cntnr, List<Test<C>> tests){
        new Tester<C>(cntnr, tests).timedTest();
    }
    public static <C> void run(C cntnr, List<Test<C>> tests, TestParam[] paramList) {
        new Tester<C>(cntnr, tests, paramList).timedTest();
    }
    //最终执行者:对每组不同的参数配置,跑全套测试。
    public void timedTest() {
        displayHeader();
        for(TestParam param : paramList) {
            System.out.format(sizeField, param.size);
            for(Test<C> test : tests) {
                C kontainer = initialize(param.size);
                long start = System.nanoTime();
                // Call the overriden method:
                int reps = test.test(kontainer, param);
                long duration = System.nanoTime() - start;
                long timePerRep = duration / reps; // Nanoseconds
                System.out.format(numberField(), timePerRep);
            }
            System.out.println();
        }
    }
}

package com.ciaoshen.thinkinjava.chapter17.testframework.gen

练习29-33,也依赖com.ciaoshen.thinkinjava.chapter17.testframework.gen包中部分组件才能运行。gen包是用来自动生成测试用随机数据的工具包。具体组件如下:

Generator.java
/**
 *  容器测试框架
 *  框架模块4:模拟数据生成器
 */
package com.ciaoshen.thinkinjava.chapter17.testframework.gen;
import java.util.*;

public interface Generator<T>{
    public T next();
}
RandomGenerator.java
/**
 *  RandomGenerator随机生成填充常用类型。
 */
package com.ciaoshen.thinkinjava.chapter17.testframework.gen;
import java.util.*;

public class RandomGenerator{
    private static Random rand=new Random();

    //Boolean
    public static class Boolean implements Generator<java.lang.Boolean>{
        public java.lang.Boolean next(){
            return rand.nextBoolean();
        }
    }
    //Integer
    public static class Integer implements Generator<java.lang.Integer>{
        public java.lang.Integer next(){
            return rand.nextInt();
        }
    }
    //Long
    public static class Long implements Generator<java.lang.Long>{
        public java.lang.Long next(){
            return rand.nextLong();
        }
    }
    //Short
    public static class Short implements Generator<java.lang.Short>{
        public java.lang.Short next(){
            return (short)rand.nextInt((int)java.lang.Short.MAX_VALUE);
        }
    }
    //Float
    public static class Float implements Generator<java.lang.Float>{
        public java.lang.Float next(){
            return rand.nextFloat();
        }
    }
    //Double
    public static class Double implements Generator<java.lang.Double>{
        public java.lang.Double next(){
            return rand.nextDouble();
        }
    }
    //Byte
    public static class Byte implements Generator<java.lang.Byte>{
        private byte[] b=new byte[1];
        public java.lang.Byte next(){
            rand.nextBytes(b);
            return b[0];
        }
    }

    //Charactor
    private static final char[] CS=("abcdefghijklmnopqrstuvwxyz"+"ABCDEFGHIJKLMNOPQRSTUVWXYZ").toCharArray();
    public static class Character implements Generator<java.lang.Character>{
        public java.lang.Character next(){
            return CS[rand.nextInt(CS.length)];
        }
    }


    //String
    public static class String implements Generator<java.lang.String>{
        private int size=7;
        private Generator<java.lang.Character> c=new Character();
        public String(){}
        public String(int size){this.size=size;}
        public java.lang.String next(){
            StringBuilder sb=new StringBuilder();
            for(int i=0;i<size;i++){
                sb.append(c.next());
            }
            return sb.toString();
        }
    }

    /**
     *  测试
     */
    public static void main(java.lang.String[] args){
        RandomGenerator.String s=new RandomGenerator.String();
        System.out.println(s.next());
    }
}
Generated.java
/**
 *  容器测试框架
 *  框架模块4:模拟数据生成器
 */
package com.ciaoshen.thinkinjava.chapter17.testframework.gen;
import java.util.*;

public class Generated {
    // Fill an existing array:
    public static <T> T[] array(T[] a, Generator<T> gen) {
        return new CollectionData<T>(gen, a.length).toArray(a);
    }
    // Create a new array:
    @SuppressWarnings("unchecked")
    public static <T> T[] array(Class<T> type, Generator<T> gen, int size) {
        T[] a = (T[])java.lang.reflect.Array.newInstance(type, size);
        return new CollectionData<T>(gen, size).toArray(a);
    }
}
CountingIntegerList.java
/**
 *  容器测试框架
 *  框架模块4:模拟数据生成器
 */
package com.ciaoshen.thinkinjava.chapter17.testframework.gen;
import java.util.*;

public class CountingIntegerList extends AbstractList<Integer> {
    private int size;
    public CountingIntegerList(int size) {
        this.size = size < 0 ? 0 : size;
    }
    public Integer get(int index) {
        return Integer.valueOf(index);
    }
    public int size() { return size; }
    public static void main(String[] args) {
        System.out.println(new CountingIntegerList(30));
    }
}
CountingStringList.java

com.ciaoshen.thinkinjava.chapter17.testframework.gen生成器包里还要加一个新的List生成器。为了减小生成List本身时间上的影响,这个CountingStringList和CountingIntegerList一样是没有数据主体的。每次get()方法都随机生成一个String。

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

public class CountingStringList extends AbstractList<String> {
    private static Generator<java.lang.String> rand=new RandomGenerator.String();
    private int size;
    public CountingStringList(int size) {
        this.size = size < 0 ? 0 : size;
    }
    public CountingStringList(int size, int length) {
        this.size = size < 0 ? 0 : size;
        rand=new RandomGenerator.String(length);
    }
    public String get(int index) {
        return rand.next();
    }
    public int size() { return size; }
    public static void main(String[] args) {
        System.out.println(new CountingStringList(30));
    }
}
CountingGenerator.java
/**
 *  容器测试框架
 *  框架模块4:模拟数据生成器
 */
package com.ciaoshen.thinkinjava.chapter17.testframework.gen;
import java.util.*;


public class CountingGenerator {
    public static class Boolean implements Generator<java.lang.Boolean> {
        private boolean value = false;
        public java.lang.Boolean next() {
            value = !value; // Just flips back and forth
            return value;
        }
    }
    public static class Byte implements Generator<java.lang.Byte> {
        private byte value = 0;
        public java.lang.Byte next() { return value++; }
    }
    static char[] chars = ("abcdefghijklmnopqrstuvwxyz" + "ABCDEFGHIJKLMNOPQRSTUVWXYZ").toCharArray();
    public static class Character implements Generator<java.lang.Character> {
        int index = -1;
        public java.lang.Character next() {
            index = (index + 1) % chars.length;
            return chars[index];
        }
    }
    public static class String implements Generator<java.lang.String> {
        private int length = 7;
        Generator<java.lang.Character> cg = new Character();
        public String() {}
        public String(int length) { this.length = length; }
        public java.lang.String next() {
            char[] buf = new char[length];
            for(int i = 0; i < length; i++)
                buf[i] = cg.next();
            return new java.lang.String(buf);
        }
    }
    public static class Short implements Generator<java.lang.Short> {
        private short value = 0;
        public java.lang.Short next() { return value++; }
    }
    public static class Integer implements Generator<java.lang.Integer> {
        private int value = 0;
        public java.lang.Integer next() { return value++; }
    }
    public static class Long implements Generator<java.lang.Long> {
        private long value = 0;
        public java.lang.Long next() { return value++; }
    }
    public static class Float implements Generator<java.lang.Float> {
        private float value = 0;
        public java.lang.Float next() {
            float result = value;
            value += 1.0;
            return result;
        }
    }
    public static class Double implements Generator<java.lang.Double> {
        private double value = 0.0;
        public java.lang.Double next() {
            double result = value;
            value += 1.0;
            return result;
        }
    }
}
CollectionData.java
/**
 *  容器测试框架
 *  框架模块4:模拟数据生成器
 */
package com.ciaoshen.thinkinjava.chapter17.testframework.gen;
import java.util.*;

@SuppressWarnings("serial")
public class CollectionData<T> extends ArrayList<T> {
    public CollectionData(Generator<T> gen, int quantity) {
        for(int i = 0; i < quantity; i++)
            add(gen.next());
    }
    // A generic convenience method:
    public static <T> CollectionData<T> list(Generator<T> gen, int quantity) {
        return new CollectionData<T>(gen, quantity);
    }
}

Exercise 29

Exercise29.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import com.ciaoshen.thinkinjava.chapter17.testframework.*;
import com.ciaoshen.thinkinjava.chapter17.testframework.gen.*;

public class Exercise29 {
    static Random rand = new Random();
    static Generator<java.lang.String> strRand = new RandomGenerator.String();
    static int reps = 1000;
    static List<Test<List<String>>> tests = new ArrayList<Test<List<String>>>();
    static List<Test<LinkedList<String>>> qTests = new ArrayList<Test<LinkedList<String>>>();

    /**
     *  实际测试类在这里定义
     */
    static {
        tests.add(new Test<List<String>>("add") {
            public int test(List<String> list, TestParam tp) {
                int loops = tp.loops;
                int listSize = tp.size;
                for(int i = 0; i < loops; i++) {
                    list.clear();
                    for(int j = 0; j < listSize; j++)
                        list.add(strRand.next());
                }
                return loops * listSize;
            }
        });
        tests.add(new Test<List<String>>("get") {
            public int test(List<String> list, TestParam tp) {
                int loops = tp.loops * reps;
                int listSize = list.size();
                for(int i = 0; i < loops; i++)
                    list.get(rand.nextInt(listSize));
                return loops;
            }
        });
        tests.add(new Test<List<String>>("set") {
            public int test(List<String> list, TestParam tp) {
                int loops = tp.loops * reps;
                int listSize = list.size();
                for(int i = 0; i < loops; i++)
                    list.set(rand.nextInt(listSize), strRand.next());
                return loops;
            }
        });
        tests.add(new Test<List<String>>("iteradd") {
            public int test(List<String> list, TestParam tp) {
                final int LOOPS = 1000000;
                int half = list.size() / 2;
                ListIterator<String> it = list.listIterator(half);
                for(int i = 0; i < LOOPS; i++)
                    it.add(strRand.next());
                return LOOPS;
            }
        });
        tests.add(new Test<List<String>>("insert") {
            public int test(List<String> list, TestParam tp) {
                int loops = tp.loops;
                for(int i = 0; i < loops; i++)
                    list.add(5, strRand.next()); // Minimize random-access cost
                return loops;
            }
        });
        tests.add(new Test<List<String>>("remove") {
            public int test(List<String> list, TestParam tp) {
                int loops = tp.loops;
                int size = tp.size;
                for(int i = 0; i < loops; i++) {
                    list.clear();
                    list.addAll(new CountingStringList(size));
                    while(list.size() > 5)
                        list.remove(5); // Minimize random-access cost
                }
                return loops * size;
            }
        });
        // Tests for queue behavior:
        qTests.add(new Test<LinkedList<String>>("addFirst") {
            public int test(LinkedList<String> list, TestParam tp) {
                int loops = tp.loops;
                int size = tp.size;
                for(int i = 0; i < loops; i++) {
                    list.clear();
                    for(int j = 0; j < size; j++)
                        list.addFirst(strRand.next());
                }
                return loops * size;
            }
        });
        qTests.add(new Test<LinkedList<String>>("addLast") {
            public int test(LinkedList<String> list, TestParam tp) {
                int loops = tp.loops;
                int size = tp.size;
                for(int i = 0; i < loops; i++) {
                    list.clear();
                    for(int j = 0; j < size; j++)
                        list.addLast(strRand.next());
                }
                return loops * size;
            }
        });
        qTests.add(new Test<LinkedList<String>>("rmFirst") {
                       public int test(LinkedList<String> list, TestParam tp) {
                           int loops = tp.loops;
                           int size = tp.size;
                           for(int i = 0; i < loops; i++) {
                               list.clear();
                               list.addAll(new CountingStringList(size));
                               while(list.size() > 0)
                                   list.removeFirst();
                           }
                           return loops * size;
                       }
                   });
        qTests.add(new Test<LinkedList<String>>("rmLast") {
            public int test(LinkedList<String> list, TestParam tp) {
                int loops = tp.loops;
                int size = tp.size;
                for(int i = 0; i < loops; i++) {
                    list.clear();
                    list.addAll(new CountingStringList(size));
                    while(list.size() > 0)
                        list.removeLast();
                }
                return loops * size;
            }
        });
    }


    static class ListTester extends Tester<List<String>> {
        public ListTester(List<String> container, List<Test<List<String>>> tests) {
            super(container, tests);
        }
        @Override
        protected List<String> initialize(int size){
            container.clear();
            container.addAll(new CountingStringList(size));
            return container;
        }
        public static void run(List<String> list, List<Test<List<String>>> tests) {
            new ListTester(list, tests).timedTest();
        }
    }

    public static void main(String[] args) {
        if(args.length > 0){
            Tester.defaultParams = TestParam.array(args);
        }
        Tester<List<String>> arrayTest = new Tester<List<String>>(null, tests.subList(1, 3)){
            @Override protected
            List<String> initialize(int size) {
                String[] ia = Generated.array(String.class, new CountingGenerator.String(), size);
                return Arrays.asList(ia);
            }
        };
        arrayTest.setHeadline("Array as List");
        arrayTest.timedTest();
        Tester.defaultParams= TestParam.array(10, 5000, 100, 5000, 1000, 1000, 10000, 200);
        if(args.length > 0){
            Tester.defaultParams = TestParam.array(args);
        }
        ListTester.run(new ArrayList<String>(), tests);
        ListTester.run(new LinkedList<String>(), tests);
        ListTester.run(new Vector<String>(), tests);
        Tester.fieldWidth = 12;
        Tester<LinkedList<String>> qTest = new Tester<LinkedList<String>>(new LinkedList<String>(), qTests);
        qTest.setHeadline("Queue tests");
        qTest.timedTest();
    }
}

Exercise 30

因为,Collections.sort()的源码是把List统一转换成数组,然后用Arrays.sort()来排序的。所以两个效率的差距只有前面转换成数组的效率高低。后面排序完全一样。

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

public class Exercise30{
    static List<Test<List<String>>> tests=new ArrayList<Test<List<String>>>();
    static TestParam[] params= TestParam.array(10, 10, 100, 10, 1000, 10, 2000, 10);

    static{
        tests.add(new Test<List<String>>("sort"){
            String name="sort";
            public int test(List<String> container, TestParam tp){
                int size=tp.size;
                int loops=tp.loops;
                for(int i=0;i<loops;i++){
                    container.clear();
                    for(int j=0;j<size;j++){
                        container.addAll(new CountingStringList(size,5));
                    }
                    Collections.sort(container);
                }
                return size*loops;
            }
        });
    }


    public static void main(String[] args){
        Tester.run(new ArrayList<String>(),tests,params);
        Tester.run(new LinkedList<String>(),tests,params);
    }
}

结果:

- ArrayList -
 size    sort
   10   14125
  100   39813
 1000  294339
10000 3639676
- LinkedList -
 size    sort
   10    3246
  100   24711
 1000  306514
10000 4026489

但这个测试的结果中,container.addAll()对List填充这一步的时间也被计算到运行时间里。对结果的影响比较大。 不排序,光填充的时间:

- ArrayList -
 size    sort
   10   12761
  100   18892
 1000  169804
10000 1349499
- LinkedList -
 size    sort
   10    1858
  100   14822
 1000  139999
10000 1406752

Exercise 31

StringList.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import com.ciaoshen.thinkinjava.chapter17.testframework.gen.*;

public class StringList extends AbstractList<String>{
    private static final int SIZE=10;
    private String[] list;
    private int max=SIZE;
    private int cursor=0;

    public StringList(){
        list=new String[max];
    }
    public StringList(int size){
        max=size;
        list=new String[max];
    }

    //add last
    public boolean add(String s){
        if(cursor==max){
            resize();
        }
        list[cursor]=s;
        cursor++;
        return true;
    }
    //get first
    public String get(){
        return size()==0? null:list[0];
    }
    public String get(int index){
        if(index<0 || index>=max){
            return null;
        }
        return list[index];
    }
    //size*2
    public void resize(){
        max*=2;
        String[] newList=Arrays.copyOf(list,max);
        list=newList;
    }

    public int size(){
        return cursor;
    }

    public void clear(){
        list=new String[SIZE];
        max=SIZE;
        cursor=0;
    }

    public static void main(String[] args){
        Random rand=new Random();
        List<String> list=new StringList();
        list.addAll(new CountingStringList(50));
        for(int i=0;i<10;i++){
            int index=rand.nextInt(50);
            System.out.println("String No."+index+":    "+list.get(index));
        }
    }
}
Exercise31.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import com.ciaoshen.thinkinjava.chapter17.testframework.*;
import com.ciaoshen.thinkinjava.chapter17.testframework.gen.*;

public class Exercise31{
    static List<Test<List<String>>> tests=new ArrayList<Test<List<String>>>();

    static{
        tests.add(new Test<List<String>>("add"){
            String name="sort";
            public int test(List<String> container, TestParam tp){
                int size=tp.size;
                int loops=tp.loops;
                Generator<String> gen=new RandomGenerator.String();
                for(int i=0;i<loops;i++){
                    container.clear();
                    for(int j=0;j<size;j++){
                        container.add(gen.next());
                    }
                }
                return size*loops;
            }
        });
        tests.add(new Test<List<String>>("get"){
            String name="sort";
            public int test(List<String> container, TestParam tp){
                int size=tp.size;
                int loops=tp.loops;
                Random rand=new Random();
                container.addAll(new CountingStringList(size,5));
                for(int i=0;i<loops;i++){
                    container.get(rand.nextInt(size));
                }
                return loops;
            }
        });
    }

    public static void main(String[] args){
        Tester.run(new ArrayList<String>(),tests);
        Tester.run(new StringList(),tests);
    }
}
结果

不泛型的简单StringList和ArrayList比,add()方法差不多,get()方法快一倍多。

----- ArrayList -----
 size     add     get
   10    1115     579
  100     229     173
 1000     211     362
10000     180   11722
----- StringList -----
 size     add     get
   10     409     187
  100     193      78
 1000     176     101
10000     175    4020

Exercise 32

IntList.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import com.ciaoshen.thinkinjava.chapter17.testframework.gen.*;

public class IntList extends AbstractList<Integer>{
    private static final int SIZE=10;
    private int[] list;
    private int max=SIZE;
    private int cursor=0;

    public IntList(){
        list=new int[max];
    }
    public IntList(int size){
        max=size;
        list=new int[max];
    }

    //add last
    @Override
    public boolean add(Integer i){
        if(cursor==max){
            resize();
        }
        list[cursor]=i;
        cursor++;
        return true;
    }
    //get first
    public Integer get(){
        return size()==0? null:list[0];
    }
    public Integer get(int index){
        if(index<0 || index>=max){
            return null;
        }
        return list[index];
    }
    public Integer set(int index, Integer i){
        if(index<0 || index>=max){
            return null;
        }
        list[index]=i;
        return list[index];
    }
    //size*2
    public void resize(){
        max*=2;
        int[] newList=Arrays.copyOf(list,max);
        list=newList;
    }

    public int size(){
        return cursor;
    }

    public void clear(){
        list=new int[SIZE];
        max=SIZE;
        cursor=0;
    }

    public static void main(String[] args){
        Random rand=new Random();
        List<Integer> list=new IntList();
        list.addAll(new CountingIntegerList(50));
        for(int i=0;i<10;i++){
            int index=rand.nextInt(50);
            System.out.println("Int No."+index+":    "+list.get(index));
        }
    }
}
Exercise32.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import com.ciaoshen.thinkinjava.chapter17.testframework.*;
import com.ciaoshen.thinkinjava.chapter17.testframework.gen.*;

public class Exercise32{
    static List<Test<List<Integer>>> tests=new ArrayList<Test<List<Integer>>>();
    static Random rand=new Random();

    static{
        tests.add(new Test<List<Integer>>("add"){
            String name="sort";
            public int test(List<Integer> container, TestParam tp){
                int size=tp.size;
                int loops=tp.loops;
                for(int i=0;i<loops;i++){
                    container.clear();
                    for(int j=0;j<size;j++){
                        container.add(rand.nextInt(size));
                    }
                }
                return size*loops;
            }
        });
        tests.add(new Test<List<Integer>>("get"){
            String name="sort";
            public int test(List<Integer> container, TestParam tp){
                int size=tp.size;
                int loops=tp.loops;
                Random rand=new Random();
                container.addAll(new CountingIntegerList(size));
                for(int i=0;i<loops;i++){
                    container.get(rand.nextInt(size));
                }
                return loops;
            }
        });
        tests.add(new Test<List<Integer>>("plus"){
            String name="sort";
            public int test(List<Integer> container, TestParam tp){
                int size=tp.size;
                int loops=tp.loops;
                Random rand=new Random();
                container.addAll(new CountingIntegerList(size));
                for(int i=0;i<loops;i++){
                    for(int j=0;j<size;j++){
                        container.set(j,container.get(j)+1);
                    }
                }
                return loops*size;
            }
        });
    }


    public static void main(String[] args){
        Tester.run(new ArrayList<Integer>(),tests);
        Tester.run(new IntList(),tests);
    }
}
结果
--------- ArrayList ---------
 size     add     get    plus
   10     193     312     221
  100      38      68      30
 1000      22     154      10
10000      15    1762      10
---------- IntList ----------
 size     add     get    plus
   10      61     137     234
  100      24      67      41
 1000      20      80       8
10000      27    3006       7

Exercise 33

  1. 插入,移除用LinkdList
  2. 遍历,set(),get()用ArrayList
  3. ListIterator(int index)接口用来返回LinkedList的迭代器
  4. iterator()接口用来返回ArrayList的迭代器
FastTraversalLinkedList.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import com.ciaoshen.thinkinjava.chapter17.testframework.gen.*;

@SuppressWarnings("serial")
public class FastTraversalLinkedList<E> extends LinkedList<E>{
    private List<E> list=new ArrayList<E>();

    public void synArrayList(){
        list.clear();
        ListIterator<E> ite=listIterator(0);
        while(ite.hasNext()){
            list.add(ite.next());
        }
    }
    public void synLinkedList(){
        clear();
        ListIterator<E> ite=listIterator(0);
        while(ite.hasNext()){
            add(ite.next());
        }
    }

    /**
     *  四个用ArrayList的方法
     */
    @Override
    public Iterator<E> iterator(){return list.isEmpty()? null:list.iterator();}
    @Override
    public E get(int index){
        return list.isEmpty()? null:list.get(index);
    }
    @Override
    public E set(int index, E element){
        return list.size()>index?  list.set(index,element):null;
    }

    public static void main(String[] args){

    }
}
Exercise33.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import com.ciaoshen.thinkinjava.chapter17.testframework.*;
import com.ciaoshen.thinkinjava.chapter17.testframework.gen.*;

public class Exercise33 {
    static Random rand = new Random();
    static int reps = 1000;
    static List<Test<List<Integer>>> tests = new ArrayList<Test<List<Integer>>>();

    /**
     *  实际测试类在这里定义
     */
    static {
        /**
         *  用LinkedList的3个方法
         */
        tests.add(new Test<List<Integer>>("add") {
            public int test(List<Integer> list, TestParam tp) {
                int loops = tp.loops;
                int listSize = tp.size;
                for(int i = 0; i < loops; i++) {
                    list.clear();
                    for(int j = 0; j < listSize; j++)
                        list.add(j);
                }
                return loops * listSize;
            }
        });
        tests.add(new Test<List<Integer>>("insert") {
            public int test(List<Integer> list, TestParam tp) {
                int loops = tp.loops;
                for(int i = 0; i < loops; i++)
                    list.add(5, 47); // Minimize random-access cost
                return loops;
            }
        });
        tests.add(new Test<List<Integer>>("remove") {
            public int test(List<Integer> list, TestParam tp) {
                int loops = tp.loops;
                int size = tp.size;
                for(int i = 0; i < loops; i++) {
                    list.clear();
                    list.addAll(new CountingIntegerList(size));
                    while(list.size() > 5)
                        list.remove(5); // Minimize random-access cost
                }
                return loops * size;
            }
        });

        /**
         *  用ArrayList的4个方法
         */
        tests.add(new Test<List<Integer>>("get") {
            public int test(List<Integer> list, TestParam tp) {
                int loops = tp.loops * reps;
                int listSize = list.size();
                for(int i = 0; i < loops; i++)
                    list.get(rand.nextInt(listSize));
                return loops;
            }
        });
        tests.add(new Test<List<Integer>>("set") {
            public int test(List<Integer> list, TestParam tp) {
                int loops = tp.loops * reps;
                int listSize = list.size();
                for(int i = 0; i < loops; i++)
                    list.set(rand.nextInt(listSize), 47);
                return loops;
            }
        });
        tests.add(new Test<List<Integer>>("iter") {
            public int test(List<Integer> list, TestParam tp) {
                int loops = tp.loops;
                int size = list.size();
                Iterator<Integer> it = list.iterator();
                for(int i = 0; i < loops; i++){
                    while(it.hasNext()){
                        it.next();
                    }
                }
                return loops*size;
            }
        });
    }


    static class ListTester extends Tester<List<Integer>> {
        public ListTester(List<Integer> container, List<Test<List<Integer>>> tests) {
            super(container, tests);
        }
        @SuppressWarnings("uchecked")
        protected List<Integer> initialize(int size){
            container.clear();
            container.addAll(new CountingIntegerList(size));
            if(container instanceof FastTraversalLinkedList){
                ((FastTraversalLinkedList)container).synArrayList();
            }
            return container;
        }
        public static void run(List<Integer> list, List<Test<List<Integer>>> tests) {
            new ListTester(list, tests).timedTest();
        }
    }

    public static void main(String[] args) {
        if(args.length > 0){
            Tester.defaultParams = TestParam.array(args);
        }
        Tester.defaultParams= TestParam.array(10, 5000, 100, 5000, 1000, 1000, 10000, 200);
        if(args.length > 0){
            Tester.defaultParams = TestParam.array(args);
        }
        ListTester.run(new ArrayList<Integer>(), tests);
        ListTester.run(new LinkedList<Integer>(), tests);
        ListTester.run(new FastTraversalLinkedList<Integer>(), tests);
        Tester.fieldWidth = 12;
    }
}
测试结果

虽然测试成绩是各取ArrayList和LinkedList的优点,但实际使用的时候因为有synchronize同步两个列表的开销,所以综合开销还是不沾优的。

--------------------- ArrayList ---------------------
 size     add  insert  remove     get     set    iter
   10      91    1172     245      15      14       8
  100      13     290      31      14      15       0
 1000      16     198      93      11      13       0
10000       8    1605     497      12      17       0
--------------------- LinkedList ---------------------
 size     add  insert  remove     get     set    iter
   10     110     322     110      32      27      10
  100       8     119      14      41      41       0
 1000      10      61      15     379     374       2
10000      18      75      19    4720    4428       0
-------------- FastTraversalLinkedList --------------
 size     add  insert  remove     get     set    iter
   10      70      87      30      14      15       3
  100      11      58      21      14      15       0
 1000      29      80      35      13      12       0
10000      17      64      21      12      13       0

Exercise 34

Exercise34.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import com.ciaoshen.thinkinjava.chapter17.testframework.*;
import com.ciaoshen.thinkinjava.chapter17.testframework.gen.*;

public class Exercise34{
    static List<Test<Set<String>>> tests = new ArrayList<Test<Set<String>>>();
    static Generator<String> gen=new RandomGenerator.String();
    static {
        tests.add(new Test<Set<String>>("add") {
            public int test(Set<String> set, TestParam tp) {
                int loops = tp.loops;
                int size = tp.size;
                for(int i = 0; i < loops; i++) {
                    set.clear();
                    for(int j = 0; j < size; j++)
                        set.add(gen.next());
                }
                return loops * size;
            }
        });
        tests.add(new Test<Set<String>>("contains") {
            public int test(Set<String> set, TestParam tp) {
                int loops = tp.loops;
                int span = tp.size * 2;
                for(int i = 0; i < loops; i++)
                    for(int j = 0; j < span; j++)
                        set.contains("xxxxxxx");
                return loops * span;
            }
        });
        tests.add(new Test<Set<String>>("iterate") {
            public int test(Set<String> set, TestParam tp) {
                int loops = tp.loops * 10;
                for(int i = 0; i < loops; i++) {
                    Iterator<String> it = set.iterator();
                    while(it.hasNext()){
                        it.next();
                    }
                }
                return loops * set.size();
            }
        });
    }

    static class Tester34 extends Tester<Set<String>>{
        public Tester34(Set<String> container, List<Test<Set<String>>> tests) {
            super(container, tests);
        }
        public Tester34(Set<String> container, List<Test<Set<String>>> tests, TestParam[] paramList){
            super(container, tests, paramList);
        }

        public static void run(Set<String> cntnr, List<Test<Set<String>>> tests){
            new Tester34(cntnr, tests).timedTest();
        }
        public static void run(Set<String> cntnr, List<Test<Set<String>>> tests, TestParam[] paramList) {
            new Tester34(cntnr, tests, paramList).timedTest();
        }

        @Override
        protected Set<String> initialize(int size){
            Generator<String> gen=new RandomGenerator.String();
            for(int i=0;i<size;i++){
                container.add(gen.next());
            }
            return container;
        }
    }

    public static void main(String[] args) {
        if(args.length > 0){
            Tester.defaultParams = TestParam.array(args);
        }
        Tester34.fieldWidth = 10;
        Tester34.run(new TreeSet<String>(), tests);
        Tester34.run(new HashSet<String>(), tests);
        Tester34.run(new LinkedHashSet<String>(), tests);
    }
}
测试结果
------------- TreeSet -------------
 size       add  contains   iterate
   10      1538        71        39
  100       325        29         6
 1000       312        39         8
10000       412        49        20
------------- HashSet -------------
 size       add  contains   iterate
   10       478        63        89
  100       190        12         7
 1000       180         4         8
10000       199         2        14
---------- LinkedHashSet ----------
 size       add  contains   iterate
   10       279        52        25
  100       193         5         7
 1000       200         5         6
10000       202         7        11

Exercise 35

SlowMap真的非常慢。

Exercise35.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import com.ciaoshen.thinkinjava.chapter17.testframework.*;
import com.ciaoshen.thinkinjava.chapter17.testframework.gen.*;

public class Exercise35 {
    static List<Test<Map<Integer,Integer>>> tests = new ArrayList<Test<Map<Integer,Integer>>>();
    static {
        tests.add(new Test<Map<Integer,Integer>>("put") {
            public int test(Map<Integer,Integer> map, TestParam tp) {
                int loops = tp.loops;
                int size = tp.size;
                for(int i = 0; i < loops; i++) {
                    map.clear();
                    for(int j = 0; j < size; j++)
                        map.put(j, j);
                }
                return loops * size;
            }
        });
        tests.add(new Test<Map<Integer,Integer>>("get") {
            public int test(Map<Integer,Integer> map, TestParam tp) {
                int loops = tp.loops;
                int span = tp.size * 2;
                for(int i = 0; i < loops; i++)
                    for(int j = 0; j < span; j++)
                        map.get(j);
                return loops * span;
            }
        });
        tests.add(new Test<Map<Integer,Integer>>("iterate") {
            public int test(Map<Integer,Integer> map, TestParam tp) {
                int loops = tp.loops * 10;
                for(int i = 0; i < loops; i ++) {
                    Iterator<Map.Entry<Integer,Integer>> it = map.entrySet().iterator();
                    while(it.hasNext())
                        it.next();
                }
                return loops * map.size();
            }
        });
    }
    static class Tester35 extends Tester<Map<Integer,Integer>>{
        public Tester35(Map<Integer,Integer> container, List<Test<Map<Integer,Integer>>> tests) {
            super(container, tests);
        }
        public Tester35(Map<Integer,Integer> container, List<Test<Map<Integer,Integer>>> tests, TestParam[] paramList){
            super(container, tests, paramList);
        }

        public static void run(Map<Integer,Integer> cntnr, List<Test<Map<Integer,Integer>>> tests){
            new Tester35(cntnr, tests).timedTest();
        }
        public static void run(Map<Integer,Integer> cntnr, List<Test<Map<Integer,Integer>>> tests, TestParam[] paramList) {
            new Tester35(cntnr, tests, paramList).timedTest();
        }

        @Override
        protected Map<Integer,Integer> initialize(int size){
            for(int i=0;i<size;i++){
                container.put(i,i);
            }
            return container;
        }
    }

    public static void main(String[] args) {
        if(args.length > 0){
            Tester.defaultParams = TestParam.array(args);
        }
        Tester35.defaultParams= TestParam.array(10, 5000, 100, 5000, 100, 1000, 10000, 20);
        Tester35.run(new TreeMap<Integer,Integer>(), tests);
        Tester35.run(new HashMap<Integer,Integer>(), tests);
        Tester35.run(new LinkedHashMap<Integer,Integer>(),tests);
        Tester35.run(
                     new IdentityHashMap<Integer,Integer>(), tests);
        Tester35.run(new WeakHashMap<Integer,Integer>(), tests);
        Tester35.run(new Hashtable<Integer,Integer>(), tests);
        Tester35.run(new BetterSlowMap<Integer,Integer>(), tests);
        Tester35.run(new SortedSlowMap<Integer,Integer>(), tests);
    }
}
测试结果
---------- TreeMap ----------
 size     put     get iterate
   10     424      98      32
  100      60      26       8
 1000      69      46       5
10000      94      58       8
---------- HashMap ----------
 size     put     get iterate
   10     205      97      71
  100      10       3       8
 1000      16       5       5
10000      15       5       6
------- LinkedHashMap -------
 size     put     get iterate
   10     290      46      14
  100      32      11       7
 1000      26      10       6
10000      27      11       6
------ IdentityHashMap ------
 size     put     get iterate
   10      89      33      24
  100      20      41      15
 1000      81      84      16
10000      95     133      16
-------- WeakHashMap --------
 size     put     get iterate
   10     126      57      28
  100      42       7      10
 1000      29      10      14
10000      25      11      16
--------- Hashtable ---------
 size     put     get iterate
   10      63      37      21
  100      53      22       9
 1000      28      27       8
10000      30      23       9
---------- SlowMap ----------
 size     put     get iterate
   10     316     135      53
  100     195     120      12
 1000    1334     820      11
10000   15946    8691      11

Exercise 36

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

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

    private class MPair<K,V> implements Map.Entry<K,V>{
        private K key;
        private V value;

        public MPair(K k, V v){key=k;value=v;}
        public K getKey(){return key;}
        public V getValue(){return value;}
        public V setValue(V v){V old=value;value=v;return old;}
        @SuppressWarnings("unchecked")
        public boolean equals(Object o){
            if(! (o instanceof Map.Entry)){return false;}
            Map.Entry<K,V> entry=(Map.Entry<K,V>)o;
            return
            (key==null? entry.getKey()==null : entry.getKey().equals(key))
            &&
            (value==null? entry.getValue()==null : entry.getValue().equals(value));
        }
        public int hashCode(){
            int hash=17*37;
            hash+= (key==null)? 0:key.hashCode();
            hash*=37;
            hash+= (value==null)? 0:value.hashCode();
            return hash;
        }
    }

    private List<Map.Entry<K,V>> list = new ArrayList<Map.Entry<K,V>>();

    public V put(K key, V value) {
        V oldValue=null;
        Map.Entry<K,V> entry=new MPair<K,V>(key, value);
        int index=list.indexOf(entry);
        if(index==-1){
            list.add(entry);
        }else{
            oldValue=list.get(index).getValue();
            list.set(index,entry);
        }
        return oldValue;
    }
    @SuppressWarnings("unchecked")
    public V get(Object key) {
        V value=null;
        K k=(K)key;
        for(Map.Entry<K,V> entry:list){
            if(entry.getKey().equals(k)){
                value=entry.getValue();
            }
        }
        return value;
    }
    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 list.iterator();
        }
        public int size(){return list.size();}
    }


    public static void main(String[] args) {
        SlowMap<String,String> m= new SlowMap<String,String>();
        m.putAll(MyCountries.capitals(15));
        System.out.println(m);
        System.out.println(m.get("BULGARIA"));
        System.out.println(m.entrySet());
    }
}
SortedSlowMap.java
/**
 *  持有MPair对象数组的SlowMap
 *  每次put()完,用sort()排序
 *  get()的时候用binarySearch()
 */
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;

class SlowMapComparator<K,V> implements Comparator<Map.Entry<K,V>>{
    @SuppressWarnings("unchecked")
    public int compare(Map.Entry<K,V> a, Map.Entry<K,V> b){
        return ((Comparable<K>)a.getKey()).compareTo(b.getKey());
    }
}

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

    private class MPair<K,V> implements Map.Entry<K,V>, Comparable<MPair<K,V>>{
        private K key;
        private V value;

        public MPair(K k, V v){key=k;value=v;}
        public K getKey(){return key;}
        public V getValue(){return value;}
        public V setValue(V v){V old=value;value=v;return old;}
        @SuppressWarnings("unchecked")
        public boolean equals(Object o){
            if(! (o instanceof Map.Entry)){return false;}
            Map.Entry<K,V> entry=(Map.Entry<K,V>)o;
            return key==null? entry.getKey()==null : entry.getKey().equals(key);
        }
        public int hashCode(){
            int hash=17*37;
            hash+= (key==null)? 0:key.hashCode();
            return hash;
        }
        @SuppressWarnings("unchecked")
        public int compareTo(MPair<K,V> entry){
            return ((Comparable<K>)entry.getKey()).compareTo(key);
        }
    }

    private List<Map.Entry<K,V>> list = new ArrayList<Map.Entry<K,V>>();

    public V put(K key, V value) {
        Map.Entry<K,V> entry=new MPair<K,V>(key,value);
        V oldValue=null;
        Comparator<Map.Entry<K,V>> comp=new SlowMapComparator<K,V>();
        int index=Collections.binarySearch(list,entry,comp);
        if(index>=0){
            oldValue=list.set(index,entry).getValue();
        }else{
            list.add(entry);
            Collections.sort(list,comp);
        }
        return oldValue;
    }

    @SuppressWarnings("unchecked")
    public V get(Object key) {
        V value=null;
        Map.Entry<K,V> entry=new MPair<K,V>((K)key,null);
        int index=Collections.binarySearch(list,entry,new SlowMapComparator<K,V>());
        if(index>=0){
            value=list.get(index).getValue();
        }
        return value;
    }

    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 list.iterator();
        }
        public int size(){return list.size();}
    }


    public static void main(String[] args) {
        SlowMap<String,String> m= new SlowMap<String,String>();
        m.putAll(MyCountries.capitals(15));
        System.out.println(m);
        System.out.println(m.get("BULGARIA"));
        System.out.println(m.entrySet());
    }
}
Exercise36.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import com.ciaoshen.thinkinjava.chapter17.testframework.*;
import com.ciaoshen.thinkinjava.chapter17.testframework.gen.*;

public class Exercise36 {
    static List<Test<Map<Integer,Integer>>> tests = new ArrayList<Test<Map<Integer,Integer>>>();
    static {
        tests.add(new Test<Map<Integer,Integer>>("put") {
            public int test(Map<Integer,Integer> map, TestParam tp) {
                int loops = tp.loops;
                int size = tp.size;
                for(int i = 0; i < loops; i++) {
                    map.clear();
                    for(int j = 0; j < size; j++)
                        map.put(j, j);
                }
                return loops * size;
            }
        });
        tests.add(new Test<Map<Integer,Integer>>("get") {
            public int test(Map<Integer,Integer> map, TestParam tp) {
                int loops = tp.loops;
                int span = tp.size * 2;
                for(int i = 0; i < loops; i++)
                    for(int j = 0; j < span; j++)
                        map.get(j);
                return loops * span;
            }
        });
        tests.add(new Test<Map<Integer,Integer>>("iterate") {
            public int test(Map<Integer,Integer> map, TestParam tp) {
                int loops = tp.loops * 10;
                for(int i = 0; i < loops; i ++) {
                    Iterator<Map.Entry<Integer,Integer>> it = map.entrySet().iterator();
                    while(it.hasNext())
                        it.next();
                }
                return loops * map.size();
            }
        });
    }

    static class Tester36 extends Tester<Map<Integer,Integer>>{
        public Tester36(Map<Integer,Integer> container, List<Test<Map<Integer,Integer>>> tests) {
            super(container, tests);
        }
        public Tester36(Map<Integer,Integer> container, List<Test<Map<Integer,Integer>>> tests, TestParam[] paramList){
            super(container, tests, paramList);
        }

        public static void run(Map<Integer,Integer> cntnr, List<Test<Map<Integer,Integer>>> tests){
            new Tester36(cntnr, tests).timedTest();
        }
        public static void run(Map<Integer,Integer> cntnr, List<Test<Map<Integer,Integer>>> tests, TestParam[] paramList) {
            new Tester36(cntnr, tests, paramList).timedTest();
        }

        @Override
        protected Map<Integer,Integer> initialize(int size){
            for(int i=0;i<size;i++){
                container.put(i,i);
            }
            return container;
        }
    }

    public static void main(String[] args) {
        if(args.length > 0){
            Tester.defaultParams = TestParam.array(args);
        }
        Tester36.defaultParams= TestParam.array(10, 5000, 100, 5000, 100, 1000, 10000, 20);
        Tester36.run(new TreeMap<Integer,Integer>(), tests);
        Tester36.run(new HashMap<Integer,Integer>(), tests);
        Tester36.run(new LinkedHashMap<Integer,Integer>(),tests);
        Tester36.run(
                   new IdentityHashMap<Integer,Integer>(), tests);
        Tester36.run(new WeakHashMap<Integer,Integer>(), tests);
        Tester36.run(new Hashtable<Integer,Integer>(), tests);
        Tester36.run(new BetterSlowMap<Integer,Integer>(), tests);
        Tester36.run(new SortedSlowMap<Integer,Integer>(), tests);  
    }
}
SortedSlowMap_V2.java 不需要用sort()排序

因为Collections.binarySearch()如果没有找到元素,返回值是(-(insertion point) - 1)。其中insertion point就是代表这个元素在原集合中应该插入的位置。利用这个数字新插入的元素就可以保持集合的排序。

    public V put(K key, V value) {
        Map.Entry<K,V> entry=new MPair<K,V>(key,value);
        V oldValue=null;
        Comparator<Map.Entry<K,V>> comp=new SlowMapComparator<K,V>();
        int index=Collections.binarySearch(list,entry,comp);
        if(index>=0){
            oldValue=list.set(index,entry).getValue();
        }else{
            list.add(Math.abs(index+1),entry);
            //Collections.sort(list,comp);	//不需要排序
        }
        return oldValue;
    }
测试结果

结果是用MPair做元素的BetterSlowMap没有比原来的SlowMap更快。尤其是get()方法因为要遍历所有MPair变得更慢了。

用了sort()和binarySearch()之后,SortedSlowMap最大的变化就是get()操作的开销指数级缩小。但代价是sort()的开销也不小。put()方法更慢了。

最后利用binarySearch()返回值的位置保持排序的SortedSlowMap_V2,put()和get()方法都显著优化。

---------- TreeMap ----------
 size     put     get iterate
   10     366     112      48
  100      61      30       6
  100      67      19       3
10000      74      69       8
---------- HashMap ----------
 size     put     get iterate
   10     193     157      73
  100      18       4       8
  100      11       3       9
10000      28      35      10
------- LinkedHashMap -------
 size     put     get iterate
   10     404      57      24
  100      43      12       7
  100      25      10       7
10000      27      11       7
------ IdentityHashMap ------
 size     put     get iterate
   10     133      54      39
  100      32      36      15
  100      13      29      13
10000     114      86      17
-------- WeakHashMap --------
 size     put     get iterate
   10     119      38      22
  100      33       8      10
  100      18       8      10
10000      26      14      11
--------- Hashtable ---------
 size     put     get iterate
   10      65      39      21
  100      34      21      10
  100      27      18       9
10000      59      34      10
---------- SlowMap ----------
 size     put     get iterate
   10     480     172      43
  100     146      91      11
  100     151      94      15
10000   11191   10775      11
------- BetterSlowMap -------
 size     put     get iterate
   10     313      77      13
  100     153     155       8
  100     168     183       9
10000   12001   17013       7
------- SortedSlowMap -------
 size     put     get iterate
   10     580     146      21
  100     288      25       7
  100     201      28       7
10000   28663      74       7
------- SortedSlowMap_V2 -------
 size     put     get iterate
   10     465     147      10
  100      38      32       7
  100      47      29       8
10000     561      69       7

Exercise 37

SimpleHashMap37.java

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

public class SimpleHashMap37<K,V> extends AbstractMap<K,V> {
    static final int SIZE = 997;

    @SuppressWarnings(value={"unchecked","rawtypes"})
    List<MapEntry<K,V>>[] buckets = new ArrayList[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 ArrayList<MapEntry<K,V>>();
        }
        List<MapEntry<K,V>> bucket = buckets[index];
        MapEntry<K,V> pair = new MapEntry<K,V>(key, value);
        boolean found = false;
        ListIterator<MapEntry<K,V>> it = bucket.listIterator();
        while(it.hasNext()) {
            MapEntry<K,V> iPair = it.next();
            if(iPair.getKey().equals(key)) {
                oldValue = iPair.getValue();
                it.set(pair); // Replace old with new
                found = true;
                break;
            }
        }
        if(!found)
            buckets[index].add(pair);
        return oldValue;
    }
    public V get(Object key) {
        int index = Math.abs(key.hashCode()) % SIZE;
        if(buckets[index] == null) return null;
        for(MapEntry<K,V> iPair : buckets[index])
            if(iPair.getKey().equals(key))
                return iPair.getValue();
        return null;
    }
    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> set= new HashSet<Map.Entry<K,V>>();
        for(List<MapEntry<K,V>> bucket : buckets) {
            if(bucket == null) continue;
            for(MapEntry<K,V> mpair : bucket)
                set.add(mpair);
        }
        return set;
    }
    public static void main(String[] args) {
        SimpleHashMap37<String,String> m = new SimpleHashMap37<String,String>();
        m.putAll(Countries.capitals(25));
        System.out.println(m);
        System.out.println(m.get("ERITREA"));
        System.out.println(m.entrySet());
    }
}
Exercise37.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
import com.ciaoshen.thinkinjava.chapter17.testframework.*;
import com.ciaoshen.thinkinjava.chapter17.testframework.gen.*;

public class Exercise37 {
    static List<Test<Map<Integer,Integer>>> tests = new ArrayList<Test<Map<Integer,Integer>>>();
    static {
        tests.add(new Test<Map<Integer,Integer>>("put") {
            public int test(Map<Integer,Integer> map, TestParam tp) {
                int loops = tp.loops;
                int size = tp.size;
                for(int i = 0; i < loops; i++) {
                    map.clear();
                    for(int j = 0; j < size; j++)
                        map.put(j, j);
                }
                return loops * size;
            }
        });
        tests.add(new Test<Map<Integer,Integer>>("get") {
            public int test(Map<Integer,Integer> map, TestParam tp) {
                int loops = tp.loops;
                int span = tp.size * 2;
                for(int i = 0; i < loops; i++)
                    for(int j = 0; j < span; j++)
                        map.get(j);
                return loops * span;
            }
        });
        tests.add(new Test<Map<Integer,Integer>>("iterate") {
            public int test(Map<Integer,Integer> map, TestParam tp) {
                int loops = tp.loops * 10;
                for(int i = 0; i < loops; i ++) {
                    Iterator<Map.Entry<Integer,Integer>> it = map.entrySet().iterator();
                    while(it.hasNext())
                        it.next();
                }
                return loops * map.size();
            }
        });
    }

    static class Tester37 extends Tester<Map<Integer,Integer>>{
        public Tester37(Map<Integer,Integer> container, List<Test<Map<Integer,Integer>>> tests) {
            super(container, tests);
        }
        public Tester37(Map<Integer,Integer> container, List<Test<Map<Integer,Integer>>> tests, TestParam[] paramList){
            super(container, tests, paramList);
        }

        public static void run(Map<Integer,Integer> cntnr, List<Test<Map<Integer,Integer>>> tests){
            new Tester37(cntnr, tests).timedTest();
        }
        public static void run(Map<Integer,Integer> cntnr, List<Test<Map<Integer,Integer>>> tests, TestParam[] paramList) {
            new Tester37(cntnr, tests, paramList).timedTest();
        }

        @Override
        protected Map<Integer,Integer> initialize(int size){
            for(int i=0;i<size;i++){
                container.put(i,i);
            }
            return container;
        }
    }

    public static void main(String[] args) {
        if(args.length > 0){
            Tester.defaultParams = TestParam.array(args);
        }else{
            Tester.defaultParams = TestParam.array(10, 5000, 100, 5000, 100, 1000, 10000, 1);
        }
        Tester37.run(new TreeMap<Integer,Integer>(), tests);
        Tester37.run(new HashMap<Integer,Integer>(), tests);
        Tester37.run(new LinkedHashMap<Integer,Integer>(),tests);
        Tester37.run(new IdentityHashMap<Integer,Integer>(), tests);
        Tester37.run(new WeakHashMap<Integer,Integer>(), tests);
        Tester37.run(new Hashtable<Integer,Integer>(), tests);
        Tester37.run(new SimpleHashMap<Integer,Integer>(), tests);
        Tester37.run(new SimpleHashMap37<Integer,Integer>(), tests);
    }
}
测试结果
---------- TreeMap ----------
 size     put     get iterate
   10     524     117      38
  100      56      27       7
  100      72      18       3
10000     101      85       8
---------- HashMap ----------
 size     put     get iterate
   10     146     114      74
  100      11       4       8
  100      28       3       7
10000      90     175      71
------- LinkedHashMap -------
 size     put     get iterate
   10     477      46      21
  100      24      10       6
  100      21       9       5
10000      94      11       6
------ IdentityHashMap ------
 size     put     get iterate
   10     115      32      23
  100      21      30      15
  100      13      35      20
10000     252      75      19
-------- WeakHashMap --------
 size     put     get iterate
   10     113      39      21
  100      27       7      10
  100      18       8      10
10000     148      54      18
--------- Hashtable ---------
 size     put     get iterate
   10      91      28      20
  100      35      19       9
  100      19      16       8
10000     130      19       8
------- SimpleHashMap -------
 size     put     get iterate
   10    1220      49     115
  100    1075      11     823
  100     996       9     805
10000     533     261  142641
------ SimpleHashMap37 ------
 size     put     get iterate
   10     761      62     113
  100     972       8     797
  100    1007       8     852
10000     756     289  145136

Exercise 38

#####Exercise38.java

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

public class Exercise38 {
    static List<Test<Map<Integer,Integer>>> tests = new ArrayList<Test<Map<Integer,Integer>>>();
    static {
        tests.add(new Test<Map<Integer,Integer>>("get") {
            public int test(Map<Integer,Integer> map, TestParam tp) {
                int loops = tp.loops;
                int span = tp.size * 2;
                for(int i = 0; i < loops; i++)
                    for(int j = 0; j < span; j++)
                        map.get(j);
                return loops * span;
            }
        });
    }

    static class Tester38 extends Tester<Map<Integer,Integer>>{
        public Tester38(Map<Integer,Integer> container, List<Test<Map<Integer,Integer>>> tests) {
            super(container, tests);
        }
        public Tester38(Map<Integer,Integer> container, List<Test<Map<Integer,Integer>>> tests, TestParam[] paramList){
            super(container, tests, paramList);
        }

        public static void run(Map<Integer,Integer> cntnr, List<Test<Map<Integer,Integer>>> tests){
            new Tester38(cntnr, tests).timedTest();
        }
        public static void run(Map<Integer,Integer> cntnr, List<Test<Map<Integer,Integer>>> tests, TestParam[] paramList) {
            new Tester38(cntnr, tests, paramList).timedTest();
        }

        @Override
        protected Map<Integer,Integer> initialize(int size){
            for(int i=0;i<size;i++){
                container.put(i,i);
            }
            return container;
        }
    }

    public static void main(String[] args) {
        if(args.length > 0){
            Tester.defaultParams = TestParam.array(args);
        }else{
            Tester.defaultParams = TestParam.array(10000, 20);
        }
        Tester38.run(new HashMap<Integer,Integer>(16384), tests);	//负载因子:10000/16384=0.61
        Tester38.run(new HashMap<Integer,Integer>(65536), tests);	//负载因子:10000/65536=0.15

    }
}
测试结果

当负载因子等于0.15的时候,查询速度明显比负载因子是0.61的时候快。

-- HashMap --
 size     get
10000      97
-- HashMap --
 size     get
10000      17

Exercise 39

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

public class RehashSimpleHashMap<K,V> extends AbstractMap<K,V> {
    static final double LOAD_FACTOR=0.75;
    int SIZE = 16;
    @SuppressWarnings(value={"unchecked","rawtypes"})
    LinkedList<MapEntry<K,V>>[] buckets = new LinkedList[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 LinkedList<MapEntry<K,V>>();
        LinkedList<MapEntry<K,V>> bucket = buckets[index];
        MapEntry<K,V> pair = new MapEntry<K,V>(key, value);
        boolean found = false;
        ListIterator<MapEntry<K,V>> it = bucket.listIterator();
        while(it.hasNext()) {
            MapEntry<K,V> iPair = it.next();
            if(iPair.getKey().equals(key)) {
                oldValue = iPair.getValue();
                it.set(pair);
                found = true;
                break;
            }
        }
        if(!found){
            if((size()/(double)SIZE)>=LOAD_FACTOR){
                rehash();
                index=Math.abs(key.hashCode()) % SIZE;
                if(buckets[index]==null){buckets[index] = new LinkedList<MapEntry<K,V>>();}
                buckets[index].add(pair);
            }else{
                buckets[index].add(pair);
            }
        }
        return oldValue;
    }

    public V get(Object key) {
        int index = Math.abs(key.hashCode()) % SIZE;
        if(buckets[index] == null) return null;
        for(MapEntry<K,V> iPair : buckets[index])
            if(iPair.getKey().equals(key))
                return iPair.getValue();
        return null;
    }

    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> set= new HashSet<Map.Entry<K,V>>();
        for(LinkedList<MapEntry<K,V>> bucket : buckets) {
            if(bucket == null) continue;
            for(MapEntry<K,V> mpair : bucket)
                set.add(mpair);
        }
        return set;
    }

    @SuppressWarnings(value={"unchecked","rawtypes"})
    private void rehash(){
        //double size
        SIZE*=2;
        while(true){
            if(isPrime(++SIZE)){break;}
        }
        System.out.println("Resize to "+SIZE);
        //transfer elements
        LinkedList<MapEntry<K,V>>[] newBuckets = new LinkedList[SIZE];
        for(LinkedList<MapEntry<K,V>> bucket:buckets){
            if(bucket!=null){
                ListIterator<MapEntry<K,V>> ite=bucket.listIterator();
                while(ite.hasNext()){
                    MapEntry<K,V> entry=ite.next();
                    int h=entry.getHash();
                    if(h==0){
                        h=entry.getKey().hashCode();
                        entry.setHash(h);
                    }
                    int ticket=Math.abs(h)%SIZE;
                    if(newBuckets[ticket]==null){
                        newBuckets[ticket]=new LinkedList<MapEntry<K,V>>();
                        newBuckets[ticket].add(entry);
                    }
                    newBuckets[ticket].add(entry);
                }
            }
        }
        buckets=newBuckets;
    }

    private boolean isPrime(int num){
        if(num<=0){
            System.out.println("Give me a number positive!");
        }
        if(num==1 || num==2){return true;}
        for(int i=2;i<num-1;i++){
            if(num%i==0){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        RehashSimpleHashMap<String,String> m = new RehashSimpleHashMap<String,String>();
        m.putAll(Countries.capitals(50));
        System.out.println(m);
        System.out.println(m.get("ERITREA"));
        System.out.println(m.entrySet());
    }
}
Exercise39.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;

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

Exercise 40

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

public abstract class Pair{
    protected String a;
    protected String b;

    public Pair(String a,String b){this.a=a;this.b=b;}

    public String getA(){return a;}
    public String getB(){return b;}

    public String toString(){return "("+a+","+b+")";}
}
PairA.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;

public class PairA extends Pair implements Comparable<PairA>{

    public PairA(String x, String y){super(x,y);}

    @Override
    public int compareTo(PairA pair){
        return a.compareTo(pair.getA());
    }
}
PairB.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;

public class PairB extends Pair implements Comparable<PairB>{

    public PairB(String x, String y){super(x,y);}

    @Override
    public int compareTo(PairB pair){
        return b.compareTo(pair.getB());
    }
}
Exercise40.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;


class CompPairA implements Comparator<PairA>{
    public int compare(PairA x, PairA y){
        return x.compareTo(y);
    }
}
class CompPairB implements Comparator<PairB>{
    public int compare(PairB x, PairB y){
        return x.compareTo(y);
    }
}

public class Exercise40{
    public static void main(String[] args){
        Generator<String> gen=new RandomGenerator.String();
        PairA[] array=new PairA[10];
        List<PairA> list=new ArrayList<PairA>();

        String arrayNo4=null;
        String listNo8=null;
        for(int i=0;i<10;i++){
            String x=gen.next();
            String y=gen.next();
            if(i==3){
                arrayNo4=x;
            }
            if(i==7){
                listNo8=y;
            }
            array[i]=new PairA(x,y);
            list.add(new PairA(y,x));
        }

        CompPairA cpa=new CompPairA();
        Arrays.sort(array,cpa);
        System.out.println(Arrays.toString(array));
        PairA newArrayNode=new PairA(arrayNo4,gen.next());
        int indexArray=Arrays.binarySearch(array,newArrayNode,cpa);
        if(indexArray>=0){
            System.out.println(newArrayNode+"=="+array[indexArray]);
        }

        Collections.sort(list);
        System.out.println(list);
        PairA newListNode=new PairA(listNo8,gen.next());
        int indexList=Collections.binarySearch(list,newListNode,cpa);
        if(indexList>=0){
            System.out.println(newListNode+"=="+list.get(indexList));
        }
    }
}

Exercise 41

Pair.java

Pair基类不变

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

public abstract class Pair{
    protected String a;
    protected String b;

    public Pair(String a,String b){this.a=a;this.b=b;}

    public String getA(){return a;}
    public String getB(){return b;}

    public String toString(){return "("+a+","+b+")";}
}
PairA.java

为了在Set里使用,最好实现equals()和hashCode()方法。 为了在Map里使用,需要实现Map.Entry接口。

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

public class PairA extends Pair implements Comparable<PairA>, Map.Entry<String,String>{

    public PairA(String x, String y){super(x,y);}

    @Override
    public int compareTo(PairA pair){
        return a.compareTo(pair.getA());
    }

    /**
     *  For the Map
     */
    public String getKey(){return a;}
    public String getValue(){return b;}
    public String setValue(String v){
        String old=b;
        b=v;
        return old;
    }


    /**
     *  For the Set
     */
    @Override
    public int hashCode(){
        return a.hashCode();
    }
    @Override
    public boolean equals(Object o){
        if(!(o instanceof PairA)){
            return false;
        }
        return a.equals(((PairA)o).getA());
    }
}
PairB.java

和PairA同理

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

public class PairB extends Pair implements Comparable<PairB>,Map.Entry<String,String>{

    public PairB(String x, String y){super(x,y);}

    @Override
    public int compareTo(PairB pair){
        return b.compareTo(pair.getB());
    }

    /**
     *  For the Map
     */
    public String getKey(){return b;}
    public String getValue(){return a;}
    public String setValue(String v){
        String old=a;
        a=v;
        return old;
    }


    /**
     *  For the Set
     */
    @Override
    public int hashCode(){
        return b.hashCode();
    }
    @Override
    public boolean equals(Object o){
        if(!(o instanceof PairB)){
            return false;
        }
        return b.equals(((PairB)o).getB());
    }
    }
}
SimpleHashMap41.java

为了使用

package com.ciaoshen.thinkinjava.chap