第十七章:容器深入研究
完整的容器分类法:这张图是把工作中常用到的实现类和相关接口使用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));
}
}