第十七章：容器深入研究
完整的容器分类法：这张图是把工作中常用到的实现类和相关接口使用UML类图辨识出来
Java SE5新添加了：
Queue接口及其实现PriorityQueue和各种风格的BlockingQueue
ConcurrentMap接口及其实现ConcurrentHashMap，它们也是用于多线程机制的
CopyOnWriteArrayList和CopyOnWriteArraySet，它们也是用于多线程机制的
EnumSet和EnumMap，为使用enum而设计的Set和Map的特殊实现
Collection的功能方法
Collection的功能方法
方法 描述
boolean add(T e); 确保容器持有具有泛型类型T的参数。如果没有则将此参数添加进容器，则返回false
boolean addAll(Collection<? extends T> c); 添加参数中的所有元素，只要添加了任意元素就返回true
void clear(); 移除容器中的所有元素
boolean contains(T e); 如果容易已持有具有泛型类型T此参数，则返回true
boolean containsAll(Collection<?> c); 如果容器持有参数中的所有元素，则返回true
boolean isEmpty(); 容器中没有元素时返回true
Iterator iterator(); 返回一个Iterator，可以用来遍历容器中的元素
boolean remove(Object o); 如果参数在容器中，则移除此元素的一个实例。如果做了移除动作，则返回true
boolean removeAll(Collection<?> c); 移除参数中的所有元素，只要有移除动作则返回true
boolean retainAll(Collection<?> c); 只保存参数中的元素（相当于"交集"的概念），只要Collection发生了改变就返回true
int size(); 返回容器中元素的数目
Object[] toArray(); 返回一个数组，该数组包含容器中的所有元素
T[] toArray(T[] a); 返回一个数组，该数组包含容器中的所有元素。返回结果的运行时类型与参数数组a的类型相同，而不是单纯的Object
注意：Collection的方法中不包括随机访问所选择元素的get()。因为Collection包含Set,而Set是自己维护内部顺序的（这使得随机访问变得没有意义）。因此，如果想检查Collection中的元素，那就必须使用迭代器。
UnsupportedOperationException：最常见的未获支持的操作，都来源于背后由固定尺寸的数据结构支持的容器。当你用Arrays.asList()将数组转为List时，就会得到这样的容器。因为Arrays.asList()生成的List是基于一个固定大小的数组，仅支持那些不会改变数组大小的操作。任何会引起对底层数据结构的尺寸进行修改的方法都会产生一个UnsupportedOperationException异常。而Collections.unmodifiableList()会产生一个不可修改的列表。
Set和存储顺序
集合对象 描述
Set(interface) 存入Set的每个元素都必须是唯一的，因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。Set和Collection有完全一样的接口。Set接口不保证维护元素的次序
HashSet 为了快速查找而设计的Set。存入HashSet的元素必须定义hashCode()
TreeSet 保证次序的Set，底层为树结构。使用它可以从Set中提取有序的序列。元素必须实现Comparable接口
LinkedHashSet 具有HashSet的查询速度，且内部使用链表维护元素的顺序（插入的次序），于是在使用迭代器遍历Set时，结果会按元素的插入次序显示。元素也必须定义hashCode()方法。
注意： 对于良好的编程风格而言，你在覆盖equals()方法时，需要总是同时覆盖hashCode()方法。
理解Map
Map也叫映射表（或者关联数组），其基本思想是它维护的是键-值（对）关联，因此你可以用键来查找值。
Map 描述
HashMap Map基于散列表的实现（它取代了Hashtable），插入和查询”键值对“的开销是固定的。可以通过构造器设置容量和负载因子，以调整容器的性能
LinkedHashMap 类似于HashMap，但是迭代遍历它时，取得”键值对“的顺序是其插入次序，或者是最近最少使用（LRU）的次序。只比HashMap慢一点，而在迭代访问时反而更快，因为它使用链表维护内部次序
TreeMap 基于红黑树的实现。查看”键“或”键值对“时，它们会被排序（次序由Comparable或Comprator决定）。TreeMap的特点在于，所得到的结果是经过排序的。TreeMap是唯一带有subMap()方法的Map，它可以返回一个子树。
WeakHashMap 弱键（weak key）映射，需要释放映射所指向的对象，这是为解决某类特殊问题而设计的。如果映射之外没有引用指向某个”键“，则此”键“可以被垃圾回收器回收
ConcurrentHashMap 一种线程安全的Map，它不涉及同步加锁。将在后面”并发“继续讨论
IdentityHashMap 使用 == 代替 equals()对”键“进行比较的散列映射。专为解决某类特殊问题而设计的。
注意：对Map中使用的键的要求与对Set的元素要求一样。
SortedMap
使用SortedMap（TreeMap是其现阶段的唯一实现），可以确保键处于排序状态，这使得它具有额外的功能，这些功能由SortedMap接口中的下列方法提供：
Comparator comparator(): 返回当前Map使用的Comparator；或者返回null，表示以自然方式排序
T firstKey()返回Map中的第一个键
T lastKey()返回Map中的最末一个键
SortedMap subMap(fromKey, toKey)生成此Map的子集，范围由formKey(包含)到toKey(不包含)的键确定
SortedMap headMap(toKey)生成此Map的子集，由键小于toKey的所有键值对组成。
SortedMap tailMap(fromKey)生成此Map的子集，由键大于或等于formKey的所有键值对组成。
在测试TreeMap的新增功能之前为了更好创建测试数据，自定义了CountingMapData这个类，它经过预初始化，并且都是唯一的Integer和String的Map，它可以具有任意尺寸。CountingMapData实现如下：
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;
}
public static class Entry implements Map.Entry<Integer, String> {
int index;
public Entry(int index) {
this.index = index;
}
@Override
public boolean equals(Object obj) {
return Integer.valueOf(index).equals(obj);
}
@Override
public int hashCode() {
return Integer.valueOf(index).hashCode();
}
@Override
public Integer getKey() {
return index;
}
@Override
public String getValue() {
return chars[index % chars.length] + index / chars.length;
}
@Override
public String setValue(String value) {
throw new UnsupportedOperationException();
}
}
@Override
public Set<Map.Entry<Integer, String>> entrySet() {
// LinkedHashSet维护了初始化顺序
Set<Map.Entry<Integer, String>> entries = new LinkedHashSet<>();
for (int i = 0; i < size; i++) {
entries.add(new Entry(i));
}
return entries;
}
public static void main(String[] args) {
System.out.println(new CountingMapData(100));
}
}