Java编程思想之十七 容器深入研究
17.1 完整的容器分类方法
17.2 填充容器
import java.util.*;
class StringAddress {
private String s;
public StringAddress(String s) { this.s = s; }
public String toString() {
return super.toString() + " " + s;
}
}
public class FillingLists {
public static void main(String[] args) {
List list= new ArrayList(
Collections.nCopies(4, new StringAddress("Hello")));//创建并填充
System.out.println(list);
Collections.fill(list, new StringAddress("World!"));//只能用于替换已有的元素
System.out.println(list);
}
} /* Output: (Sample)
[StringAddress@82ba41 Hello, StringAddress@82ba41 Hello, StringAddress@82ba41 Hello, StringAddress@82ba41 Hello]
[StringAddress@923e30 World!, StringAddress@923e30 World!, StringAddress@923e30 World!, StringAddress@923e30 World!]
*///:~
17.2.1 一种Generator解决方案
所有的Collection子类型都有一个接受另一个Collection对象的构造器，用所接受的Collection对象种的元素来填充新的容器。
import java.util.*;
import net.mindview.util.*;
class Government implements Generator {
String[] foundation = ("strange women lying in ponds " +
"distributing swords is no basis for a system of " +
"government").split(" ");
private int index;
public String next() { return foundation[index++]; }
}
public class CollectionDataTest {
public static void main(String[] args) {
Set set = new LinkedHashSet(
new CollectionData(new Government(), 15));
System.out.println(set);
// Using the convenience method:
List list=new ArrayList<>();
list.addAll(CollectionData.list(new Government(), 15));
System.out.println(list);
}
} /* Output:
[strange, women, lying, in, ponds, distributing, swords, is, no, basis, for, a, system, of, government]
*///:~
17.2.2 Map生成器
Map适配器现在都可以使用各种不同的Generator、Iterator和常量值的组合来填充Map初始化对象：
package net.mindview.util;
import java.util.Iterator;
import java.util.LinkedHashMap;
public class MapData extends LinkedHashMap {
public MapData(Generator> gen, int quantity) {
for(int i = 0; i < quantity; ++i) {
Pair p = (Pair)gen.next();
this.put(p.key, p.value);
}
}
public MapData(Generator genK, Generator genV, int quantity) {
for(int i = 0; i < quantity; ++i) {
this.put(genK.next(), genV.next());
}
}
public MapData(Generator genK, V value, int quantity) {
for(int i = 0; i < quantity; ++i) {
this.put(genK.next(), value);
}
}
public MapData(Iterable genK, Generator genV) {
Iterator var4 = genK.iterator();
while(var4.hasNext()) {
K key = (Object)var4.next();
this.put(key, genV.next());
}
}
public MapData(Iterable genK, V value) {
Iterator var4 = genK.iterator();
while(var4.hasNext()) {
K key = (Object)var4.next();
this.put(key, value);
}
}
public static MapData map(Generator> gen, int quantity) {
return new MapData(gen, quantity);
}
public static MapData map(Generator genK, Generator genV, int quantity) {
return new MapData(genK, genV, quantity);
}
public static MapData map(Generator genK, V value, int quantity) {
return new MapData(genK, value, quantity);
}
public static MapData map(Iterable genK, Generator genV) {
return new MapData(genK, genV);
}
public static MapData map(Iterable genK, V value) {
return new MapData(genK, value);
}
}
下面是一个使用MapData的示例。LettersGenerator通过产生一个Iterator还实现了Iterable，通过这种方式，它可以被用来测试MapData.map()方式，而这些方法都需要用到Iterable：
import java.util.*;
import net.mindview.util.*;
import static net.mindview.util.Print.*;
class Letters implements Generator>,
Iterable {
private int size = 9;
private int number = 1;
private char letter = 'A';
public Pair next() {
return new Pair(
number++, "" + letter++);
}
public Iterator iterator() {
return new Iterator() {
public Integer next() { return number++; }
public boolean hasNext() { return number < size; }
public void remove() {
throw new UnsupportedOperationException();
}
};
}
}
public class MapDataTest {
public static void main(String[] args) {
// Pair Generator:
print(MapData.map(new Letters(), 11));
// Two separate generators:
print(MapData.map(new CountingGenerator.Character(),
new RandomGenerator.String(3), 8));
// A key Generator and a single value:
print(MapData.map(new CountingGenerator.Character(),
"Value", 6));
// An Iterable and a value Generator:
print(MapData.map(new Letters(),
new RandomGenerator.String(3)));
// An Iterable and a single value:
print(MapData.map(new Letters(), "Pop"));
}
} /* Output:
{1=A, 2=B, 3=C, 4=D, 5=E, 6=F, 7=G, 8=H, 9=I, 10=J, 11=K}
{a=YNz, b=brn, c=yGc, d=FOW, e=ZnT, f=cQr, g=Gse, h=GZM}
{a=Value, b=Value, c=Value, d=Value, e=Value, f=Value}
{1=mJM, 2=RoE, 3=suE, 4=cUO, 5=neO, 6=EdL, 7=smw, 8=HLG}
{1=Pop, 2=Pop, 3=Pop, 4=Pop, 5=Pop, 6=Pop, 7=Pop, 8=Pop}
*///:~
17.3 Collection的功能方法
下面展示了Collection所有这些方法：
import java.util.*;
import net.mindview.util.*;
import static net.mindview.util.Print.*;
public class CollectionMethods {
public static void main(String[] args) {
Collection c = new ArrayList();
c.addAll(Countries.names(6));
c.add("ten");
c.add("eleven");
print(c);
// Make an array from the List:
Object[] array = c.toArray();
// Make a String array from the List:
String[] str = c.toArray(new String[0]);//将list转换为需要的数组
System.out.println("str="+Arrays.deepToString(str));
// Find max and min elements; this means
// different things depending on the way
// the Comparable interface is implemented:
print("Collections.max(c) = " + Collections.max(c));
print("Collections.min(c) = " + Collections.min(c));
// Add a Collection to another Collection
Collection c2 = new ArrayList();
c2.addAll(Countries.names(6));
c.addAll(c2);
print(c);
c.remove(Countries.DATA[0][0]);
print(c);
c.remove(Countries.DATA[1][0]);
print(c);
// Remove all components that are
// in the argument collection:
c.removeAll(c2);
print(c);
c.addAll(c2);
print(c);
// Is an element in this Collection?
String val = Countries.DATA[3][0];
print("c.contains(" + val + ") = " + c.contains(val));
// Is a Collection in this Collection?
print("c.containsAll(c2) = " + c.containsAll(c2));
Collection c3 =
((List)c).subList(3, 5);
// Keep all the elements that are in both
// c2 and c3 (an intersection of sets):
c2.retainAll(c3);
print(c2);
// Throw away all the elements
// in c2 that also appear in c3:
c2.removeAll(c3);
print("c2.isEmpty() = " + c2.isEmpty());
c = new ArrayList();
c.addAll(Countries.names(6));
print(c);
c.clear(); // Remove all elements
print("after c.clear():" + c);
}
}
17.4 可选操作
执行各种不同的添加和移除的方法在Collection接口中都是可选操作。这意味着实现类并不需要为这些方法提供功能定义。
接口是面向对象设计中的契约，它声明"无论你选择如何实现该接口，我保证你可以向该接口发送这些消息"。但是可选操作违反这个非常基本的原则，它声明调用某些方法将不会执行有意义的行为。
"未获支持的操作"这种方式可以实现Java容器类库一个重要目标：容器应该易学易用。未获支持的操作是一种特例，可以延迟到需要时在实现。
为了让你种方式能够工作：
- UnsupportedOperationException必须是一种罕见事件。对于大多数类来说，所有操作都应该可以工作，只有在特例中才会有未获支持的操作。
- 如果一个操作未获支持的，那么在实现接口的时候可能会导致 UnsupportedOperationException异常，而不是将产品程序交给客户以后才出现异常。它表示编程上有错误：使用了不正确的接口实现。
- 未获支持的操作只有在运行时才能检测到，因此它们表示动态类型检查。
17.4.1 未获支持的操作
当你用Arrays.aslist()将数组转换未List时，就会得到这样的容器。你可以通过使用Collections类中"不可修改"的方法，选择创建任何会抛出 UnsupportedOperationException的容器。
import java.util.*;
public class Unsupported {
static void test(String msg, List list) {
System.out.println("--- " + msg + " ---");
Collection c = list;
Collection subList = list.subList(1,8);
// Copy of the sublist:
Collection c2 = new ArrayList(subList);
try { c.retainAll(c2); } catch(Exception e) {
System.out.println("retainAll(): " + e);
}
try { c.removeAll(c2); } catch(Exception e) {
System.out.println("removeAll(): " + e);
}
try { c.clear(); } catch(Exception e) {
System.out.println("clear(): " + e);
}
try { c.add("X"); } catch(Exception e) {
System.out.println("add(): " + e);
}
try { c.addAll(c2); } catch(Exception e) {
System.out.println("addAll(): " + e);
}
try { c.remove("C"); } catch(Exception e) {
System.out.println("remove(): " + e);
}
// The List.set() method modifies the value but
// doesn't change the size of the data structure:
try {
list.set(0, "X");
} catch(Exception e) {
System.out.println("List.set(): " + e);
}
}
public static void main(String[] args) {
List list =
Arrays.asList("A B C D E F G H I J K L".split(" "));//返回固定尺寸的List
test("Modifiable Copy", new ArrayList(list));
test("Arrays.asList()", list);//
test("unmodifiableList()",
Collections.unmodifiableList(
new ArrayList(list)));//产生不可修改的列表，任何情况下都不可修改
}
} /* Output:
--- Modifiable Copy ---
--- Arrays.asList() ---
retainAll(): java.lang.UnsupportedOperationException
removeAll(): java.lang.UnsupportedOperationException
clear(): java.lang.UnsupportedOperationException
add(): java.lang.UnsupportedOperationException
addAll(): java.lang.UnsupportedOperationException
remove(): java.lang.UnsupportedOperationException
--- unmodifiableList() ---
retainAll(): java.lang.UnsupportedOperationException
removeAll(): java.lang.UnsupportedOperationException
clear(): java.lang.UnsupportedOperationException
add(): java.lang.UnsupportedOperationException
addAll(): java.lang.UnsupportedOperationException
remove(): java.lang.UnsupportedOperationException
List.set(): java.lang.UnsupportedOperationException
*///:~
Arrays.asList()会生成一个List，它基于一个固定大小的数组，仅支持那些不会改变数组大小的操作。任何会引起对底层数据结构尺寸进行修改的方法都会产生 UnsupportedOperationException异常，以表示对未获取支持操作的调用。
17.5 List基本功能方法
基本的LIst很容易使用：add()添加对象，get()一次取出一个元素，iterator()获取用于该序列的Iterator。
下面的例子每个方法都涵盖了不同动作：
import java.util.*;
import net.mindview.util.*;
import static net.mindview.util.Print.*;
public class Lists {
private static boolean b;
private static String s;
private static int i;
private static Iterator it;
private static ListIterator lit;
public static void basicTest(List a) {//包含每个List都可执行的操作
a.add(1, "x"); // Add at location 1
a.add("x"); // Add at end
// Add a collection:
a.addAll(Countries.names(25));
// Add a collection starting at location 3:
a.addAll(3, Countries.names(25));
b = a.contains("1"); // Is it in there?
// Is the entire collection in there?
b = a.containsAll(Countries.names(25));
// Lists allow random access, which is cheap
// for ArrayList, expensive for LinkedList:
s = a.get(1); // Get (typed) object at location 1
i = a.indexOf("1"); // Tell index of object
b = a.isEmpty(); // Any elements inside?
it = a.iterator(); // Ordinary Iterator
lit = a.listIterator(); // ListIterator
lit = a.listIterator(3); // Start at loc 3
i = a.lastIndexOf("1"); // Last match
a.remove(1); // Remove location 1
a.remove("3"); // Remove this object
a.set(1, "y"); // Set location 1 to "y"
// Keep everything that's in the argument
// (the intersection of the two sets):
a.retainAll(Countries.names(25));
// Remove everything that's in the argument:
a.removeAll(Countries.names(25));
i = a.size(); // How big is it?
a.clear(); // Remove all elements
}
public static void iterMotion(List a) {//使用Iterator遍历元素
ListIterator it = a.listIterator();
b = it.hasNext();
b = it.hasPrevious();
s = it.next();
i = it.nextIndex();
s = it.previous();
i = it.previousIndex();
}
public static void iterManipulation(List a) {//使用Iterator修改元素
ListIterator it = a.listIterator();
it.add("47");
// Must move to an element after add():
it.next();
// Remove the element after the newly produced one:
it.remove();
// Must move to an element after remove():
it.next();
// Change the element after the deleted one:
it.set("47");
}
public static void testVisual(List a) {//查看List的操作效果
print(a);
List b = Countries.names(25);
print("b = " + b);
a.addAll(b);
a.addAll(b);
print(a);
// Insert, remove, and replace elements
// using a ListIterator:
ListIterator x = a.listIterator(a.size()/2);
x.add("one");
print(a);
print(x.next());
x.remove();
print(x.next());
x.set("47");
print(a);
// Traverse the list backwards:
x = a.listIterator(a.size());
while(x.hasPrevious())
printnb(x.previous() + " ");
print();
print("testVisual finished");
}
// There are some things that only LinkedLists can do:
public static void testLinkedList() {//LinkedList专用的操作
LinkedList ll = new LinkedList();
ll.addAll(Countries.names(25));
print(ll);
// Treat it like a stack, pushing:
ll.addFirst("one");
ll.addFirst("two");
print(ll);
// Like "peeking" at the top of a stack:
print(ll.getFirst());
// Like popping a stack:
print(ll.removeFirst());
print(ll.removeFirst());
// Treat it like a queue, pulling elements
// off the tail end:
print(ll.removeLast());
print(ll);
}
public static void main(String[] args) {
// Make and fill a new list each time:
basicTest(
new LinkedList(Countries.names(25)));
basicTest(
new ArrayList(Countries.names(25)));
iterMotion(
new LinkedList(Countries.names(25)));
iterMotion(
new ArrayList(Countries.names(25)));
iterManipulation(
new LinkedList(Countries.names(25)));
iterManipulation(
new ArrayList(Countries.names(25)));
testVisual(
new LinkedList(Countries.names(25)));
testLinkedList();
}
} /* (Execute to see output) *///:~
17.6 Set和存储顺序
| 类型 | 描述 |
|---|---|
| Set(interface) | 存入Set的每个元素都必须是唯一的，因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。 |
| HashSet | 为快速查找而设计的Set。存入HashSet的元素必须定义hashCode() |
| TreeSet | 保持次序的Set，底层为树结构。使用它可以从set中提取有序的序列。元素必须实现Comparable接口 |
| LinkedHashSet | 具有HashSet的查询速度，且内部使用链表维护元素的顺序。 |
| 使用特定的Set实现类型而必须定义的方法： |
import java.util.*;
class SetType {
int i;
public SetType(int n) { i = n; }
public boolean equals(Object o) {
return o instanceof SetType && (i == ((SetType)o).i);
}
public String toString() { return Integer.toString(i); }
}
class HashType extends SetType {
public HashType(int n) { super(n); }
public int hashCode() { return i; }
}
class TreeType extends SetType
implements Comparable {
public TreeType(int n) { super(n); }
public int compareTo(TreeType arg) {
return (arg.i < i ? -1 : (arg.i == i ? 0 : 1));
}
}
public class TypesForSets {
static Set fill(Set set, Class type) {
try {
for(int i = 0; i < 10; i++)
set.add(
type.getConstructor(int.class).newInstance(i));
} catch(Exception e) {
throw new RuntimeException(e);
}
return set;
}
static void test(Set set, Class type) {
fill(set, type);
fill(set, type); // Try to add duplicates
fill(set, type);
System.out.println(set);
}
public static void main(String[] args) {
test(new HashSet(), HashType.class);//实现hashCode确保排序并且不会重复
test(new LinkedHashSet(), HashType.class);
test(new TreeSet(), TreeType.class);//实现Comparable接口排序并不会重复
// Things that don't work:
test(new HashSet(), SetType.class);
test(new HashSet(), TreeType.class);
test(new LinkedHashSet(), SetType.class);
test(new LinkedHashSet(), TreeType.class);
try {
test(new TreeSet(), SetType.class);
} catch(Exception e) {
System.out.println(e.getMessage());
}
try {
test(new TreeSet(), HashType.class);
} catch(Exception e) {
System.out.println(e.getMessage());
}
}
} /* Output: (Sample)
[2, 4, 9, 8, 6, 1, 3, 7, 5, 0]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
[9, 9, 7, 5, 1, 2, 6, 3, 0, 7, 2, 4, 4, 7, 9, 1, 3, 6, 2, 4, 3, 0, 5, 0, 8, 8, 8, 6, 5, 1]
[0, 5, 5, 6, 5, 0, 3, 1, 9, 8, 4, 2, 3, 9, 7, 3, 4, 4, 0, 7, 1, 9, 6, 2, 1, 8, 2, 8, 6, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
java.lang.ClassCastException: SetType cannot be cast to java.lang.Comparable
java.lang.ClassCastException: HashType cannot be cast to java.lang.Comparable
*///:~
17.6.1 SortedSet
SortedSet可以确保元素处于排序状态下：
import java.util.*;
import static net.mindview.util.Print.*;
public class SortedSetDemo {
public static void main(String[] args) {
SortedSet sortedSet = new TreeSet();
Collections.addAll(sortedSet,
"one two three four five six seven eight"
.split(" "));
print(sortedSet);
String low = sortedSet.first();//返回第一个元素
String high = sortedSet.last();//返回最后一个元素
print(low);
print(high);
Iterator it = sortedSet.iterator();
for(int i = 0; i <= 6; i++) {
if(i == 3) low = it.next();
if(i == 6) high = it.next();
else it.next();
}
print(low);
print(high);
print(sortedSet.subSet(low, high));//生成此Set子集，从low到high
print(sortedSet.headSet(high));//生成此Set子集，小于high
print(sortedSet.tailSet(low));//生成此Set子集，大于等于low
}
}
17.7 队列
Queue在Java SE5中仅有的两个实现LinkedList和PriorityQueue，它们的差异在于排序行为而不是性能。
Queue实现的大部分操作的基本示例：
import java.util.concurrent.*;
import java.util.*;
import net.mindview.util.*;
public class QueueBehavior {
private static int count = 10;
static void test(Queue queue, Generator gen) {
for(int i = 0; i < count; i++)
queue.offer(gen.next());
while(queue.peek() != null)
System.out.print(queue.remove() + " ");
System.out.println();
}
static class Gen implements Generator {
String[] s = ("one two three four five six seven " +
"eight nine ten").split(" ");
int i;
public String next() { return s[i++]; }
}
public static void main(String[] args) {
test(new LinkedList(), new Gen());
test(new PriorityQueue(), new Gen());
test(new ArrayBlockingQueue(count), new Gen());
test(new ConcurrentLinkedQueue(), new Gen());
test(new LinkedBlockingQueue(), new Gen());
test(new PriorityBlockingQueue(), new Gen());
}
} /* Output:
one two three four five six seven eight nine ten
eight five four nine one seven six ten three two
one two three four five six seven eight nine ten
one two three four five six seven eight nine ten
one two three four five six seven eight nine ten
eight five four nine one seven six ten three two
*///:~
17.7.1 优先级队列
import java.util.*;
class ToDoList extends PriorityQueue {
static class ToDoItem implements Comparable {
private char primary;
private int secondary;
private String item;
public ToDoItem(String td, char pri, int sec) {
primary = pri;
secondary = sec;
item = td;
}
public int compareTo(ToDoItem arg) {
if(primary > arg.primary)
return +1;
if(primary == arg.primary)
if(secondary > arg.secondary)
return +1;
else if(secondary == arg.secondary)
return 0;
return -1;
}
public String toString() {
return Character.toString(primary) +
secondary + ": " + item;
}
}
public void add(String td, char pri, int sec) {
super.add(new ToDoItem(td, pri, sec));
}
public static void main(String[] args) {
ToDoList toDoList = new ToDoList();
toDoList.add("Empty trash", 'C', 4);
toDoList.add("Feed dog", 'A', 2);
toDoList.add("Feed bird", 'B', 7);
toDoList.add("Mow lawn", 'C', 3);
toDoList.add("Water lawn", 'A', 1);
toDoList.add("Feed cat", 'B', 1);
while(!toDoList.isEmpty())System.out.println(toDoList.remove());
}
} /* Output:
A1: Water lawn
A2: Feed dog
B1: Feed cat
B7: Feed bird
C3: Mow lawn
C4: Empty trash
*///:~
17.7.2 双向队列
双向队列就像是一个队列，但是以可以在任何一端添加或移除元素。
实现一个双向队列：
package net.mindview.util;
import java.util.LinkedList;
public class Deque {
private LinkedList deque = new LinkedList();
public Deque() {
}
public void addFirst(T e) {
this.deque.addFirst(e);
}
public void addLast(T e) {
this.deque.addLast(e);
}
public T getFirst() {
return this.deque.getFirst();
}
public T getLast() {
return this.deque.getLast();
}
public T removeFirst() {
return this.deque.removeFirst();
}
public T removeLast() {
return this.deque.removeLast();
}
public int size() {
return this.deque.size();
}
public String toString() {
return this.deque.toString();
}
}
测试Deque：
import net.mindview.util.*;
import static net.mindview.util.Print.*;
public class DequeTest {
static void fillTest(Deque deque) {
for(int i = 20; i < 27; i++)
deque.addFirst(i);
for(int i = 50; i < 55; i++)
deque.addLast(i);
}
public static void main(String[] args) {
Deque di = new Deque();
fillTest(di);
print(di);
while(di.size() != 0)
printnb(di.removeFirst() + " ");
print();
fillTest(di);
while(di.size() != 0)
printnb(di.removeLast() + " ");
}
} /* Output:
[26, 25, 24, 23, 22, 21, 20, 50, 51, 52, 53, 54]
26 25 24 23 22 21 20 50 51 52 53 54
54 53 52 51 50 20 21 22 23 24 25 26
*///:~
17.8 理解Map
映射表(关联数组)的基本思想是它维护的是键-值对关联，因此你可以使用建来查找值。标准的Java类库中包含了Map的几种基本实现，包括：HashMap，TreeMap,LinkedHashMap,WeakHashMap,ConcurrentHashMap,IdentityHashMap。它们都有同样的基本接口Map。
下面对Map简单实现：
import static net.mindview.util.Print.*;
public class AssociativeArray {
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 static void main(String[] args) {
AssociativeArray map =
new AssociativeArray(6);
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) {
print("Too many objects!");
}
print(map);
print(map.get("ocean"));
}
}
17.8.1 性能
HashMap使用了特殊的值，称作散列码，来取代对健的缓慢搜索。
| 名称 | 描述 |
|---|---|
| HashMap | Map基于散列表的实现。插入和查询键值对的开销是固定的。可以i通过构造器设置容量和负载因子，以调整容器的性能 |
| LinkedHashMap | 类似于HashMap，但是迭代遍历它时，取得键值对的顺序是其插入次序，或者是最近最少使用(LRU)次序。只比HashMap慢一点。而在迭代访问时反而更快，因为它使用链表维护内部次序 |
| TreeMap | 基于红黑树的实现，是唯一带有subMap()的Map |
| WeakHashMap | 弱键映射，允许释放映射所指向的对象 |
| ConcurrentHashMap | 一种线程安全的Map，不涉及同步锁 |
| IdentityHashMap | 使用==代替equals()对键进行比较的散列映射 |
| 散列是映射中存储元素时最常用的方式。 | |
| 对Map中使用的键要求与对Set中的元素要求一致。 | |
| 展示通过Map接口可用的操作： |
import java.util.concurrent.*;
import java.util.*;
import net.mindview.util.*;
import static net.mindview.util.Print.*;
public class Maps {
public static void printKeys(Map map) {
printnb("Size = " + map.size() + ", ");
printnb("Keys: ");
print(map.keySet()); // Produce a Set of the keys
}
public static void test(Map map) {
print(map.getClass().getSimpleName());
map.putAll(new CountingMapData(25));
// Map has 'Set' behavior for keys:
map.putAll(new CountingMapData(25));
printKeys(map);
// Producing a Collection of the values:
printnb("Values: ");
print(map.values());
print(map);
print("map.containsKey(11): " + map.containsKey(11));
print("map.get(11): " + map.get(11));
print("map.containsValue(\"F0\"): "
+ map.containsValue("F0"));
Integer key = map.keySet().iterator().next();
print("First key in map: " + key);
map.remove(key);
printKeys(map);
map.clear();
print("map.isEmpty(): " + map.isEmpty());
map.putAll(new CountingMapData(25));
// Operations on the Set change the Map:
map.keySet().removeAll(map.keySet());
print("map.isEmpty(): " + map.isEmpty());
}
public static void main(String[] args) {
test(new HashMap());
test(new TreeMap());
test(new LinkedHashMap());
test(new IdentityHashMap());
test(new ConcurrentHashMap());
test(new WeakHashMap());
}
}
17.8.2 SortedMap
使用SortedMap(TreeMap是其现阶段唯一实现)，可以确保键处于排序状态。
import java.util.*;
import net.mindview.util.*;
import static net.mindview.util.Print.*;
public class SortedMapDemo {
public static void main(String[] args) {
TreeMap sortedMap =
new TreeMap(new CountingMapData(10));
print(sortedMap);
Integer low = sortedMap.firstKey();
Integer high = sortedMap.lastKey();
print(low);
print(high);
Iterator it = sortedMap.keySet().iterator();
for(int i = 0; i <= 6; i++) {
if(i == 3) low = it.next();
if(i == 6) high = it.next();
else it.next();
}
print(low);
print(high);
print(sortedMap.subMap(low, high));
print(sortedMap.headMap(high));
print(sortedMap.tailMap(low));
}
}
17.8.3 LinkedHashMap
为了提高速度，LinkedHashMap散列化所有的元素，但是在遍历键值对时，却又以元素的插入顺序返回键值对。
可以在构造器中设定LinkedHashMap，使之采用基于访问最近最少使用算法，于是没有被访问过的元素就会出现在队列的前面。
import java.util.*;
import net.mindview.util.*;
import static net.mindview.util.Print.*;
public class LinkedHashMapDemo {
public static void main(String[] args) {
LinkedHashMap linkedMap =
new LinkedHashMap(
new CountingMapData(9));
print(linkedMap);
// Least-recently-used order:
linkedMap =
new LinkedHashMap(16, 0.75f, true);
linkedMap.putAll(new CountingMapData(9));
print(linkedMap);
for(int i = 0; i < 6; i++) // Cause accesses:
linkedMap.get(i);
print(linkedMap);
linkedMap.get(0);
print(linkedMap);
}
} /* Output:
{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0}
{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0}
{6=G0, 7=H0, 8=I0, 0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0}
{6=G0, 7=H0, 8=I0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 0=A0}
*///:~
17.9 散列与散列码
当自己创建用作HashMap的键的类，有可能会忘记在其中放置必须的方法，而这是通常会犯的一个错误：
public class Groundhog {
protected int number;
public Groundhog(int n) { number = n; }
public String toString() {
return "Groundhog #" + number;
}
}
import java.util.*;
public class Prediction {
private static Random rand = new Random(47);
private boolean shadow = rand.nextDouble() > 0.5;
public String toString() {
if(shadow)
return "Six more weeks of Winter!";
else
return "Early Spring!";
}
} ///:~
import java.lang.reflect.*;
import java.util.*;
import static net.mindview.util.Print.*;
public class SpringDetector {
// Uses a Groundhog or class derived from Groundhog:
public static
void detectSpring(Class type) throws Exception {
Constructor ghog = type.getConstructor(int.class);// 通过类对象的getConstructor()或getDeclaredConstructor()方法获得构造器（Constructor）对象并调用其newInstance()方法创建对象
Map map =
new HashMap();
for(int i = 0; i < 10; i++)
map.put(ghog.newInstance(i), new Prediction());
print("map = " + map);
Groundhog gh = ghog.newInstance(3);
print("Looking up prediction for " + gh);
if(map.containsKey(gh))
print(map.get(gh));
else
print("Key not found: " + gh);
}
public static void main(String[] args) throws Exception {
detectSpring(Groundhog.class);
}
} /* Output:
map = {Groundhog #3=Early Spring!, Groundhog #7=Early Spring!, Groundhog #5=Early Spring!, Groundhog #9=Six more weeks of Winter!, Groundhog #8=Six more weeks of Winter!, Groundhog #0=Six more weeks of Winter!, Groundhog #6=Early Spring!, Groundhog #4=Six more weeks of Winter!, Groundhog #1=Six more weeks of Winter!, Groundhog #2=Early Spring!}
Looking up prediction for Groundhog #3
Key not found: Groundhog #3
*///:~
从上面结果可以看到，在map中无法找到3这个key，那是因为这里Groundhog 没有实现hashCode()和equals()这两个方法，默认使用Object中的这两个方法进行比较，Object中的hashCode()是根据对象地址计算出来的。
重载实现两个方法即可：
public class Groundhog {
protected int number;
public Groundhog(int n) { number = n; }
public String toString() {
return "Groundhog #" + number;
}
@Override
public int hashCode()
{
return number;
}
@Override
public boolean equals(Object obj)
{
return obj instanceof Groundhog && (number==((Groundhog)obj).number);
} ///:~
ashMap使用equals()判断当前的键是否与表中存在的键相同。
正确的equals()方法必须满足下面5个条件：
- 自反性。对任意x，x.equals(x)一定返回true。
- 对称性。对任意x和y，如果y.equals(x)返回true，则x.equals(y)也返回true。
- 传递性。对任意x，y，z,如果有x.equals(y)返回true，y.equals(z)返回true，则x.equals(z)一定返回true。
- 一致性。对任意x和y，如果对象中用于等价比较信息没有改变，那么无论调用x.equals(y)多少次，返回结果保持一致。
- 对任何不是null的x，x.equals(null)一定返回false。
17.9.1 理解hashCode()
使用散列的目的在于：想要使用一个对象来查找另一个对象。
下面的示例用一对ArrayLists实现了一个Map：
import java.util.*;
import net.mindview.util.*;
public class SlowMap extends AbstractMap {//使用索引位置来关联表
private List keys = new ArrayList();
private List values = new ArrayList();
public V put(K key, V value) {
V oldValue = get(key); // The old value or null
if(!keys.contains(key)) {
keys.add(key);
values.add(value);
} else
values.set(keys.indexOf(key), value);
return oldValue;
}
public V get(Object key) { // key is type Object, 这里使用Object是因为泛型引入太晚导致
if(!keys.contains(key))
return null;
return values.get(keys.indexOf(key));
}
public Set> entrySet() {
Set> set= new HashSet>();
Iterator ki = keys.iterator();
Iterator vi = values.iterator();
while(ki.hasNext())
set.add(new MapEntry(ki.next(), vi.next()));
return set;
}
public static void main(String[] args) {
SlowMap m= new SlowMap();
m.putAll(Countries.capitals(15));
System.out.println(m);
System.out.println(m.get("BULGARIA"));
System.out.println(m.entrySet());
}
}
Map.Entry是一个接口，用来描述依赖于实现的结构，如果要创建自己的Map类型，就必须同时定义Map.Entry的实现：
import java.util.*;
public class MapEntry implements Map.Entry {
private K key;
private V value;
public MapEntry(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() { return key; }
public V getValue() { return value; }
public V setValue(V v) {
V result = value;
value = v;
return result;
}
public int hashCode() {
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
}
public boolean equals(Object o) {
if(!(o instanceof MapEntry)) return false;
MapEntry me = (MapEntry)o;
return
(key == null ?
me.getKey() == null : key.equals(me.getKey())) &&
(value == null ?
me.getValue()== null : value.equals(me.getValue()));
}
public String toString() { return key + "=" + value; }
}
17.9.2 为速度而散列
散列的价值在于速度：散列使得查询得以快速进行。
散列跟进一步，它将键保持在某处，以便能够很快找到。存储一组元素最快的数据结构就是数组，所以使用它来表示键的信息。
数组不能调整容量，但我们不希望键的数量被数组的容量限制。
解决办法：数组并不保存键本身。而是通过键对象生成一个数字，将其作为数组的下标，这个数字就是散列码。
为解决数组容量被固定的问题，不同的键可以产生相同的下标。也就是说，可能会有冲突。因此，数组多大就不重要了，任何键总能在数组中找到位置。
于是查询一个值得过程首先就是计算散列码，然后使用散列码查询数组。如果能够保证没有冲突，那就是一个完美散列函数了。但是这种情况只是特例。冲突有外部链接处理：数组并不直接保存值，而是保存值得list。然后对list中的值使用equals()方法进行线性查询。
public class SimpleHashMap extends AbstractMap {
// 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("unchecked")
LinkedList>[] 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>();
LinkedList> bucket = buckets[index];
MapEntry pair = new MapEntry(key, value);
boolean found = false;
ListIterator> it = bucket.listIterator();
while(it.hasNext()) {
MapEntry 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 iPair : buckets[index])
if(iPair.getKey().equals(key))
return iPair.getValue();
return null;
}
public Set> entrySet() {
Set> set= new HashSet>();
for(LinkedList> bucket : buckets) {
if(bucket == null) continue;
for(MapEntry mpair : bucket)
set.add(mpair);
}
return set;
}
public static void main(String[] args) {
SimpleHashMap m =
new SimpleHashMap();
m.putAll(Countries.capitals(25));
System.out.println(m);
System.out.println(m.get("ERITREA"));
System.out.println(m.entrySet());
}
}
17.9.3 覆盖hashCode()
设计hashCode()最重要的因素就是：无论何时，对同一个对象调用hashCode()都应该产生同样的值。
下面String为例。String有个特点：如果程序中有多个String对象，都包含相同的字符串序列，那么这些String对象都映射到同一块内存区域：
public class StringHashCode {
public static void main(String[] args) {
String[] hellos = "Hello Hello".split(" ");
System.out.println(hellos[0].hashCode());
System.out.println(hellos[1].hashCode());
}
} /* Output: (Sample)
69609650
69609650
*///:~
对于String而言，hashCode()明显是基于String的内容的。
hashCode()的散列码必须是基于内容生成，不必独一无二，但是通过hashCOde()和equals()必须能够完全确定对象。
怎样写出一份像样的hashCode基本指导：
- 给int变量result赋予某个非零值常量。例如17
- 为对象内每个有意义的域f计算一个int散列码c：
|域类型|计算|
|:--??:--??
|boolean|c=(f?0:1)|
|byte,char,short或int|c=(int)f|
|long|c=(int)(f^(f>>>32))|
|float|c=Float.float.ToIntBits(f)|
|double|long l=Doule.doubleToLongBits(f);c=(int)(l^(l>>>32))|
|object,其equals()调用这个域的equals()|c=f.hashCode()|
|数组|对每个元素应用上述规则| - 合并计算得到散列码：
result=37*result+c - 返回result
- 检查hashCode()最后生成结果，确保相同的对象有相同的散列码。
import java.util.*;
import static net.mindview.util.Print.*;
public class CountedString {
private static List created =
new ArrayList();
private String s;
private int id = 0;
public CountedString(String str) {
s = str;
created.add(s);
// id is the total number of instances
// of this string in use by CountedString:
for(String s2 : created)
if(s2.equals(s))
id++;
}
public String toString() {
return "String: " + s + " id: " + id +
" hashCode(): " + hashCode();
}
public int hashCode() {
// The very simple approach:
// return s.hashCode() * id;
// Using Joshua Bloch's recipe:
int result = 17;
result = 37 * result + s.hashCode();
result = 37 * result + id;
return result;
}
public boolean equals(Object o) {
return o instanceof CountedString &&
s.equals(((CountedString)o).s) &&
id == ((CountedString)o).id;
}
public static void main(String[] args) {
Map map =
new HashMap();
CountedString[] cs = new CountedString[5];
for(int i = 0; i < cs.length; i++) {
cs[i] = new CountedString("hi");
map.put(cs[i], i); // Autobox int -> Integer
}
print(map);
for(CountedString cstring : cs) {
print("Looking up " + cstring);
print(map.get(cstring));
}
}
} /* Output: (Sample)
{String: hi id: 4 hashCode(): 146450=3, String: hi id: 1 hashCode(): 146447=0, String: hi id: 3 hashCode(): 146449=2, String: hi id: 5 hashCode(): 146451=4, String: hi id: 2 hashCode(): 146448=1}
Looking up String: hi id: 1 hashCode(): 146447
0
Looking up String: hi id: 2 hashCode(): 146448
1
Looking up String: hi id: 3 hashCode(): 146449
2
Looking up String: hi id: 4 hashCode(): 146450
3
Looking up String: hi id: 5 hashCode(): 146451
4
*///:~
第二个实例Individual：
package pets;
public class Individual implements Comparable {
private static long counter = 0;
private final long id = counter++;
private String name;
public Individual(String name) { this.name = name; }
// 'name' is optional:
public Individual() {}
public String toString() {
return getClass().getSimpleName() +
(name == null ? "" : " " + name);
}
public long id() { return id; }
public boolean equals(Object o) {
return o instanceof Individual &&
id == ((Individual)o).id;
}
public int hashCode() {
int result = 17;
if(name != null)
result = 37 * result + name.hashCode();
result = 37 * result + (int)id;
return result;
}
public int compareTo(Individual arg) {
// Compare by class name first:
String first = getClass().getSimpleName();
String argFirst = arg.getClass().getSimpleName();
int firstCompare = first.compareTo(argFirst);
if(firstCompare != 0)
return firstCompare;
if(name != null && arg.name != null) {
int secondCompare = name.compareTo(arg.name);
if(secondCompare != 0)
return secondCompare;
}
return (arg.id < id ? -1 : (arg.id == id ? 0 : 1));
}
} ///:~
compareTO()方法有一个比较结构，因此它会产生一个排序序列，排序规则首先按照实际类型排序，然后如果有名字按名字排序，最后按创建顺序排序：
import pets.*;
import java.util.*;
public class IndividualTest {
public static void main(String[] args) {
Set pets = new TreeSet();
for(List<? extends Pet> lp :
MapOfList.petPeople.values())
for(Pet p : lp)
pets.add(p);
System.out.println(pets);
}
} /* Output:
[Cat Elsie May, Cat Pinkola, Cat Shackleton, Cat Stanford aka Stinky el Negro, Cymric Molly, Dog Margrett, Mutt Spot, Pug Louie aka Louis Snorkelstein Dupree, Rat Fizzy, Rat Freckly, Rat Fuzzy]
*///:~
17.10 选择接口的不同实现
尽管实际上只有4种容器：Map，List，Set，Queue，但是每种接口都有不止一个实现版本。
容器之间的区别通常归结为由什么在背后支持它们。也就是说，所使用的接口是由什么样的数据结构实现的。
ArrayList底层由数组支持，LinkedList由双向链表实现。
Set被实现为TreeSet（基于TreeMap，生成一个总是处于排序状态的Set），HashSet（查询速度最快）或LinkedHashSet（保持元素插入顺序）。
17.10.1 性能测试框架
下面的代码构建了一个基类，从中可以创建一个匿名内部类列表，其中每个匿名内部类都用于各种不同的测试，它们每个都被当作测试过程的一部分而被调用。
待测容器类型是泛型参数C。每个对象都存储了该测试的名字。
public abstract class Test {
String name;
public Test(String name) { this.name = name; }
// Override this method for different tests.
// Returns actual number of repetitions of test.
abstract int test(C container, TestParam tp);
} ///:~
第二个版本，接受相同类型的列表，但是它的值都在String中——通过这种方式，它可以用来解析命令行参数：
public class TestParam {
public final int size;
public final int loops;
public TestParam(int size, int loops) {
this.size = size;
this.loops = loops;
}
// Create an array of TestParam from a varargs sequence:
public static TestParam[] array(int... values) {
int size = values.length/2;
TestParam[] result = new TestParam[size];
int n = 0;
for(int i = 0; i < size; i++)
result[i] = new TestParam(values[n++], values[n++]);
return result;
}
// Convert a String array to a TestParam array:
public static TestParam[] array(String[] values) {
int[] vals = new int[values.length];
for(int i = 0; i < vals.length; i++)
vals[i] = Integer.decode(values[i]);
return array(vals);
}
} ///:~
import java.util.*;
public class Tester {
public static int fieldWidth = 8;//标准宽度
public static TestParam[] defaultParams= TestParam.array(
10, 5000, 100, 5000, 1000, 5000, 10000, 500);
// Override this to modify pre-test initialization:
protected C initialize(int size) { return container; }//可覆盖执行特殊的初始化
protected C container;
private String headline = "";
private List> tests;
private static String stringField() {//格式化字符串
return "%" + fieldWidth + "s";
}
private static String numberField() {
return "%" + fieldWidth + "d";
}
private static int sizeWidth = 5;
private static String sizeField = "%" + sizeWidth + "s";
private TestParam[] paramList = defaultParams;
public Tester(C container, List> tests) {
this.container = container;
this.tests = tests;
if(container != null)
headline = container.getClass().getSimpleName();
}
public Tester(C container, List> tests,
TestParam[] paramList) {
this(container, tests);
this.paramList = paramList;
}
public void setHeadline(String newHeadline) {
headline = newHeadline;
}
// Generic methods for convenience :
public static void run(C cntnr, List> tests){
new Tester(cntnr, tests).timedTest();
}
public static void run(C cntnr,
List> tests, TestParam[] paramList) {
new Tester(cntnr, tests, paramList).timedTest();
}
private void displayHeader() {//头信息
// Calculate width and pad with '-':
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();
}
// Run the tests for this container:
public void timedTest() {
displayHeader();
for(TestParam param : paramList) {
System.out.format(sizeField, param.size);
for(Test 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();
}
}
} ///:~
17.10.2 对List的选择
List操作中最本质部分的性能测试，它还展示了Queue中最重要的操作。在测试中，Queue操作只应用到LinkedList之上：
//: containers/ListPerformance.java
// Demonstrates performance differences in Lists.
// {Args: 100 500} Small to keep build testing short
import java.util.*;
import net.mindview.util.*;
public class ListPerformance {
static Random rand = new Random();
static int reps = 1000;
static List>> tests =
new ArrayList>>();
static List>> qTests =
new ArrayList>>();
static {
tests.add(new Test>("add") {
int test(List 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>("get") {
int test(List 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>("set") {
int test(List 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>("iteradd") {
int test(List list, TestParam tp) {
final int LOOPS = 1000000;
int half = list.size() / 2;
ListIterator it = list.listIterator(half);
for (int i = 0; i < LOOPS; i++)
it.add(47);
return LOOPS;
}
});
tests.add(new Test>("insert") {
int test(List 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>("remove") {
int test(List 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;
}
});
// Tests for queue behavior:
qTests.add(new Test>("addFirst") {
int test(LinkedList 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(47);
}
return loops * size;
}
});
qTests.add(new Test>("addLast") {
int test(LinkedList 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(47);
}
return loops * size;
}
});
qTests.add(
new Test>("rmFirst") {
int test(LinkedList 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() > 0)
list.removeFirst();
}
return loops * size;
}
});
qTests.add(new Test>("rmLast") {
int test(LinkedList 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() > 0)
list.removeLast();
}
return loops * size;
}
});
}
static class ListTester extends Tester> {
public ListTester(List container,
List>> tests) {
super(container, tests);
}
// Fill to the appropriate size before each test:
@Override
protected List initialize(int size) {
container.clear();
container.addAll(new CountingIntegerList(size));
return container;
}
// Convenience method:
public static void run(List list,
List>> tests) {
new ListTester(list, tests).timedTest();
}
}
public static void main(String[] args) {
if (args.length > 0)
Tester.defaultParams = TestParam.array(args);
// Can only do these two tests on an array:
Tester> arrayTest =
new Tester>(null, tests.subList(1, 3)) {
// This will be called before each test. It
// produces a non-resizeable array-backed list:
@Override
protected List initialize(int size) {
Integer[] ia = Generated.array(Integer.class,
new CountingGenerator.Integer(), 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(), tests);
ListTester.run(new LinkedList(), tests);
ListTester.run(new Vector(), tests);
Tester.fieldWidth = 12;
Tester> qTest =
new Tester>(
new LinkedList(), qTests);
qTest.setHeadline("Queue tests");
qTest.timedTest();
}
} /* Output: (Sample)
--- Array as List ---
size get set
10 130 183
100 130 164
1000 129 165
10000 129 165
--------------------- ArrayList ---------------------
size add get set iteradd insert remove
10 121 139 191 435 3952 446
100 72 141 191 247 3934 296
1000 98 141 194 839 2202 923
10000 122 144 190 6880 14042 7333
--------------------- LinkedList ---------------------
size add get set iteradd insert remove
10 182 164 198 658 366 262
100 106 202 230 457 108 201
1000 133 1289 1353 430 136 239
10000 172 13648 13187 435 255 239
----------------------- Vector -----------------------
size add get set iteradd insert remove
10 129 145 187 290 3635 253
100 72 144 190 263 3691 292
1000 99 145 193 846 2162 927
10000 108 145 186 6871 14730 7135
-------------------- Queue tests --------------------
size addFirst addLast rmFirst rmLast
10 199 163 251 253
100 98 92 180 179
1000 99 93 216 212
10000 111 109 262 384
*///:~
get和set测试都使用了随机数生成器来执行对List的随机访问。对于背后是数组支撑的List和ArrayList，无论列表大小如何，这些访问都快速一致。而对于LinkedList访问时间对于较大的列表明显增加，如果需要执行大量随机访问，链接链表不会是一种好的选择。
使用迭代器在列表中间插入新的元素。对于ArrayList，当列表变大时，其开销将变得高昂，但是对于LinkedList，相对来说比较低廉，并且不随列表尺寸而发生变化。这是因为ArrayList在插入时，必须创建空间并将它的所有引用向前移动，这会随ArrayList的尺寸增加而产生高昂的代价。LinkedList自需要链接新的元素，而不必修改列表中剩余的元素，一次你可以认为列表尺寸如果变化，其代价大致相同。
没有选择List两端的元素时因为LinkedList对List端点会进行特殊处理——这使得在将LinkedList用作Queue时，速度可以得到提高。
在LinkedList中的插入和移除代价相当低廉，并且不随列表尺寸发生变化，但是对于ArrayList，插入操作代价很高昂，并且不随列表尺寸的增加而增加。
从Queue测试中，可以看到LinkedList可以多么快速的从列表的端点插入和移除元素，这正是对Queue行为所做的优化。
将ArrayList作为默认首选，只有你需要使用额外的功能，或者当程序的性能因为经常从表中间进行插入和删除而变差的时候，才去选择LinkedList。
CopyOnWriteArrayList是List的一个特殊实现，专门用于并发编程。
17.10.4 对Set的选择
import java.util.*;
public class SetPerformance {
static List>> tests =
new ArrayList>>();
static {
tests.add(new Test>("add") {
int test(Set 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(j);
}
return loops * size;
}
});
tests.add(new Test>("contains") {
int test(Set 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(j);
return loops * span;
}
});
tests.add(new Test>("iterate") {
int test(Set set, TestParam tp) {
int loops = tp.loops * 10;
for(int i = 0; i < loops; i++) {
Iterator it = set.iterator();
while(it.hasNext())
it.next();
}
return loops * set.size();
}
});
}
public static void main(String[] args) {
if(args.length > 0)
Tester.defaultParams = TestParam.array(args);
Tester.fieldWidth = 10;
Tester.run(new TreeSet(), tests);
Tester.run(new HashSet(), tests);
Tester.run(new LinkedHashSet(), tests);
}
} /* Output: (Sample)
------------- TreeSet -------------
size add contains iterate
10 746 173 89
100 501 264 68
1000 714 410 69
10000 1975 552 69
------------- HashSet -------------
size add contains iterate
10 308 91 94
100 178 75 73
1000 216 110 72
10000 711 215 100
---------- LinkedHashSet ----------
size add contains iterate
10 350 65 83
100 270 74 55
1000 303 111 54
10000 1615 256 58
*///:~
HashSet的性能基本上总是比TreeSet的好，特别是在添加和查询元素时，而这两个操作是最重要的操作。TreeSet存在的唯一原因是它可以维持元素的排序状态。
对于插入操作，LinkedHashSet比HashSet的代价更高，这是由维护链表所带来额外开销造成的。
17.10.5 对Map的选择
//: containers/MapPerformance.java
// Demonstrates performance differences in Maps.
// {Args: 100 5000} Small to keep build testing short
import java.util.*;
public class MapPerformance {
static List>> tests =
new ArrayList>>();
static {
tests.add(new Test>("put") {
int test(Map 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>("get") {
int test(Map 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>("iterate") {
int test(Map map, TestParam tp) {
int loops = tp.loops * 10;
for(int i = 0; i < loops; i ++) {
Iterator it = map.entrySet().iterator();
while(it.hasNext())
it.next();
}
return loops * map.size();
}
});
}
public static void main(String[] args) {
if(args.length > 0)
Tester.defaultParams = TestParam.array(args);
Tester.run(new TreeMap(), tests);
Tester.run(new HashMap(), tests);
Tester.run(new LinkedHashMap(),tests);
Tester.run(
new IdentityHashMap(), tests);
Tester.run(new WeakHashMap(), tests);
Tester.run(new Hashtable(), tests);
}
} /* Output: (Sample)
---------- TreeMap ----------
size put get iterate
10 748 168 100
100 506 264 76
1000 771 450 78
10000 2962 561 83
---------- HashMap ----------
size put get iterate
10 281 76 93
100 179 70 73
1000 267 102 72
10000 1305 265 97
------- LinkedHashMap -------
size put get iterate
10 354 100 72
100 273 89 50
1000 385 222 56
10000 2787 341 56
------ IdentityHashMap ------
size put get iterate
10 290 144 101
100 204 287 132
1000 508 336 77
10000 767 266 56
-------- WeakHashMap --------
size put get iterate
10 484 146 151
100 292 126 117
1000 411 136 152
10000 2165 138 555
--------- Hashtable ---------
size put get iterate
10 264 113 113
100 181 105 76
1000 260 201 80
10000 1245 134 77
*///:~
所有的Map实现的插入操作都会随着Map尺寸的变大明显变慢。但是查找的代价比插入小很多。
Hashtable的性能大体和HashMap相当。因为HashMap是用来替代Hashtable的，因此它们使用了相同的底层存储和查找机制。
TreeMap是一种创建有序列表的方式。树的行为是：总是保证有序，并且不必进行特殊的排序。一旦你填充了一个TreeMap，就可以调用keySet()方法来获取键的Set视图，然后调用toArray()来产生这些键构成的数组。
可以使用静态方法Arrays.binarySearch()在排序数组中快速查找对象。
LingkedHashMap在插入时比HashMap慢一点，因为它维护散列数据结构的同时还要维护链表。就是因为这个列表，使得其迭代速度更快。
IdentityHashMap则具有完全不同的性能，因为它使用==而不是equals()来比较元素。
HashMap的性能因子
可以通过手工调整HashMap来提高性能，从而满足我们特定应用的需求：
容量：表中的桶位数。
初始容量：表在创建时所拥有的桶位数。
尺寸：表中当前存储的项数。
负载因子：尺寸/容量。负载轻的表产生的可能性小，因此对于插入和查找都是最理想的。
HashMap使用的默认负载因子时0.75，这个因子在时间和空间代价之间达到了平衡。
17.11 实用方法
Java中有大量用于容器得卓越的使用方法，它们表示为java.util.Collection类nebulous的静态方法。
import java.util.*;
import static net.mindview.util.Print.*;
public class Utilities {
static List list = Arrays.asList(
"one Two three Four five six one".split(" "));
public static void main(String[] args) {
print(list);
print("'list' disjoint (Four)?: " +
Collections.disjoint(list,
Collections.singletonList("Four")));//disjoint 两个集合中没有相同的元素返回true
print("max: " + Collections.max(list));
print("min: " + Collections.min(list));//max，min返回最小或最大的元素，用Comparator比较
print("max w/ comparator: " + Collections.max(list,
String.CASE_INSENSITIVE_ORDER));
print("min w/ comparator: " + Collections.min(list,
String.CASE_INSENSITIVE_ORDER));
List sublist =
Arrays.asList("Four five six".split(" "));
print("indexOfSubList: " +
Collections.indexOfSubList(list, sublist));//返回sublist再list中第一个出现的位置，找不到返回-1
print("lastIndexOfSubList: " +
Collections.lastIndexOfSubList(list, sublist));//返回sublist再list中最后一次出现的位置，找不到返回-1
Collections.replaceAll(list, "one", "Yo");//使用newVal替换所有的oldVal
print("replaceAll: " + list);
Collections.reverse(list);//逆转所有元素次序
print("reverse: " + list);
Collections.rotate(list, 3);//所有元素向后移动distance个位置，将最后元素循环到前面来
print("rotate: " + list);
List source =
Arrays.asList("in the matrix".split(" "));
Collections.copy(list, source);
print("copy: " + list);
Collections.swap(list, 0, list.size() - 1);//交换list中位置i与位置j的元素。
print("swap: " + list);
Collections.shuffle(list, new Random(47));//随机改变指定列表顺序
print("shuffled: " + list);
Collections.fill(list, "pop");
print("fill: " + list);
print("frequency of 'pop': " +
Collections.frequency(list, "pop"));
List dups = Collections.nCopies(3, "snap");//返回大小为n的List,次List不可改变
print("dups: " + dups);
print("'list' disjoint 'dups'?: " +
Collections.disjoint(list, dups));//当没有相同的元素时，返回true
// Getting an old-style Enumeration:
Enumeration e = Collections.enumeration(dups);//生成一个旧式的Enumeraton
Vector v = new Vector();
while(e.hasMoreElements())
v.addElement(e.nextElement());
// Converting an old-style Vector
// to a List via an Enumeration:
ArrayList arrayList =
Collections.list(v.elements());
print("arrayList: " + arrayList);
}
} /* Output:
[one, Two, three, Four, five, six, one]
'list' disjoint (Four)?: false
max: three
min: Four
max w/ comparator: Two
min w/ comparator: five
indexOfSubList: 3
lastIndexOfSubList: 3
replaceAll: [Yo, Two, three, Four, five, six, Yo]
reverse: [Yo, six, five, Four, three, Two, Yo]
rotate: [three, Two, Yo, Yo, six, five, Four]
copy: [in, the, matrix, Yo, six, five, Four]
swap: [Four, the, matrix, Yo, six, five, in]
shuffled: [six, matrix, the, Four, Yo, five, in]
fill: [pop, pop, pop, pop, pop, pop, pop]
frequency of 'pop': 7
dups: [snap, snap, snap]
'list' disjoint 'dups'?: true
arrayList: [snap, snap, snap]
*///:~
17.11.1 List的排序和查询
List排序和查询所使用的方法与对象数组所使用的相应方法有相同的名字与语法，只是用Collections的static方法代替Arrays的方法而已。
import java.util.*;
import static net.mindview.util.Print.*;
public class ListSortSearch {
public static void main(String[] args) {
List list =
new ArrayList(Utilities.list);
list.addAll(Utilities.list);
print(list);
Collections.shuffle(list, new Random(47));
print("Shuffled: " + list);
// Use a ListIterator to trim off the last elements:
ListIterator it = list.listIterator(10);
while(it.hasNext()) {
it.next();
it.remove();
}
print("Trimmed: " + list);
Collections.sort(list);
print("Sorted: " + list);
String key = list.get(7);
int index = Collections.binarySearch(list, key);
print("Location of " + key + " is " + index +
", list.get(" + index + ") = " + list.get(index));
Collections.sort(list, String.CASE_INSENSITIVE_ORDER);
print("Case-insensitive sorted: " + list);
key = list.get(7);
index = Collections.binarySearch(list, key,
String.CASE_INSENSITIVE_ORDER);
print("Location of " + key + " is " + index +
", list.get(" + index + ") = " + list.get(index));
}
}
17.11.2 设定Collection或Map为不可修改
生成各种只读容器：
import java.util.*;
import net.mindview.util.*;
import static net.mindview.util.Print.*;
public class ReadOnly {
static Collection data =
new ArrayList(Countries.names(6));
public static void main(String[] args) {
Collection c =
Collections.unmodifiableCollection(
new ArrayList(data));
print(c); // Reading is OK
//! c.add("one"); // Can't change it
List a = Collections.unmodifiableList(
new ArrayList(data));
ListIterator lit = a.listIterator();
print(lit.next()); // Reading is OK
//! lit.add("one"); // Can't change it
Set s = Collections.unmodifiableSet(
new HashSet(data));
print(s); // Reading is OK
//! s.add("one"); // Can't change it
// For a SortedSet:
Set ss = Collections.unmodifiableSortedSet(
new TreeSet(data));
Map m = Collections.unmodifiableMap(
new HashMap(Countries.capitals(6)));
print(m); // Reading is OK
//! m.put("Ralph", "Howdy!");
// For a SortedMap:
Map sm =
Collections.unmodifiableSortedMap(
new TreeMap(Countries.capitals(6)));
}
}
对特定类型的"不可修改的"方法的调用并不会产生编译时的检查，但是转换完成后，任何改变容器内容的操作都会引发UnsupportedOperationException异常。
17.11.3 Collection或Map的同步控制
import java.util.*;
public class Synchronization {
public static void main(String[] args) {
Collection c =
Collections.synchronizedCollection(
new ArrayList());
List list = Collections.synchronizedList(
new ArrayList());
Set s = Collections.synchronizedSet(
new HashSet());
Set ss = Collections.synchronizedSortedSet(
new TreeSet());
Map m = Collections.synchronizedMap(
new HashMap());
Map sm =
Collections.synchronizedSortedMap(
new TreeMap());
}
} ///:~
直接将新生成的容器传递给适当的同步方法。
快速报错
Java容器有一种保护机制，能够防止多个进程同时修改同一个容器的内容。
Java容器类类库采用快速报错机制，它会探查容器上的任何除了你进程所进行的操作以外的所有变化，一旦发现其他进程修改了容器，就会抛出ConcurrentModificationException异常。
import java.util.*;
public class FailFast {
public static void main(String[] args) {
Collection c = new ArrayList();
Iterator it = c.iterator();
c.add("An object");
try {
String s = it.next();
} catch(ConcurrentModificationException e) {
System.out.println(e);
}
}
} /* Output:
java.util.ConcurrentModificationException
*///:~