文章目录
1.完整的容器分类法2.填充容器复制同一个对象引用来填充容器一种Generator解决方案Map生成器使用Abstract类
3.Collection的功能方法4.可选操作5.List的功能方法6.Set和存储顺序类型从输出看出SortedSet
7.队列优先级队列双向队列
8.理解Map标准的Java类库中包含了Map的几种基本实现，包括：实现Map接口SortedMapLinkedHashMap
9.散列与散列码为速度而散列覆盖hashCode()
10.选择接口的不同实现例如List接口Set接口对List的选择对Set的选择对Map的选择
11.实用方法List的排序和查询设定Collection或Map为不可修改Collection或Map的同步控制
12.持有引用13.Java 1.0/1.1 的容器Vector和Enumeration
1.完整的容器分类法
2.填充容器
复制同一个对象引用来填充容器
(1) Collections.nCopies()(2) Collections.fill()
toString()：返回类名+散列码的无符号十六进制
一种Generator解决方案
(1) 所有的Collection子类型都有一个接收另一个Collection对象的构造器，用所接收的Collection对象中的元素来填充新的容器(2) 泛型便利方法（例如addAll()）可以减少在使用类时所必需的类型检查数量
Map生成器
(1) 例
package Chapter17
.Example
;
import java
.util
.*
;
import net
.mindview
.util
.*
;
import static net
.mindview
.util
.Print
.*
;
class Letters implements Generator<Pair
<Integer, String>>,
Iterable
<Integer> {
private int size
= 9;
private int number
= 1;
private char letter
= 'A';
public Pair
<Integer, String> next() {
return new Pair<Integer, String>(
number
++, "" + letter
++);
}
public Iterator
<Integer> iterator() {
return new Iterator<Integer>() {
public Integer
next() {
return number
++;
}
public boolean hasNext() {
return number
< size
;
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
}
package Chapter17
.Example
;
import net
.mindview
.util
.Generator
;
import java
.util
.Iterator
;
import java
.util
.LinkedHashMap
;
public class MapData<K, V> extends LinkedHashMap<K, V> {
public MapData(Generator
<Pair
<K, V>> gen
, int quantity
) {
for(int i
= 0; i
< quantity
; ++i
) {
Pair
<K, V> p
= (Pair
)gen
.next();
this.put(p
.key
, p
.value
);
}
}
public MapData(Generator
<K> genK
, Generator
<V> genV
, int quantity
) {
for(int i
= 0; i
< quantity
; ++i
) {
this.put(genK
.next(), genV
.next());
}
}
public MapData(Generator
<K> genK
, V value
, int quantity
) {
for(int i
= 0; i
< quantity
; ++i
) {
this.put(genK
.next(), value
);
}
}
public MapData(Iterable
<K> genK
, Generator
<V> genV
) {
Iterator var4
= genK
.iterator();
while(var4
.hasNext()) {
K key
= (K
) var4
.next();
this.put(key
, genV
.next());
}
}
public MapData(Iterable
<K> genK
, V value
) {
Iterator var4
= genK
.iterator();
while(var4
.hasNext()) {
K key
= (K
) var4
.next();
this.put(key
, value
);
}
}
public static <K, V> MapData
<K, V> map(Generator
<Pair
<K, V>> gen
, int quantity
) {
return new MapData(gen
, quantity
);
}
public static <K, V> MapData
<K, V> map(Generator
<K> genK
, Generator
<V> genV
, int quantity
) {
return new MapData(genK
, genV
, quantity
);
}
public static <K, V> MapData
<K, V> map(Generator
<K> genK
, V value
, int quantity
) {
return new MapData(genK
, value
, quantity
);
}
public static <K, V> MapData
<K, V> map(Iterable
<K> genK
, Generator
<V> genV
) {
return new MapData(genK
, genV
);
}
public static <K, V> MapData
<K, V> map(Iterable
<K> genK
, V value
) {
return new MapData(genK
, value
);
}
}
package Chapter17
.Example
;
import net
.mindview
.util
.CountingGenerator
;
import net
.mindview
.util
.RandomGenerator
;
import static net
.mindview
.util
.Print
.print
;
public class MapDataTest {
public static void main(String
[] args
) {
print(MapData
.map(new Letters(), 11));
print(MapData
.map(new CountingGenerator.Character(),
new RandomGenerator.String(3), 8));
print(MapData
.map(new CountingGenerator.Character(),
"Value", 6));
print(MapData
.map(new Letters(),
new RandomGenerator.String(3)));
print(MapData
.map(new Letters(), "Pop"));
}
}
package Chapter17
.Example
;
public class Pair<K, V> {
public final K key
;
public final V value
;
public Pair(K k
, V v
) {
key
= k
;
value
= v
;
}
}
(2) 创建一个Pair<V，K>类，再调用Generator.next()方法来组装Map(3) Map适配器可以使用各种不同的Generator、Iterator和常量值的组合来填充Map初始化对象(4) 通过产生一个Iterator还实现了Iterable。
使用Abstract类
(1) 例：
package Chapter17
.Test5
;
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 class Entry implements Map.Entry<Integer, String> {
int index
;
Entry(int index
) {
this.index
= index
;
}
public boolean equals(Object o
) {
return o
instanceof Entry && index
== ((Entry
) o
).index
;
}
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();
}
}
class EntrySet extends AbstractSet<Map
.Entry
<Integer, String>> {
public int size() {
return size
;
}
private class Iter implements Iterator<Map
.Entry
<Integer, String>> {
private Entry entry
= new Entry(-1);
public boolean hasNext() {
return entry
.index
< size
- 1;
}
public Map
.Entry
<Integer, String> next() {
entry
.index
++;
return entry
;
}
public void remove() {
throw new UnsupportedOperationException();
}
}
public Iterator
<Map
.Entry
<Integer, String>> iterator() {
return new Iter();
}
}
private Set
<Map
.Entry
<Integer, String>> entries
=
new EntrySet();
public Set
<Map
.Entry
<Integer, String>> entrySet() {
return entries
;
}
}
package Chapter17
.Test5
;
public class Test5 {
public static void main(String
[] args
) {
System
.out
.println(new CountingMapData(60));
}
}
(1) 产生容器的测试数据：创建定制的Collection和Map实现(2) 享元设计模式：在普通的解决方案需要过多的对象，或者产生普通对象太占用空间时使用享元(3) 为了创建只读的Map，可以继承AbstractMap并实现entrySet()。为了创建只读的Set，可以继承AbstractSet并实现iterator()和size()
3.Collection的功能方法
boolean add(T)：像容器添加内容添加失败返回falseboolean addAll(Collection<? extends E> c)：添加参数中所有元素，有任意元素添加成功则返回truevoid clear()：移除容器中所有元素boolean contains(T)：如果容器已经持有泛型类型T的参数，则返回trueboolean containsAll(Collection<?>)：如果容器中持有参数中所有元素返回trueboolean isEmpty()：容器中没有元素，返回trueIterator iterator()：返回一个Iterator，可用来遍历容器中的元素boolean remove(Object o)：如果元素再容器中，则移除一个元素实例。如果做了移除动作，则返回trueboolean removeAll(Collection<?> c)：一处参数中所有元素。如果有移除动作，则返回trueboolean retainAll(Collection<?> c)：只保存参数中元素。Collection发生改变返回trueint size()：返回容器中元素数目Object[] toArray()：返回一个数组，该数组包含容器中所有元素 T[] toArray(T[] a)：返回一个包含所有容器内元素的数组，但返回类型为T而不简单是Object
4.可选操作
执行各种不同的添加和移除的方法在Collection接口中都是可选操作。这意味着实现类并不需要为这些方法提供功能定义“可选操作”可以防止设计中出现接口爆炸的情况容器应该易学易用，未获得支持的操作时一种特例，可以延迟到需要时再实现如果一个操作未获得支持，那么实现接口会导致UnsupportedOperationException异常未获支持的操作
(1) 最常见的未获支持的操作，都是源于背后由固定尺寸的数据结构支持的容器(2) 任何会引起对底层数据结构的尺寸进行修改的方法都会产生一个UnsupportedOperationException异常，以表示对未获支持操作的调用（一个编程错误）(3) 未获支持的操作只有在运行时才能检测到，因此它们表示动态类型检查
5.List的功能方法
基本的List很容易使用：大多数时候只是调用add()添加对象，使用get()一次取出一个元素，以及调用iterator()获取用于该序列的Iterator
package Chapter17
.Example2
;
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
<String> it
;
private static ListIterator
<String> lit
;
public static void basicTest(List
<String> a
) {
a
.add(1, "x");
a
.add("x");
a
.addAll(Countries
.names(25));
a
.addAll(3, Countries
.names(25));
b
= a
.contains("1");
b
= a
.containsAll(Countries
.names(25));
s
= a
.get(1);
i
= a
.indexOf("1");
b
= a
.isEmpty();
it
= a
.iterator();
lit
= a
.listIterator();
lit
= a
.listIterator(3);
i
= a
.lastIndexOf("1");
a
.remove(1);
a
.remove("3");
a
.set(1, "y");
a
.retainAll(Countries
.names(25));
a
.removeAll(Countries
.names(25));
i
= a
.size();
a
.clear();
}
public static void iterMotion(List
<String> a
) {
ListIterator
<String> 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
<String> a
) {
ListIterator
<String> it
= a
.listIterator();
it
.add("47");
it
.next();
it
.remove();
it
.next();
it
.set("47");
}
public static void testVisual(List
<String> a
) {
print(a
);
List
<String> b
= Countries
.names(25);
print("b = " + b
);
a
.addAll(b
);
a
.addAll(b
);
print(a
);
ListIterator
<String> x
= a
.listIterator(a
.size() / 2);
x
.add("one");
print(a
);
print(x
.next());
x
.remove();
print(x
.next());
x
.set("47");
print(a
);
x
= a
.listIterator(a
.size());
while (x
.hasPrevious())
printnb(x
.previous() + " ");
print();
print("testVisual finished");
}
public static void testLinkedList() {
LinkedList
<String> ll
= new LinkedList<String>();
ll
.addAll(Countries
.names(25));
print(ll
);
ll
.addFirst("one");
ll
.addFirst("two");
print(ll
);
print(ll
.getFirst());
print(ll
.removeFirst());
print(ll
.removeFirst());
print(ll
.removeLast());
print(ll
);
}
public static void main(String
[] args
) {
basicTest(
new LinkedList<String>(Countries
.names(25)));
basicTest(
new ArrayList<String>(Countries
.names(25)));
iterMotion(
new LinkedList<String>(Countries
.names(25)));
iterMotion(
new ArrayList<String>(Countries
.names(25)));
iterManipulation(
new LinkedList<String>(Countries
.names(25)));
iterManipulation(
new ArrayList<String>(Countries
.names(25)));
testVisual(
new LinkedList<String>(Countries
.names(25)));
testLinkedList();
}
}
6.Set和存储顺序
不同的Set实现不仅具有不同的行为，而且对于可以在特定的Set中放置的元素的类型也有不同的要求
类型
(1) Set(interface)：存入Set的每个元素都必须是唯一的，因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。(2) HashSet：为快速查找而设计的Set。存入HashSet的元素必须定义hashCode()(3) TreeSet：保持次序的Set，底层为树结构。使用它可以从set中提取有序的序列。元素必须实现Comparable接口(4) LinkedHashSet：具有HashSet的查询速度，且内部使用链表维护元素的顺序。元素也必须实现hashCode()方法
从输出看出
(1) HashSet以某种神秘的顺序保存所有的元素(2) LinkedHashSet按照元素插入的顺序保存元素(3) 而TreeSet按照排序顺序维护元素（按照CompareTo()的实现方式）
SortedSet
(1) SortedSet中的元素可以保证处于排序状态(2) SortSet：按对象的比较函数对元素排列(3) Comparator comparator() 返回当前Set使用的Comparator；或者返回null，表示以自然方式排序(4) Object first() 返回容器中第一个元素(5) Object last()返回容器最后一个元素(6) SortedSet subSet(from,to)生成此Set子集，范围从from(包含)到 to(不包含)(7) SortSet headSet(to) 生成此Set子集，由 小于 to的元素组成(8) SortSet tailSet(to) 生成此Set子集，由 大于或等于 from的元素组成
7.队列
Queue在Java SE5中仅有的两个实现是LInkedList和PriorityQueue(优先队列，不保证输出顺序)，他们的差异在于排序行为而不是性能
优先级队列
(1)
package Chapter17
.Example3
;
import java
.util
.*
;
class ToDoList extends PriorityQueue<ToDoList.ToDoItem> {
static class ToDoItem implements Comparable<ToDoItem> {
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());
}
}
(2) 优先队列通过实现Comparable进行控制
双向队列
(1)
package Chapter17
.Example4
;
import java
.util
.LinkedList
;
public class Deque<T> {
private LinkedList
<T> 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();
}
}
package Chapter17
.Example4
;
import static net
.mindview
.util
.Print
.*
;
public class DequeTest {
static void fillTest(Deque
<Integer> 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
<Integer> di
= new Deque<Integer>();
fillTest(di
);
print(di
);
while (di
.size() != 0)
printnb(di
.removeFirst() + " ");
print();
fillTest(di
);
while (di
.size() != 0)
printnb(di
.removeLast() + " ");
}
}
(2) 双向队列可以在任何一端添加或移除元素(3) 可以使用组合来创建一个Deque类，并直接从LinkedList中暴露相关的方法
8.理解Map
标准的Java类库中包含了Map的几种基本实现，包括：
(1) HashMap(2) TreeMap(3) LinkedHashMap(4) WeakHashMap(5) ConcurrentHashMap(6) IdentityHashMap
它们都有同样的基本接口Map，但是行为特性各不相同，这表现在效率、键值对的保存及呈现次序、对象的保存周期、映射表如何在多线程程序中工作和判定“键”等价的策略等方面
实现Map接口
(1) HashMap
Map基于散列表的实现（取代了Hashtable）。插入和查询键值对的开销是固定的。可以i通过构造器设置容量和负载因子，以调整容器的性能 (2) LinkedHashMap
类似于HashMap，但是迭代遍历它时，取得“键值对”的顺序是其插入次序，或者是最近最少使用(LRU)次序。只比HashMap慢一点。而在迭代访问时反而更快，因为它使用链表维护内部次序 (3) TreeMap
基于红黑树实现。查看“键”或“键值对”时，他们会被排序（次序由Comparable或Comparator决定）TreeMap的特点在于，所得到的结果是经过排序的。TreeMap是唯一带有subMap()方法的Map，他返回一个子树 (4) WeakHashMap
弱键 映射，允许释放映射所指向的对象；这是为解决某类特殊问题而设计的。如果映射之外没有引用指向某个“键”，则此“键”可以被垃圾收集器回收 (5) ConcurrentHashMap
一种线程安全的Map，它不涉及同步枷锁。 (6) IdentityHashMap
使用==代替equals()对“键”进行比较的散列映射
散列是映射中存储元素时最常用的方式
键必须是唯一的，而值可以有重复
SortedMap
(1) 使用SortedMap（TreeMap是其现阶段的唯一实现），可以确保键处于排序状态(2) Comparator comparator()：返回当前Map使用的Comparator;或者返回null，以表示自然排序(3) T firstKey()：返回Map中的第一个键(4) T lastKey()：返回Map中的最后一个键(5) SortMap subMap(fromKet,toKey)：生成此Map的子集，范围从fromKey（包含）到toKey（不包含）的键确定(6) SortMap headMap(toKey)：生成此Map的子集，由键 小于toKey的所有键值对组成(7) SortMap tailMap(fromKey)：生成此Map的子集，由键 大于或等于 fromeKey的所有键值对组成
LinkedHashMap
(1) 为了提高速度，LinkedHashMap散列化所有的元素，但是在遍历键值对时，却又以元素的插入顺序返回键值对(2) 可以在构造器中设定LinkedHashMap，使之采用基于访问最近最少使用算法，于是没有被访问过的元素就会出现在队列的前面(3)
package Chapter17
.Example5
;
import java
.util
.*
;
import net
.mindview
.util
.*
;
import static net
.mindview
.util
.Print
.*
;
public class LinkedHashMapDemo {
public static void main(String
[] args
) {
LinkedHashMap
<Integer, String> linkedMap
=
new LinkedHashMap<Integer, String>(
new CountingMapData(9));
print(linkedMap
);
linkedMap
=
new LinkedHashMap<Integer, String>(16, 0.75f, true);
linkedMap
.putAll(new CountingMapData(9));
print(linkedMap
);
for (int i
= 0; i
< 6; i
++)
linkedMap
.get(i
);
print(linkedMap
);
linkedMap
.get(0);
print(linkedMap
);
}
}
9.散列与散列码
hashMap使用equals()判断当前的键是否与表中存在的键相同
2 ###### 正确的equals()方法必须满足下面5个条件：
(1) 自反性。对任意x，x.equals(x)一定返回true。(2) 对称性。对任意x和y，如果y.equals(x)返回true，则x.equals(y)也返回true。(3) 传递性。对任意x，y，z,如果有x.equals(y)返回true，y.equals(z)返回true，则x.equals(z)一定返回true。(4) 一致性。对任意x和y，如果对象中用于等价比较信息没有改变，那么无论调用x.equals(y)多少次，返回结果保持一致。(5) 对任何不是null的x，x.equals(null)一定返回false。
如果要使用自己的类作为HashMap的键，必须同时重载hashCode()和equals()理解hashCode()
使用散列的目的在于：想要使用一个对象来查找另一个对象
为速度而散列
(1)
package Chapter17
.Example6
;
import Chapter17
.Test15
.MapEntry
;
import net
.mindview
.util
.Countries
;
import java
.util
.*
;
public class SimpleHashMap<K,V> extends AbstractMap<K,V> {
static final int SIZE
= 997;
@SuppressWarnings("unchecked")
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
)
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
<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());
}
}
(2) 散列的价值在于速度：散列使得查询得以快速进行(3) 数组并不保存键本身。而是通过键对象生成一个数字，将其作为数组的下标。这个数字就是散列码，由定义在Object中的、且可能由你的类覆盖的hashCode()方法生成(4) HashMap快的原因：不是查询整个list，而是快速地跳到数组的某个位置，只对很少的元素进行比较(5) 由于散列表中的“槽位”（slot）通常称为桶位（bucket），因此我们将表示实际散列表的数组命名为bucket。为使散列分布均匀，同的数量通常使用质数(6) 为了能够自动处理冲突，使用一个LinkedList的数组；每一个新的元素只是直接添加到list末尾的某个特定桶中
覆盖hashCode()
(1) 你无法控制bucket数组的下标值的产生。这个值依赖于具体的HashMap对象的容量，而容量的改变与容器的充满程度和负载因子有关
(2) 设计hashCode()是最重要的因素是：无论何时，对同一个对象调用hasCode()都应该生成个同样的值
(3) 如果你的hashCode()方法依赖于对象中易变的数据，因此数据发生变化时，hashCode()就会生成一个不同的散列码，相当于产生了一个不同的键
(4) 不应该使hashCode()依赖于具有唯一型的对象信息，尤其是使用this值，这只能产生很糟糕的hashCode()，应为这样无法生成一个新的键，使之与put()中源氏键值相同
(5) String有个特点：如果程序中有多个String对象，都包含相同的字符串序列，那么这些String对象都映射到同一块内存区域
(6) 怎样写出一份像样的hashCode基本指导
i.
package Chapter17
.Example7
;
import java
.util
.*
;
import static net
.mindview
.util
.Print
.*
;
public class CountedString {
private static List
<String> created
=
new ArrayList<String>();
private String s
;
private int id
= 0;
public CountedString(String str
) {
s
= str
;
created
.add(s
);
for(String s2
: created
)
if(s2
.equals(s
))
id
++;
}
public String
toString() {
return "String: " + s
+ " id: " + id
+
" hashCode(): " + hashCode();
}
public int hashCode() {
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
<CountedString,Integer> map
=
new HashMap<CountedString,Integer>();
CountedString
[] cs
= new CountedString[5];
for(int i
= 0; i
< cs
.length
; i
++) {
cs
[i
] = new CountedString("hi");
map
.put(cs
[i
], i
);
}
print(map
);
for(CountedString cstring
: cs
) {
print("Looking up " + cstring
);
print(map
.get(cstring
));
}
}
}
ii.给int变量result赋予某个非零值常量。例如17
iii.为对象内每个有意义的域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() 数组
对每个元素应用上述规则
iv.返回result
v.检查hashCode()最后生成结果，确保相同的对象有相同的散列码。
(7) compareTo()方法有一个比较结构，因此它会产生一个排序序列，排序规则首先按照实际类型排序，然后如果有名字按名字排序，最后按创建顺序排序：
package Chapter17
.Example7
;
import typeinfo
.pets
.Individual
;
import typeinfo
.pets
.Pet
;
import java
.util
.*
;
public class IndividualTest {
public static void main(String
[] args
) {
Set
<Individual> pets
= new TreeSet<Individual>();
for(List
<? extends Pet> lp
:
MapOfList
.petPeople
.values())
for(Pet p
: lp
)
pets
.add(p
);
System
.out
.println(pets
);
}
}
10.选择接口的不同实现
尽管实际上只有4种容器：Map，List，Set，Queue，但是每种接口都有不止一个实现版本
容器之间的区别：所使用的接口是由什么样的数据结构实现的
例如List接口
(1) ArrayList（底层由数组支持）(2) LinkedList（底层由双向链表实现）
Set接口
(1) HashSet（查询速度最快）(2) LinkedHashSet（保持元素插入顺序）(3) TreeSet（基于TreeMap，生成一个总是处于排序状态的Set）
性能测试框架
package Chapter17
.Example8
;
public abstract class Test<C> {
String name
;
public Test(String name
) { this.name
= name
; }
abstract int test(C container
, TestParam tp
);
}
package Chapter17
.Example8
;
import java
.util
.*
;
public class Tester<C> {
public static int fieldWidth
= 8;
public static TestParam
[] defaultParams
= TestParam
.array(
10, 5000, 100, 5000, 1000, 5000, 10000, 500);
protected C
initialize(int size
) { return container
; }
protected C container
;
private String headline
= "";
private List
<Test
<C>> 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
<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 void setHeadline(String newHeadline
) {
headline
= newHeadline
;
}
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();
}
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
);
System
.out
.format(sizeField
, "size");
for(Test test
: tests
)
System
.out
.format(stringField(), test
.name
);
System
.out
.println();
}
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();
int reps
= test
.test(kontainer
, param
);
long duration
= System
.nanoTime() - start
;
long timePerRep
= duration
/ reps
;
System
.out
.format(numberField(), timePerRep
);
}
System
.out
.println();
}
}
}
package Chapter17
.Example8
;
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 n
= 0;
for(int i
= 0; i
< size
; i
++)
result
[i
] = new TestParam(values
[n
++], values
[n
++]);
return result
;
}
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
);
}
}
对List的选择
package Chapter17
.Example9
;
import java
.util
.*
;
import net
.mindview
.util
.*
;
public class ListPerformance {
static Random rand
= new Random();
static int reps
= 1000;
static List
<Test
<List
<Integer>>> tests
=
new ArrayList<Test
<List
<Integer>>>();
static List
<Test
<LinkedList
<Integer>>> qTests
=
new ArrayList<Test
<LinkedList
<Integer>>>();
static {
tests
.add(new Test<List
<Integer>>("add") {
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>>("get") {
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") {
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>>("iteradd") {
int test(List
<Integer> list
, TestParam tp
) {
final int LOOPS
= 1000000;
int half
= list
.size() / 2;
ListIterator
<Integer> it
= list
.listIterator(half
);
for(int i
= 0; i
< LOOPS
; i
++)
it
.add(47);
return LOOPS
;
}
});
tests
.add(new Test<List
<Integer>>("insert") {
int test(List
<Integer> list
, TestParam tp
) {
int loops
= tp
.loops
;
for(int i
= 0; i
< loops
; i
++)
list
.add(5, 47);
return loops
;
}
});
tests
.add(new Test<List
<Integer>>("remove") {
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);
}
return loops
* size
;
}
});
qTests
.add(new Test<LinkedList
<Integer>>("addFirst") {
int test(LinkedList
<Integer> 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<LinkedList
<Integer>>("addLast") {
int test(LinkedList
<Integer> 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<LinkedList
<Integer>>("rmFirst") {
int test(LinkedList
<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() > 0)
list
.removeFirst();
}
return loops
* size
;
}
});
qTests
.add(new Test<LinkedList
<Integer>>("rmLast") {
int test(LinkedList
<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() > 0)
list
.removeLast();
}
return loops
* size
;
}
});
}
static class ListTester extends Tester<List
<Integer>> {
public ListTester(List
<Integer> container
,
List
<Test
<List
<Integer>>> tests
) {
super(container
, tests
);
}
@Override protected List
<Integer> initialize(int size
){
container
.clear();
container
.addAll(new CountingIntegerList(size
));
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
<List
<Integer>> arrayTest
=
new Tester<List
<Integer>>(null
, tests
.subList(1, 3)){
@Override protected
List
<Integer> 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<Integer>(), tests
);
ListTester
.run(new LinkedList<Integer>(), tests
);
ListTester
.run(new Vector<Integer>(), tests
);
Tester
.fieldWidth
= 12;
Tester
<LinkedList
<Integer>> qTest
=
new Tester<LinkedList
<Integer>>(
new LinkedList<Integer>(), qTests
);
qTest
.setHeadline("Queue tests");
qTest
.timedTest();
}
}
注：由于篇幅问题，代码中的Test、Tester、TestParam类见：Chapter17\Example9
(1) 对于背后是数组支撑的List和ArrayList，无论列表大小如何，这些访问都快速一致。而对于LinkedList访问时间对于较大的列表明显增加，如果需要执行大量随机访问，链接链表不会是一种好的选择(2) 使用迭代器在列表中间插入新的元素。对于ArrayList，当列表变大时，其开销将变得高昂，但是对于LinkedList，相对来说比较低廉，并且不随列表尺寸而发生变化。这是因为ArrayList在插入时，必须创建空间并将它的所有引用向前移动，这会随ArrayList的尺寸增加而产生高昂的代价。LinkedList自需要链接新的元素，而不必修改列表中剩余的元素，一次你可以认为列表尺寸如果变化，其代价大致相同(3) LinkedList对List端点会进行特殊处理——这使得在将LinkedList用作Queue时，速度可以得到提高(4) 在LinkedList中的插入和移除代价相当低廉，并且不随列表尺寸发生变化，但是对于ArrayList，插入操作代价很高昂，并且不随列表尺寸的增加而增加(5) 从Queue测试中，可以看到LinkedList可以多么快速的从列表的端点插入和移除元素，这正是对Queue行为所做的优化(6) 将ArrayList作为默认首选，只有你需要使用额外的功能，或者当程序的性能因为经常从表中间进行插入和删除而变差的时候，才去选择LinkedList。如果使用的是固定数量的元素，那么既可以使用背后有支撑的List，也可以选择真正的数组(7) CopyOnWriteArrayList是List的一个特殊实现，专门用于并发编程
微基准测试的危险
Math.random()的输出中的，其范围是[0,1)
对Set的选择
(1) HashSet的性能基本上总是比TreeSet的好，特别是在添加和查询元素时，而这两个操作是最重要的操作。TreeSet存在的唯一原因是它可以维持元素的排序状态(2) 对于插入操作，LinkedHashSet比HashSet的代价更高，这是由维护链表所带来额外开销造成的
对Map的选择
(1) 所有的Map实现的插入操作都会随着Map尺寸的变大明显变慢。但是查找的代价比插入小很多。(2) Hashtable的性能大体和HashMap相当。因为HashMap是用来替代Hashtable的，因此它们使用了相同的底层存储和查找机制(3) TreeMap
i.TreeMap是一种创建有序列表的方式。树的行为是：总是保证有序，并且不必进行特殊的排序。一旦你填充了一个TreeMap，就可以调用keySet()方法来获取键的Set视图，然后调用toArray()来产生这些键构成的数组。ii.可以使用静态方法Arrays.binarySearch()在排序数组中快速查找对象iii.只有你要求Map始终保持有序时，才需要使用TreeMap (4) LingkedHashMap在插入时比HashMap慢一点，因为它维护散列数据结构的同时还要维护链表。就是因为这个列表，使得其迭代速度更快(5) IdentityHashMap则具有完全不同的性能，因为它使用==而不是equals()来比较元素(6) HashMap的性能因子，可以通过手工调整HashMap来提高性能，从而满足我们特定应用的需求：
i.容量：表中的桶位数ii.初始容量：表在创建时所拥有的桶位数iii.尺寸：表中当前存储的项数iv.负载因子：尺寸/容量。负载轻的表产生的可能性小，因此对于插入和查找都是最理想的 (7) HashMap使用的默认负载因子时0.75，这个因子在时间和空间代价之间达到了平衡。更高的负载因子可以降低表所需空间，但是会增加查找代价
11.实用方法
List的排序和查询
(1) List排序和查询所使用的方法与对象数组所使用的相应方法有相同的名字与语法，只是用Collections的static方法代替Arrays的方法而已(2) 如果使用Comparator进行排序，那么binarySearch()必须使用相同的Comparator
设定Collection或Map为不可修改
(1) Collections.unmodifiableCollection()用于创建“不可修改”的容器（返回值是容器的只读版本），任何修改容器内的操作（例如add()、put()）都会引起UnsupportedOperationException异常(2) 在将容器设为只读之前，必须填入有意义的数据。装在数据后就不可修改了
Collection或Map的同步控制
(1) 直接将新生成的容器传递给适当的同步方法
Collections.synchronizedCollection( new ArrayList());Collections.synchronizedList( new ArrayList());Collections.synchronizedSet( new HashSet());Collections.synchronizedSortedSet( new TreeSet());Collections.synchronizedMap( new HashMap<String,String>())Collections.synchronizedSortedMap( new TreeMap<String,String>()) (2) 快速报错
Java容器有一种保护机制，能够防止多个进程同时修改同一个容器的内容Java容器类类库采用快速报错机制，它会探查容器上的任何除了你进程所进行的操作以外的所有变化，一旦发现其他进程修改了容器，就会抛出ConcurrentModificationException异常ConcurrentHashMap、CopyOnWriteArrayList和CopyOnWriteArrayList都使用了可以避免ConcurrentModificationException异常
12.持有引用
java.lang.ref类库包含了一组类，这些类为垃圾回收提供了更大的灵活性有三个继承自抽象类Reference的类：SoftReference、WeakReference和PhantomReference。当垃圾回收器正在考察的对象只能通过某个Reference对象才“可获得”时，上述这些不同的派生类为垃圾回收器提供了不同级别的间接性指示使用Renference对象，可以继续使用该对象，而在内存消耗殆尽的时候由允许释放该对象Soft reference：用以实现内存敏感的高速缓存Weak reference：是为实现“规范映射”而设计的，它不妨碍垃圾回收映射的“键”（或“值”）Phantom reference：用以调用回收前的清理工作，它比Java终止机制更灵活WeakHashMap：容器类中有一种特殊的Map，即WeakHashMap，它被用来保存WeakReference
13.Java 1.0/1.1 的容器
Vector和Enumeration
Vector是唯一可以自我扩展的序列Enumeration只是接口而不是实现boolean hasMoreElement():如果此枚举包含更多元素，该方法就返回trueObject nextElement():该方法返回此枚举中的下一个元素（如果该有下一个元素），否则抛出异常Collection.emumeration()：从Collection生成一个Enumeration
Hashtable
在新程序中，应使用HashMap
Stack
Stack继承了Vector。它拥有Vector所有的特点和行为，在加上一些额外的Stack行为
BitSet
如果想要高效率地存储大量“开/关”信息，BitSet是很好的选择。不过它的效率仅是对空间而言；如果需要高效的访问时间，BitSet比本地数组稍微慢一点
