第13章 集合
13.1 集合接口
Java最初版本只为最常用的数据结构提供了很少的一组类: Vector、 Stack、 Hashtable、Bitset与 Enumeration接口,其中的 Enumeration接口提供了一种用于访问任意容器中各个元素的抽象机制。这是一种很明智的选择,但要想建立一个全面的集合类库还需要大量的时间和高超的技能。
13.1.1 将集合的接口于实现分离
与现代的数据结构类库的常见情况一样,Java集合类库也将接口( interface)与实现( implementation)分离。
13.1.2 Java类库中的集合接口和迭代器接口
在Java类库中，集合类的基本接口是Collection接口。这个接口有两个基本方法：
public
interface
Collection<E>{
boolean
add(E
element);
Iterator<E>
iterator();
...
}
1.迭代器
Iterator接口包含3个方法：
public
interface
Iterator<E>{
E
next();
boolean
hasNext();
void
remove();
}
"for each"循环而已与任何实现了Iterable接口的对象一起工作，换个接口只包含一个方法：
public
interface
Iterable<E>{
Iterator<E>
iterator();
}
Collection接口扩展了Iterable接口。
元素被访问的顺序取决于集合类型。如果对 Arraylist进行迭代,迭代器将丛索引0始,每迭代一次,索引值加1。然而、如果访回 Hashset中的亓素,每个元素将会按照某种随机的次序出现。虽然可以确定在迭代过程中能够遍历到集合中的所有元素,但却无法预知元素被访问的次序。这对于计算总和或统计符合某个条件的元素个数这类与顺序无关的操作来说,并不是什么问题。
2.删除元素
Iterator接口的 remove方法将会删除上次调用next方法时返回的元素。
3.泛型使用方法
由于 Collection与 Iterator都是泛型接口,可以编写操作任何集合类型的实用方法。
13.2具体集合
集合类型 | 描述 |
ArrayList | 一种可以动态增长和缩减的索引序列 |
LinkedList | 一种可以在任何位置进行高效地插入和删除操作的有序序列 |
ArrayDeque | 一种使用循环数组实现的双端队列 |
HashSet | 一种没有重复元素的无序集合 |
TreeSet | 一种有序集合 |
EnumSet | 一种包含枚举类型的集合 |
LinkedHashSet | 一种可以记住元素插入次序的集 |
PriorityQueue | 一种允许高效删除最小元素的集合 |
HashMap | 一种存储键/值关联的数据结构 |
TreeMap | 一种键值有序排列的映射表 |
EnumMap | 一种键值属于枚举类型的映射表 |
LinkedHashMap | 一种可以记住键/值项添加次序的映射表 |
WeakHashMap | 一种其值无用武之地后可以被垃圾回收器回收的映射表 |
IdentityHashMap | 一种用==而不是用equals比较键值的映射表 |
13.2.1 链表
LinkedList
链表是一个有序集合( orderedcollection),每个对象的位置十分重要。 LinkedList. add方法将对象添加到链表的尾部。但是,常常需要将元素添加到链表的中间。由于迭代器是描述集合中位置的,所以这种依赖于位置的add方法将由迭代器负责。只有对自然有序的集合使用迭代器添加元素才有实际意义。例如,下一节将要讨论的集(set)类型,其中的元素完全无序。因此,在 Iterator接口中就没有add方法。相反地,集合类库提供了子接口 Listiterator其中包含add方法。
可以想象,如果在某个迭代器修改集合时,另一个迭代器对其进行遍历,一定会出现混乱的状况。例如,一个迭代器指向另一个迭代器刚刚删除的元素前面,现在这个迭代器就是无效的,并且不应该再使用。链表迭代器的设计使它能够检测到这种修改。如果迭代器发现它的集合被另一个迭代器修改了,或是被该集合自身的方法修改了,就会抛出一个Concurrent Modification Exception异常。
为了避免发生并发修改的异常,请遵循下述简单规则:可以根据需要给容器附加许多的迭代器,但是这些迭代器只能读取列表。另外,再单独附加一个既能读又能写的迭代器。
在Java类库中,还提供了许多在理论上存在一定争议的方法。链表不支持快速地随机访问。如果要查看链表中第n个元素,就必须从头开始,越过n-1个元素。没有捷径可走。鉴于这个原因,在程序需要采用整数索引访问元素时,程序员通常不选用链表。
13.2.2 数组列表
ArrayList
在上一节中,介绍了List接口和实现了这个接口的 Linkedlist类。List接口用于描述个有序集合,并且集合中每个元素的位置十分重要。有两种访问元素的协议:一种是用迭代器,另一种是用get和set方法随机地访问每个元素。后者不适用于链表,但对数组却很有用。集合类库提供了一种大家熟悉的 Arraylist类,这个类也实现了List接口。 Array List封装了一个动态再分配的对象数组。
13.2.3 散列集
HashSet
链表和数组可以按照人们的意愿排列元素的次序。但是,如果想要查看某个指定的元素,却又忘记了它的位置,就需要访问所有元素,直到找到为止。如果集合中包含的元素很多,将会消耗很多时间。如果不在意元素的顺序,可以有几种能够快速查找元素的数据结构。其缺点是无法控制元素出现的次序。它们将按照有利于其操作目的的原则组织数据。
13.2.4 树集
TreeSet类与散列集十分类似,不过,它比散列集有所改进。树集是一个有序集合( sorted collection)。可以以任意顺序将元素插入到集合中。在对集合进行遍历时,每个值将自动地按照排序后的顺序呈现。
将一个元素添加到树中要比添加到散列表中慢,但是,与将元素添加到数组或链表的正确位置上相比还是快很多的。
13.2.5 对象的比较
Tree Set如何知道希望元素怎样排列呢?在默认情况时,树集假定插入的元素实现了Comparable接口。这个接口定义了一个方法:
public
interface
Comparable<T>{
int
compareTo(T
other);
}
如果a与b相等,调用 a. compare To(b)一定返回0;如果排序后a位于b之前,则返回负值;如果a位于b之后,则返回正值。具体返回什么值并不重要,关键是符号(>0、0或<0)。有些标准的Java平台类实现了 Comparable接口,例如, String类。这个类的compare To方法依据字典序(有日时称为词典序)对字符串进行比较。
在这种情况下,可以通过将 Comparator对象传递给 Treeset构造器来告诉树集使用不同的比较方法。 Comparator接口声明了一个带有两个显式参数的 compare方法:
public
interface
Comparator<T>{
int
compare(T
a,T
b);
}
与 compareto方法一样,如果a位于b之前 compare方法则返回负值;如果a和b相等则返回0,否则返回正值。
13.2.6 队列与双端队列
Queue Deque ArrayDeque
前面已经讨论过,队列可以让人们有效地在尾部添加一个元素,在头部删除一个元素。有两个端头的队列,即双端队列,可以让人们有效地在头部和尾部同时添加或删除元素。不支持在队列中间添加元素。在 Java SE6中引人了 Deque接口,并由 Array Deque和Linkedlist类实现。这两个类都提供了双端队列,而且在必要时可以增加队列的长度。在第14章将会看到有限队列和有限双端队列。
13.2.7 优先级队列
优先级队列( priority queue)中的元素可以按照任意的顺序插入,却总是按照排序的顺序进行检索。也就是说,无论何时调用 remove方法,总会获得当前优先级队列中最小的元素。然而,优先级队列并没有对所有的元素进行排序。如果用迭代的方式处理这些元素,并不需要对它们进行排序。优先级队列使用了一个优雅且高效的数据结构,称为堆(heap)。堆是一个可以自我调整的二叉树,对树执行添加(add)和删除( remore)操作,可以让最小的元素移动到根,而不必花费时间对元素进行排序。
13.2.8 映射表
集是一个集合,它可以快速地查找现有的元素。但是,要查看一个元素,需要有要查找元素的精确副本。这不是一种非常通用的查搜方式通常,我们知道某些键的信息,并想要查找与之对应的元素。映射表(map.数据结构就是为此设计十的。映射表用来存放键/值对。
Java类库为映射表提供了两个通用的实现: Hashmap和 Treemap。这两个类都实现Map接口。
散列映射表对键进行散列,树映射表用键的整体顺序对元素进行排序,并将其组织成搜索树。散列或比较函数只能作用于键。与键关联的值不能进行散列或比较
13.2.9 专用集与映射表类
1.弱散列映射表
下面是这种机制的内部运行情况。 Weakhashmap使用弱引用( weak references)保存键。Weak Reference对象将引用保存到另外一个对象中,在这里,就是散列表键。对于这种类型的对象,垃圾回收器用一种特有的方式进行处理。通常,如果垃圾回收器发现某个特定的对象已经没有他人引用了,就将其回收。然而,如果某个对象只能由 Weak Reference引用,垃圾回收器仍然回收它,但要将引用这个对象的弱引用放入队列中。 Weakhashmap将周期性地检查队列,以便找出新添加的弱引用。一个弱引用进入队列意味着这个键不再被他人使用,并且已经被收集起来。于是, Weak Hashmap将删除对应的条目。
2.链接散列表和链接映射表
Java Se1.4增加了两个类: Linked Hash Set和 Linkedhashmap,用来记住插入元素项的顺序。这样就可以避免在散列表中的项从表面上看是随机排列的。
3.枚举集与映射表
Enumset是一个枚举类型元素集的高效实现。由于枚举类型只有有限个实例,所以Enum set内部用位序列实现。如果对应的值在集中,则相应的位被置为1Enumset类没有公共的构造器。可以使用静态工厂方法构造这个集。
Enummap是一个键类型为枚举类型的映射表。它可以直接且高效地用一个值数组实现在使用时!,需要在构造器中指定键类型。
4.标识散列映射表
Java SE14还为另外一个特殊目的增加了另一个类 Identity Hashmap。在这个类中,键的散列值不是用 hash Code函数计算的,而是用 System identity Hash Code方法计算的。这是Object. hashcode方法根据对象的内存地址来计算散列码时所使用的方式。而且,在对两个对象进行比较时, Identity Hashmap类使用==,而不使用 equals也就是说,不同的键对象,即使内容相同,也被视为是不同的对象。在实现对象遍历算法(如又对象序列化)时,这个类非常有用,可以用来跟踪每个对象的遍历状况。