容器的填充
实现容器抽象类
例子是一个“享元模式（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()”表达的是：
- 创建一个继承自CountriesMap的匿名类的对象。
这里仅仅是重写了entrySet()方法，就能够返回数据表不同大小的子块。这算是匿名内部类比较经典的应用场景了。
Collection接口
不多说，放张图，这几个方法是要记住的。总的来说，以一个List表为代表的一组容器，最典型的操作就这么几样：
- 读取元素：add(), addAll()
- 检查元素：contains(), containsAll(), isEmpty(), size()
- 改变元素：clear(), remove(), removeAll(), retainAll()
- 迭代器：iterator(), Iterator.hasNext(), Iterator.next(), Iterator.remove()
- 类型转换：toArray()
这些都是经过时间检验的“工程经验”。
注意一下迭代器光标Cursor位置：
可选操作
可选操作是个坑。它是指比如在Collection接口中，以下几个方法，
- retainAll()
- removeAll()
- clear()
- add()
- addAll()
- remove()
它们是可选方法。但仅仅是在官方文档的方法解释后面加了两个字“(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();
}
//... ...
//... ...
可选操作是坑？还是良好的设计？
书上对此的解释是：
- 因为Arrays.asList()生成的List，基于一个固定大小的数组，所以仅支持那些不会改变数组大小的操作，是有道理的。
我表示，很难接受这样的解释。这真的很坑。要么索性就重新取个名字，干嘛要取一样的名字骗我们呢。网上都把这个错误列为《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抽象类的源码。看到它是完全不依赖于任何数据而独立存在的。对它的简单描述应该是这样：
- 是个空壳，没有数据。
- 所有定义的操作全都指向一个假象的数据体。
- 操作和数据之间唯二的发生关系的途径是通过：get()和size()两个方法。而这两个方法是抽象方法，留给用户自己定义。
- 大致的思路就是以size()为界，用Iterator遍历元素。然后假设get()方法能返回元素。能完成几乎所有读取，查找，转换操作。
- 然后写操作的add()方法是未定义操作UnsupportedOperationException。
所以AbstractCollection是完全没有实体的。
List
工程模型和Collection是一致的，操作也分成：读取元素，检查元素，改变元素，迭代器，类型转换，这几大类。不赘述。
需要注意：List有个更强大的迭代器ListIterator。 遍历能往前，往后，双向移动。还有写操作add(),set()。看下图，
单向链表设计思路
比较重要的几个点，方便以后回顾比较：
- 节点的数据结构很清楚：一部分放数据，一部分是指向下一个节点的指针。
- 个人比较喜欢：前后两个固定的头节点head和尾节点tail。只站桩，无数据。
- 其中，只有头节点是必须的。无头节点的话，对第一个元素的操作会和其他元素不同，代码复杂化。
- 尾节点可以没有。可以让最后一个元素指向null。加尾节点是为了在末尾插入新元素更高效。不然就得从head遍历到最后一个元素，再插入。
- head.next指向第一个节点，tail.next指向最后一个节点。当链表为空，head.next=tail。 tail.next=head。
- cursor光标表示上一个next()方法返回的节点。
- previous引用盯住cursor。表示cursor的前一个节点。为了remove()的时候能找到前一个节点的向后引用。
- 每一次调用next()，只能用remove()方法删除一次当前节点。删除完，光标退回上一节点。
- 只有两种情况，previous和cursor指向同一个节点：要么初始阶段还没有调用过next()。要么next()返回的上一个节点被remove()方法删掉。
- previous和cursor永远不可能指向tail。
关于LinkedList头节点的总结：
- 头节点是不储存元素信息的纯功能性节点。用来停放指针。
- 单纯从功能上讲，单个头节点head就够了。不需要尾节点。
- 没有head头节点的话，大部分操作对第一个元素和后续元素，实现都不同。导致逻辑复杂。容易出bug。编程目标是不出错，不是为了挑战脑力。
- 不需要专门的桩子尾节点。但需要一个tail指针，指向末尾元素，方便从末尾插入新元素。
- 双头节点版本：一个头节点head，一个尾节点tail。也没什么不好。反而逻辑清楚。
- JDK里的官方LinkedList是没有头节点的版本。不知道为什么。难道是节约内存？
Set
Set主要有两个点：
- 内部元素唯一性。
- 维持特定的元素排序。不同类型Set的排序方式不同。
其中：
- HashSet：以散列值对set容量取余后决定的下标。没有规律。
- TreeSet：保持降序。
- LinkedHashSet：保持插入顺序。
Set对内部元素的要求
希望放入Set中的元素类型必须先实现一些特定方法：
- 所有实现Set接口的类，都要求内部元素实现equals()方法。为了保证唯一性。
- HashSet系的还要实现hashCode()方法。
- 以TreeSet为代表的SortedSet系需要内部元素实现Comparable接口。也就是实现compareTo()方法。
没有实现特定方法，存到Set里就会乱套。但编译器不会报错。因为默认的equals()和hashCode()虽然是错的，但是能运行的。
自定义Set
可以继承AbstractSet抽象类。因为AbstractSet继承自AbstractCollection抽象类。加在一起，基本实现了Set接口。但有几个关键方法还需要自己定义：
- add()
- size()
- iterator()
- Iterator
比如下面是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？贴一张图。
最常用的还是HashMap，效率最高。
自定义Map
自定义Map可以继承AbstractMap。但必须自己实现几个方法：
Map.Entry<K,V>接口- entrySet()方法
- put()方法
自定义Map的关键在于定义一个键值对的Pair：叫Map.Entry<K,V>的内部类接口。也可以用一个独立的类来实现这个接口。这个数据结构把Map里的一个“键-值”对捏合成单个元素。
然后定义一个“entrySet()”方法，返回一个Map.Entry元素的集合Set<Map.Entry<K,V>>。
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个逻辑条件：
- 自反性。x=x必须为true。
- 对称性。如果x=y为true，y=x也必须返回true。
- 传递性。如果x=y,y=z。那么x=z必须返回true。
- 一致性。在x和y都没变的情况下。每次测试x=y必须返回一样的结果。
- 任何不是null的x。x.equals(null)必须返回false。
散列值（hashCode()）
关于散列值，参见之前的一篇：《Java HashMap的哈希值是怎么计算的？》。 这里简单强调几个基本逻辑层次：
- HashMap的基本理念是：通过对内部数组直接下标访问，做到get()普通情况O(1).
- 下标访问的原理：对key键值执行hashCode()函数，生成散列值（一般比较大），然后对内部数组大小取余运算，获得数组下标。
- hashCode()在Object根类就定义了。几乎每个类都重写了这个方法。
- 自己写hashCode()要符合两个基本逻辑：第一，同一个对象每次的散列值必须相等。第二，两个equals()判定值相等的对象，散列值也要相等。
简单容器测试框架
非常简单的一个模块化封装实践，主要记住思路：
- testframework.Test.java: 框架模块1：封装测试类
- testframework.TestParam.java: 框架模块2：封装测试参数。
- testframework.Tester.java: 框架模块3：运行测试工具包。
- testframework.gen.*: 框架模块4：模拟数据生成器包。
最终实现的功能是：
- 可以自定义扩展测试类（Test.java定义）。
- 给一种容器，和一个参数包，自动对容器执行不同参数的全套测试。
关于垃圾回收再唐僧几句
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后不会被置入引用队列?》专题。
- Joshua Bloch在Effective 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的时机不同：
- 当一个对象只维持着WeakReference，直接被加入ReferenceQueue。然后等待被GC销毁。
- 当一个对象只维持着PhantomReference，GC先销毁对象，然后把这个虚引用加入ReferenceQueue。
WeakHashMap
- 内部类Entry直接继承WeakReference。
- 键值Key被包装成WeakReference的referent。
- 当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
- Exercise 1: (1) Create a List (try both ArrayList and LinkedList) and fill it using Countries. Sort the list and print it, then apply Collections.shuffle( ) to the list repeatedly, printing it each time so that you can see how the shuffle( ) method randomizes the list differently each time.
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
- Exercise 3: (1) Using Countries, fill a Set multiple times with the same data and verify that the Set ends up with only one of each instance. Try this with HashSet, LinkedHashSet, and TreeSet.
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
- Exercise 4: (2) Create a Collection initializer that opens a file and breaks it into words using TextFile, and then uses the words as the source of data for the resulting Collection. Demonstrate that it works.
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
- Exercise 5: (3) Modify CountingMapData.java to fully implement the flyweight by adding a custom EntrySet class like the one in Countries.java. ```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));
} } ```
Exercise 6
- Exercise 6: (2) Note that List has additional “optional” operations that are not included in Collection. Write a version of Unsupported.java that tests these additional optional operations.
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
- Exercise 7: (4) Create both an ArrayList and a LinkedList, and fill each using the Countries.names( ) generator. Print each list using an ordinary Iterator, then insert one list into the other by using a Listlterator, inserting at every other location. Now perform the insertion starting at the end of the first list and moving backward.
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头节点的总结：
- 头节点是不储存元素信息的纯功能性节点。用来停放指针。
- 单纯从功能上讲，单个头节点head就够了。不需要尾节点。
- 没有head头节点的话，大部分操作对第一个元素和后续元素，实现都不同。导致逻辑复杂。容易出bug。编程目标是不出错，不是为了挑战脑力。
- 不需要专门的桩子尾节点。但需要一个tail指针，指向末尾元素，方便从末尾插入新元素。
- 双头节点版本：一个头节点head，一个尾节点tail。也没什么不好。反而逻辑清楚。
- JDK里的官方LinkedList是没有头节点的版本。不知道为什么。难道是节约内存？
单头节点版本
- 单向列表
- 单头节点。只有前头节点head，无尾节点tail。
- tail只是一个指向最后一个元素的指针。
- 前中后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);
}
}
双头节点版本
- 单向列表
- 双头节点。前头节点head，后尾节点tail。两个节点永远不存放元素。尾节点的next指向最后一个元素。空链表时指向head。
- 两个光标：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);
} } ```
无头节点版本
- 单向列表
- 没有栓塞头
- head和tail只是两个指针，指向第一个和最后一个元素。
- 当链表为空：维持一个空节点。head和tail都指向这个空节点。只有一个元素的时候，head和tail也都指向唯一的这个节点。
- 两个光标：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
- Exercise 9: (2) Use RandomGenerator.String to fill a TreeSet, but use alphabetic ordering. Print the TreeSet to verify the sort order.
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
- Exercise 10: (7) Using a LinkedList as your underlying implementation, define your own SortedSet.
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
- Exercise 11: (2) Create a class that contains an Integer that is initialized to a value between o and 100 using java.util.Random. Implement Comparable using this Integer field. Fill a PriorityQueue with objects of your class, and extract the values using poll( ) to show that it produces the expected order.
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
- Exercise 12: (1) Substitute a HashMap, a TreeMap and a LinkedHashMap in AssociativeArray .Java’s main( ).
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
- Exercise 13: (4) Use AssociativeArray Java to create a wordoccurrence counter, mapping String to Integer. Using the net.mindview.util.TextFile utility in this book, open a text file and break up the words in that file using whitespace and punctuation, and count the occurrence of the words in that file.
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
- Exercise 14: (3) Show that java.util.Properties works in the above program.
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
- Exercise 15: (1) Repeat Exercise 13 using a SlowMap.
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
- Exercise 16: (7) Apply the tests in Maps.java to SlowMap to verify that it works. Fix anything in SlowMap that doesn’t work correctly. SlowMap里EntrySet是享元化的，没有set实体。里面只有一个Iterator返回视图。 实体化只有在要打印的时候，在Abstract.toString()里完成。
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
- Exercise 18: (3) Using SlowMap.java for inspiration, create a SlowSet.
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
- Exercise 19: (1) Repeat Exercise 13 using a SimpleHashMap.
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
- Exercise 20: (3) Modify SimpleHashMap so that it reports collisions, and test this by adding the same data set twice so that you see collisions.
只要在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
- Exercise 21: (2) Modify SimpleHashMap so that it reports the number of “probes” necessary when collisions occur. That is, how many calls to next( ) must be made on the Iterators that walk the LinkedLists looking for matches?
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
- Exercise 24: (5) Following the example in SimpleHashMap.java, create and test a SimpleHashSet.
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
- Exercise 25: (6) Instead of using a Listlterator for each bucket, modify MapEntry so that it is a self-contained singly linked list (each MapEntry should have a forward link to the next MapEntry). Modify the rest of the code in SimpleHashMap.java so that this new approach works correctly.
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
- Exercise 26: (2) Add a char field to CountedString that is also initialized in the constructor, and modify the hashCode( ) and equals( ) methods to include the value of this char.
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
- Exercise 27: (3) Modify the hashCode( ) in CountedString.java by removing the combination with id, and demonstrate that CountedString still works as a key. What is the problem with this approach? 如果hashCode()没有绑定所有的域，本质上不会影响这个类作为Map的键使用。因为不会出现重复的键值。
但还是存在一定问题：不同的对象，在HashMap里有同样的键值。也就是，部分对象会被其他不同的对象替换掉，因为有相同的键值。练习中，下面4个不同的对象，拥有相同的散列值。
- A-Hi-1
- A-Hi-2
- A-Hi-3
- A-Hi-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
- Exercise 28: (4) Modify net/mindview/util/Tuple.java to make it a general-purpose class by adding hashCode( ), equals( ), and implementing Comparable for each type of Tuple.
Tuple.java
这里实现的是Comparable
比如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
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
- Exercise 29: (2) Modify ListPerformance.java so that the Lists hold String objects instead of Integers. Use a Generator from the Arrays chapter to create test values.
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
- Exercise 30: (3) Compare the performance of Collections.sort( ) between an ArrayList and a LinkedList. ArrayList和LinkedList在较大规模的测试下，效率基本一致。
因为，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
- Exercise 31: (5) Create a container that encapsulates an array of String, and that only allows adding Strings and getting Strings, so that there are no casting issues during use. If the internal array isn’t big enough for the next add, your container should automatically resize it. In main( ), compare the performance of your container with an ArrayList
.
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
- Exercise 32: (2) Repeat the previous exercise for a container of int, and compare the performance to an ArrayList
. In your performance comparison, include the process of incrementing each object in the container.
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
- Exercise 33: (5) Create a FastTraversalLinkedList that internally uses a LinkedList for rapid insertions and removals, and an ArrayList for rapid traversals and get( ) operations. Test it by modifying ListPerformance.java.
- 插入，移除用LinkdList
- 遍历，set(),get()用ArrayList
- ListIterator(int index)接口用来返回LinkedList的迭代器
- 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
- Exercise 34: (1) Modify SetPerformance.java so that the Sets hold String objects instead of Integers. Use a Generator from the Arrays chapter to create test values.
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
- Exercise 35: (1) Modify MapPerformance.java to include tests of SlowMap.
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
- Exercise 36: (5) Modify SlowMap so that instead of two ArrayLists, it holds a single ArrayList of MapEntry objects. Verify that the modified version works correctly. Using MapPerformance.java, test the speed of your new Map. Now change the put( ) method so that it performs a sort( ) after each pair is entered, and modify get( ) to use Collections.binarySearch( ) to look up the key. Compare the performance of the new version with the old ones.
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
- Exercise 37: (2) Modify SimpleHashMap to use ArrayLists instead of LinkedLists. Modify MapPerformance.java to compare the performance of the two implementations.
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
- Exercise 38: (3) Look up the HashMap class in the JDK documentation. Create a HashMap, fill it with elements, and determine the load factor. Test the lookup speed with this map, then attempt to increase the speed by making a new HashMap with a larger initial capacity and copying the old map into the new one, then run your lookup speed test again on the new map.
#####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
- Exercise 39: (6) Add a private rehash( ) method to SimpleHashMap that is invoked when the load factor exceeds 0.75. During rehashing, double the number of buckets, then search for the first prime number greater than that to determine the new number of buckets.
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
- Exercise 40: (5) Create a class containing two String objects and make it Comparable so that the comparison only cares about the first String. Fill an array and an ArrayList with objects of your class, using the RandomGenerator generator. Demonstrate that sorting works properly. Now make a Comparator that only cares about the second String, and demonstrate that sorting works properly. Also perform a binary search using your Comparator.
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
- Exercise 41: (3) Modify the class in the previous exercise so that it will work with HashSets and as a key in HashMaps.
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.chapter17;
import java.util.*;
public class SimpleHashMap41 extends AbstractMap<String,String> {
static final int SIZE = 997;
@SuppressWarnings(value={"unchecked","rawtypes"})
LinkedList<PairA>[] buckets = new LinkedList[SIZE];
public String put(String key, String value) {
String oldValue = null;
int index = Math.abs(key.hashCode()) % SIZE;
if(buckets[index] == null)
buckets[index] = new LinkedList<PairA>();
LinkedList<PairA> bucket = buckets[index];
PairA pair = new PairA(key, value);
boolean found = false;
ListIterator<PairA> it = bucket.listIterator();
while(it.hasNext()) {
PairA 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 String get(Object key) {
int index = Math.abs(key.hashCode()) % SIZE;
if(buckets[index] == null) return null;
for(PairA iPair : buckets[index])
if(iPair.getKey().equals(key))
return iPair.getValue();
return null;
}
public Set<Map.Entry<String,String>> entrySet() {
Set<Map.Entry<String,String>> set= new HashSet<Map.Entry<String,String>>();
for(LinkedList<PairA> bucket : buckets) {
if(bucket == null) continue;
for(PairA mpair : bucket)
set.add(mpair);
}
return set;
}
}
Exercise41.java
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
public class Exercise41{
public static void runMap(){
Map<String,String> m = new SimpleHashMap41();
m.putAll(Countries.capitals(25));
System.out.println(m);
System.out.println(m.get("BENIN"));
System.out.println(m.entrySet());
}
public static void runSet(){
Set<PairA> set1=new LinkedHashSet<PairA>();
Set<PairA> set2=new TreeSet<PairA>();
RandomGenerator.String gen=new RandomGenerator.String(1);
for(int i=0;i<20;i++){
set1.add(new PairA(gen.next(),gen.next()));
set2.add(new PairA(gen.next(),gen.next()));
}
Sets.test(set1,set2);
}
public static void main(String[] args) {
Exercise41.runMap();
Exercise41.runSet();
}
}
Exercise 42
- Exercise 42: (2) Modify Exercise 40 so that an alphabetic sort is used.
PairA和PairB都不变。
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());
}
}
Exercise42.java
就是把Comparator改成用String自带的忽略大小写的CASE_INSENSITIVE_ORDER。
package com.ciaoshen.thinkinjava.chapter17;
import java.util.*;
class CompPairA implements Comparator<PairA>{
public int compare(PairA x, PairA y){
return String.CASE_INSENSITIVE_ORDER.compare(x.getA(),y.getA());
}
}
class CompPairB implements Comparator<PairB>{
public int compare(PairB x, PairB y){
return String.CASE_INSENSITIVE_ORDER.compare(x.getB(),y.getB());
}
}
public class Exercise42{
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));
}
}
}