第九章 集合

发表于 | 分类于 |

第九章 集合

9.1 Java集合框架

9.1.1 集合接口与实现分离

与现代的数据结构类库的常见做法一样，Java集合类库也将接口(interface)与实现(implementation)分离。下面利用我们熟悉的数据结构——队列(Queue)来说明是如何分离的。

队列接口指出可以在队列的尾部添加元素，在队列的头部删除元素，并且可以查找队列中元素的个数。当需要收集对象，并按照“先进先出”方式检索对象时就应该使用队列。

队列接口的最简形式可能类似下面这样：

1
2
3
4
5
6
public interface Queue<E>
{
    void add(E element);
    E remove();
    int size();
}

这个接口并没有说明是如何实现的。队列通常有两种实现方式”一种是使用循环数组；另一种是使用链表。

每一个实现都可以用一个实现了Queue接口的类表示。

1
2
3
4
5
6
7
8
9
10
public class CircularArrayQueue<E> implements Queue<E>
{
    private int head;
    private int tail;
    CircularArrayQueue(int capacity){...}
    public void add(E element){...}
    public E remove(){...}
    public int size(){...}
    private E[] elemnts;
}
1
2
3
4
5
6
7
8
9
10
public class LinkedListQueue<E> implements Queue<E>
{
    private Link head;
    private Link tail;
    
    LinkedListQueue(){...}
    public void add(E elment){}
    public E remove(){...}
    public int size(){...}
}

当在程序中使用队列时，一旦已经构造了集合，就不需要知道究竟使用了哪种实现。因此，只有在构造集合对象时，才会使用具体的类。可以使用接口类型存放集合引用。

1
2
Queue<Customer> expressLane = new CircularArrayQueue<>(100);
expressLane.add(new Customer("Harry"));

利用这种方法，一旦改变了想法，就可以很轻松地使用另一种不同的实现。只需要对程序的一个地方做出修改，即调用构造器的地方。如果觉得LinkedListQueue是个更好的选择，就将代码修改为：

1
2
Queue<Customer> expressLane = new LinkedListQueue<>();
expressLane.add(new Customer("Harry"));

为什么选择这种实现，而不选择那种实现呢？接口本身并不能说明哪种实现的效率究竟如何。循环数组要比链表更高效，因此多数人优先选择循环数组。不过，通常来讲，这样做也需要付出一定的代价。

循环数组是一个有界集合，即容量有限。如果程序中要收集的对象数量没有上限，就最好使用链表来实现。

在研究API文档时，会发现另外一组名字以Abstract开头的类，例如，AbstractQueue。这些库是为类库实现者而设计的。如果想要实现自己的队列类，会发现扩展AbstractQueue类要比实现Queue接口中的所有方法轻松的多。

9.1.2 Collection 接口

在Java类库中，集合类的基本接口是Collection接口。这个接口有两个基本方法：

1
2
3
4
5
6
public interface Collection<E>
{
    boolean add(E element);
    Iterator<E> iterator();
    ...;
}

除了这两个方法之外，还有几个方法。

add方法用于向集合中添加元素。如果添加元素确实改变了集合就返回true；如果集合没有发生变化就返回flase。例如，如果试图向集(set)中添加一个对象，而这个对象在集中已经存在，这个add请求就没有失效，因为集中不允许有重复的对象。

iterator方法用于返回一个实现了Iterator接口的对象。可以使用这个迭代器对象依次访问集合中的元素。

9.1.3 迭代器

Iterator接口包含4个方法：

1
2
3
4
5
6
7
public interface Iterator<E>
{
    E next();
    boolean hasNext();
    void remove();
    default void forEachRemaining(Consumer<? super E> action)
}

通过反复调用next方法，可以逐个访问集合中的每个元素。但是，如果到达了集合的末尾，next方法将抛出一个NoSuchElementException。因此，需要在调用之前调用hasNext方法。如果迭代器对象还有多个可以访问的元素，这个方法返回true。如果想要查看集合中的所有元素就请求一个迭代器，当hasNext()返回true时就反复地调用next方法。例如：

1
2
3
4
5
6
7
Collection<String> c = ...;
Iterator<String> it = c.iterator();
while(it.hasNext)
{
    String element = it.next();
    //do something with element
}

用for each 循环可以更简练地表示同样的循环操作：

1
2
3
4
for(String element : c)
{
    //do something with element
}

编译器简单地将for each 循环转换为带有迭代器的循环。

for each 循环可以处理任何实现了Iterable接口的对象，这个接口只包含了一个抽象方法：

1
2
3
4
5
public interface Iterable<E>
{
    Iterator<E> iterator();
    ...
}

Collection 接口扩展了Iterable。因此，对于标准类库中的任何集合都可以使用for each 循环。

也可以不写循环，而是调用forEachRemaining方法并提供一个lambda表达式。将对迭代器的每一个元素调用这个lambda表达式，直到再没有元素为止。

1
iterator.forEachRemaining(element -> do something with element)

访问元素的顺序取决于集合类型。如果迭代器处理一个ArrayList，迭代器将从索引0开始，每迭代一次，索引值+1.不过，如果访问HashSet中的元素，会按照一种基本上随机的顺序获得元素。虽然可以确保在迭代过程中能够遍历到集合中的所有元素，但是无法预知访问各元素的顺序。这通常并不是什么问题，因为对于计算总和或匹配之类的计算，顺序并不重要。

Java集合类库中的迭代器与其他类库中的迭代器在概念上有着重要的区别。在传统的集合类库中，例如，C++的标准模板库，迭代器是根据数组索引建模的。如果给定这样一个迭代器，可以查找存储在指定位置上的元素，就像如果知道数组索引i，就可以查找数组元素a[i]。不需要查找元素，也可以将迭代器向前移动一个位置。这与不需要执行查找操作而通过i++将数组索引向前移动一样。但是，java迭代器并不是这样处理的。查找操作与位置变更紧密耦合。查找一个元素的唯一方法是调用next()，而在执行查找操作的同时，迭代器的位置就会随之向前移动。

因此，可以认为Java迭代器位于两个元素之间。当调用next时，迭代器就越过下一个元素，并返回刚刚越过的那个元素的引用。

Itterator接口的remove方法将会删除上次调用next方法时返回的元素。在大多数情况下，这是有道理的，在决定删除某个元素之前应该先看一下这个元素。不过，如果想要删除指定位置上的元素，仍然需要越过这个元素。例如，可以如下删除一个字符串集合中的第一个元素：

1
2
3
Iterator<String> it = c.iterator();
it.next;// skip over the first element
it.remove();//now remove it

更重要的是，next方法和remove方法调用之间存在依赖性。如果调用remove之前没有调用next，将是不合法的。如果这样做，将会抛出一个IllegalStateException异常。

如果想要删除两个相邻的元素，不能直接这样调用：

1
2
it.remove();
it.remove();//ERROR

实际上，必须先调用next越过要删除的元素。

1
2
3
it.remove();
it.next();
it.remove();//OK

9.1.4 泛型实用方法

由于Collection与Iterator都是饭泛型接口，这意味着你可以编写任何集合类型的实用方法。例如，下面是一个检测任意集合是否包含指定元素的泛型方法：

1
2
3
4
5
6
7
8
9
public static <E> boolean contains(Collection<E> c, Object obj)
{
    for(E elmement : c)
    {
        if(element.equals(obj))
            return true;
        return false
    }
}

Java类库的设计者认为：这些实用方法中有一些非常有用，应该将它们提供给用户使用。这样，类库的使用者就不必自己重新构建这些方法了。contains就是这样一个实用方法。

事实上，Collection接口声明了很多有用的方法，所有实现类都必须提供这些方法。下面列举了其中的一部分：

  • int size()
  • boolean isEmpty()
  • boolean contains(Object obj)
  • boolean containsAll(Collection<?> c)
  • boolean equals(Object other)
  • boolean addAll(Collection<?> c)
  • void clear()
  • boolean retainAll(Collection<?> c)
  • Object[] toArray()
  • \ T[] toArray(T[] arrayToFill)

在这些方法中有许多方法的功能非常明确，不需要过多的解释。

当然，如果实现Collection接口的每一个类都要提供如此多的例行方法，这将是一件很烦人的事情。为了能够让实现者更容易地实现这个接口，Java类库提供了一个类AbstractCollection，它保持基础方法size和iterator仍为抽象方法，但是为实现者实现了其他例行方法。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public abstract class AbstractCollection<E> implements Collection<E>
{
    ...;
    public abstract Iterator<E> iterator();
    
    public boolean contains(Object obj)
    {
        for(E element : this)
        {
            if(element.equals(obj))
                return true;
        }
        return false;
    }
    ...;
}

这样一来，具体集合可以扩展AbstractColletion类。现在要由具体的集合类提供iterator方法，而contains方法已由AbstractColletion超类提供。不过，如果子类有更加高效的方式实现cotains方法，也完全可以由子类提供contains方法。

这种做法有些过时了。这些方法最好是Collection接口的默认方法。但实际上并不是这样。不过，确实已经增加了很多默认方法。其中大部分方法都与流的处理有关。另外，还有一个很有用的方法：default boolean ramoveIf(Predicate<? super E> filter)这个方法用于删除满足某个条件的元素。

9.2 集合框架中的接口

集合中有两个基本接口：Coection和Map。我们已经看到，可以用以下方法在集合中插入元素：

1
boolean add(E element)

不过，由于映射包含键/值对，所以要用put方法来插入：

1
V put(K key, V value)

要从集合读取元素，可以用迭代器访问元素。不过，从映射中读取值则要使用get方法：

1
V get(K key)

List是一个有序集合(ordered collection)。元素会增加到容器中的特定位置。可以采用两种方式访问元素：使用迭代器，或者使用一个整数索引来访问。后面这种方法称为随机访问(random access)，因为这样可以按照任意顺序访问元素。与之不同，使用迭代器访问时，必须顺序地访问元素。

List接口定义了多个用于随机访问的方法：

1
2
3
4
void add(int index , E element)
void remove(int index)
E get(int index)
E set(int index, E element)

ListIterator接口是Iterator的一个子接口。它定义了一个方法用于在迭代器位置前面增加了一个元素：

1
void add(E element)

坦率地讲，集合框架的这个方面设计得很不好。实际上有两种有序集合，其性能开销有很大差异。由数组支持的有序集合可以快速地随机访问，因此适合使用List方法并提供一个整数索引来访问。与之不同，链表尽管也是有序的，但是随机访很慢，所以最好使用迭代器来遍历。如果原先提供两个接口就会容易一些了。

set接口等同于Collection接口，不过其方法的行为有更严谨的定义。集(set)的add方法不允许增加重复的元素。要适当定义集的equals方法：只要两个集包含同样的元素就认为它们是相等的，而不要求这些元素有同样的顺序。hashCode方法的定义要保证包含相同元素的两个集合会得到相同的散列码。

既然方法签名是一样的，为什么还要建立一个单独的接口呢？从概念上讲，并不是所有集合都是集。建立一个Set接口可以允许程序员编写只接受集的方法。

SortedSet和SortedMap接口会提供用于排序的比较器对象，这两个接口定义了可以得到集合子集试图的方法。

最后，Java6引入了接口NavigableSet和NavigableMap，其中包含一些用于搜索和遍历有序集合映射的方法。TreeSet和TreeMap类实现了这些接口。

9.3 具体集合

集合类型 描述
ArrayList
LinkedList
ArrayDeque
HashSet
TreeSet
EnumSet
LinkedHashSet
PriorityQueue
HashMap
TreeMap
EnumMap
LinkedHashMap
WeakHashMap
IdentityHashMap

9.3.1 链表

在本书中，有很多示例已经使用了数组以及动态的ArrayList类。不过，数组和数组列表都有一个重大的缺陷。这就是从数组中删除一个元素开销很大，其原因是数组中位于被删除元素之后的所有元素都要向数组的前端移动。在数组中间插入一个元素也是如此。

大家都知道的另外一个数组结构——链表(linked list)解决了这个问题。数组是在连续的存储位置上存放对象引用，而链表则是将每个对象存放在单独的链接(link)中。每个连接还存放这序列中下一个连接的引用。在Java程序设计语言上，所有链表实际上都是双向链接的(doubly linked)——即每个链接还存放着其前驱的引用。

从链表中间删除一个元素是一个很轻松的操作，只需要更新所删除元素周围的链接即可。

你也许曾经在数据结构中学习如何实现链表。在链表中添加或删除元素时，绕来绕去的指针可能给人们留下了极坏的印象。如果真是如此的话，你肯定为Java集合类库提供一个LinkedList类而感到高兴。

在下面的代码示例中，先添加3个元素，然后再将第2个元素删除：

1
2
3
4
5
6
7
8
LinkedList<String> staff = new LinkedList<String>();
staff.add("Amy");
staff.add("Bob");
staff.add("Carl");
Iterator<String> iter = staff.iterator();
String first = iter.next();// visit first element
String second = iter.next();// visit second element
iter.remove();// remove last visited element

不过，链表与泛型集合之间有一个重要区别。链表是一个有序集合(ordered collection)，每个对象的位置十分重要。LinkedList.add方法将对象添加到链表的尾部。但是，常常需要将元素添加到链表的中间。由于迭代器描述了集合中的位置，所以这种依赖于位置的add方法将由迭代器负责。只有对自然有序的集合使用迭代器添加元素才有实际意义。例如，下一节将要讨论的集(set)数据类型中，元素是完全无序的。因此，Iterator接口中没有add方法。实际上，集合类库提供了一个子接口ListIterator，其中包含add方法：

1
2
3
4
5
interface ListIterator<E> extends Iterator<E>
{
    void add(E element);
    ...;
}

与Collection.add不同，这个方法不返回boolean类型的值，它假定add操作总会改变链表。

另外，ListIterator接口有两个方法。可以用来反向遍历链表。

1
2
E previous()
boolean hasPrevious()

与next方法一样，previous方法返回越过的对象。

LinkedList类的listIterator方法返回一个实现了ListIterator接口的迭代器对象。

1
ListIterator<String> iter =  staff.listIterator();

add方法在迭代器位置之前添加一个新对象。例如，下面的代码越过链表中的第一个元素，在第二个元素之前添加“Juliet”：

1
2
3
4
5
6
7
LinkedList<String> staff = new LinkedList<String>();
staff.add("Amy");
staff.add("Bob");
staff.add("Carl");
LsitIterator<Stirng> iter = staff.listIterator();
iter.next();
iter.add("Juliet");

如果多次调用add方法，按照提供的次序把元素添加到链表中。他们被依次添加到迭代器当前位置之前。

当用一个刚由listIterator方法返回并指向链表表头的迭代器调用add操作时，新添加的元素将变成列表的新表头。当迭代器越过链表的最后一个元素时(hasNext返回false)，添加的元素将变成为列表的新表尾。如果链表有n个元素，会有n+1个位置可以添加新元素。这些位置与迭代器的n+1个可能的位置相对应。例如，如果链表包含3个元素，A，B，C就有4个位置可以插入新元素：

1
2
3
4
|ABC
A|BC
AB|C
ABC|

最后需要说明，set方法用一个新元素替换调用next或previous方法返回上一个元素：

1
2
3
ListIterator<String> iter = list.listIterator();
String oldValue = iter.next();
iter.set(newValue);

可以想象，如果在某个迭代器修改集合时，另一个迭代器却在遍历这个集合，那么一定会出现混乱。例如，假设一个迭代器指向一个元素前面的位置，而另一个迭代器刚刚删除了这个元素，现在前一个迭代器就是无效的，并且不能再使用。链表迭代器设计可以检测到这种修改。如果一个迭代器发现它的集合被另外一个迭代器修改了，或是被该集合自身的某个方法修改了，就会抛出一个ConcurrentModificationException异常。例如，考虑下面这段代码：

1
2
3
4
5
6
List<String> list = ...;
ListIterator<String> iter1 = list.listIterator();
ListIterator<String> iter2 = list.listIterator();
iter1.next();
iter1.remove();
iter2.next();//throws ConcurrentModificationException

由于iter2检测出这个链表从外部修改了，所以对iter2.next的调用抛出一个ConcurrentModificationException异常。

为了避免发生并发修改异常，请遵循这样一个简单的规则：可以根据需要为一个集合关联多个迭代器，前提是这些迭代器只能读取集合。或者，可以再关联一个能同时读写的迭代器。

有一种简单的方法可以检测到并发修改。集合可以跟踪更改操作的次数。每个迭代器都会为它负责的更改操作维护一个单独的更改操作数。在每个迭代器方法的开始处，迭代器会检查它自己的更改操作数是否与集合的更改操作数相等。如果不一致，就抛出一个ConcurrentModificationException异常。

现在已经介绍了LinkedLsit类的基本方法。可以使用ListIterator类从前后两个方向遍历链表中的元素，以及添加和删除元素。

在9.2节已经看到，Collection接口还声明了操作链表的很多其他有用的方法。其中大部分方法都是在LinkedList类的超类AbstractCollection中实现的。例如，toString方法调用了所有元素的toString，并产生了一个格式为[A,B,C]的长字符串。这为调试工作提供了便利。可以使用contains方法检测某个元素是否出现在链表中。例如，如果链表中已经包含了一个等于“Harry”的字符串，调用staff.conatins(“Harry”)将会返回true。

在Java类库中，还提供了许多在理论上存在一定争议的方法。链表不支持快速随机访问。如果要查看链表中的第n个元素，就必须从头开始，越过n-1个元素。没有捷径可走。

鉴于这个原因，需要按整数索引访问元素时，程序员通常不选用链表。

不过，LinkedList类还是提供了一个用来访问某个特定元素的get方法：

1
2
LinkedList<String> list = ...;
String obj = list.get(n);

当然，这个方法的效率并不太高。如果发现自己正在使用这个方法，说明对于所要解决的问题，你可能使用了错误的数据结构。

绝不应该使用这个“虚假”的随机访问来遍历链表。下面这段代码的效率极低：

1
2
3
4
for(int i = 0; i < list.size(); i++)
{
    do something with list.get(i);
}

每次查找一个元素都要从列表的头部重新开始搜索。LinkedList对象根本没有缓存位置信息。

列表迭代器接口还有一个方法，可以告诉你当前位置的索引。实际上，从概念上将，由于java迭代器指向两个元素之间的位置，所以可以有两个索引：nextIndex方法返回下一次调用next方法时所返回元素的整数索引；previousIndex方法返回下一次调用previous方法时所返回元素的整数索引。当然，这个索引只比nextIndex返回的索引值小1。这两个方法的效率非常高，因为有一个迭代器保持着当前位置的计数值。最后需要说明一点，如果有一个整数索引n，list.listIterator(n)将返回一个迭代器这个迭代器指向索引为n的元素前面的位置。也就是说，调用next()与调用list.get(n)会产生同一个元素，只是获得迭代器的效率比较低。

如果链表中只有很少几个元素，就完全没有必要为get方法和set方法的开销而烦恼。但是，最初为什么要使用链表呢？使用链表的唯一理由就是尽可能地减少在列表中间插入或删除元素的开销。如果列表只有很少几个元素，就完全可以使用ArrayList。

建议避免使用以整数索引表示链表中位置的所有方法。如果需要对集合进行随机访问，就使用数组或ArrayList，而不要使用链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package linkedlist;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;

public class LinkedlistTest
{
    public static void main(String[] args)
    {
        LinkedList<String> a = new LinkedList<>();
        a.add("Amy");
        a.add("Carl");
        a.add("Erica");

        LinkedList<String> b = new LinkedList<>();
        b.add("Bob");
        b.add("Doug");
        b.add("Frances");
        b.add("Gloria");

        ListIterator<String> aIter = a.listIterator();
        Iterator<String> bIter = b.iterator();

        while (bIter.hasNext())
        {
            if (aIter.hasNext()) aIter.next();
            aIter.add(bIter.next());
        }

        System.out.println(a);

        bIter = b.iterator();//重制迭代器

        //间隔删除b中的元素
        while (bIter.hasNext())
        {
            bIter.next();
            if (bIter.hasNext())
            {
                bIter.next();
                bIter.remove();
            }
        }

        System.out.println(b);

        //在a中删除b里的元素
        a.removeAll(b);
        System.out.println(a);

    }
}

9.3.2 数组列表

在上一节中，介绍了List接口和实现这个接口的LikedList类。List接口用于描述一个有序集合，并且集合中每个元素的位置都很重要。有两种访问元素的协议：一种是通过迭代器，另一种是通过get和set方法随机地访问每个元素。后者不适用于链表，但当然get和set方法对数组很有用。集合类库提供了一种大家熟悉的ArrayList类，这个类也实现了List接口。ArrayList封装了一个动态再分配的对象数组。

9.3.3 散列集

链表和数组允许你根据意愿指定元素的次序。但是，如果想要查看某个指定的元素，却又不记得它的位置，就需要访问所有元素，直到找到为止。如果集合中包含的元素很多，这将会需要很长的时间。如果不在意元素的顺序，有几种能够快速查找元素的数据结构。其缺点是无法控制元素出现的次序。这些数据结构按照对自己最方便的方式组织元素。

有一种众所周知的数据结构，可以用于快速地查找，这就是散列表(hash table)。散列表为每个对象计算一个整数，称为散列码(hash code)。散列码是由对象的实例字段得出的一个整数。更准确地说，有不同数据的对象将产生不同的散列码。例如：它们是由String类的hashcode方法产生的。

字符串 散列码
“Lee” 76268
“lee” 107020
“eel” 100300

如果定义你自己的类，你就要负责实现自己得hashCode方法。有关hashCode方法的详细内容请参看第五章。注意，你的实现应该与equals方法兼容，即如果a.equals(b)为true，a与b必须有相同的散列码。

现在，最重要的问题是要能够快速计算出散列码，并且这个计算只与要计算散列的那个对象的状态有关，与散列表中的其他对象无关。

在Java中，散列表用链表数组实现。每个列表被称为桶(bucket)。想要查找表中对象的位置，就要先计算它的散列码，然后与桶的总数取余，所得到的结果就是保存这个元素的桶的索引。例如，如果某个对象的散列码为76268，并且有128个桶，那么这个对象应该保存在第108号桶中。或许很幸运，在这个桶中没有其他元素，此时将元素直接插入到桶中就可以了。当然，有时候会遇到桶已经被填充的情况。这种现象被称为散列冲突(hash collision)。这时，需要将新对象与桶中的所有对象进行比较，查看这个对象是否存在。如果散列码合理地随机分布，桶的数目也足够大，需要比较的次数就会很少。

如果想要更多地控制散列表的性能，可以指定一个初始的桶数。桶数是指用于收集有相同散列值的桶的数目。如果要插入到散列表中的元素太多，就会增加冲突数量，降低检索性能。

如果大致知道最终会有多少个元素要插入到散列表中，就可以设置桶数。通常，将桶数设置为预计元素个数的75%~150%。有些研究人员认为：最好将桶数设置是2的幂，默认值为16.

当然，并不总是能够知道需要存储多少个元素，也有可能最初的估计过低。如果散列表太满，就需要再散列(rehashed)。如果要对散列表再散列，就需要创建一个桶数更多的表，并将所有元素插入到这个新表中，然后丢弃原来的表。装填因子(load factor)可以确定何时对散列表进行再散列。例如，如果装填因子为0.75，说明表中已经填满了75%以上，就会自动再散列，新表的桶数是原来的两倍。对于大多数应用程序来说，装填因子为0.75是合理的。

散列表可以用于实现很多重要的数据结构。其中最简单的是集类型。集是没有重复元素的元素集合集的add方法首先在这个集中查找要添加的对象，如果不存在，就添加这个对象。

Java集合类库提供了HashSet类，它实现了基于散列表的集。可以用add方法添加元素。contains方法已经被重新定义，用来快速查找某个元素是否已经在集中。它只查看一个桶中的元素，而不必查看集合中的所有元素。

散列集迭代器将依次访问所有的桶。由于散列将元素分散在表中，所以会一种看起来随机的顺序访问元素。只有不关心集合中的顺序时才应该使用HashSet。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package setStudent;

import java.util.Objects;

public class Student
{
    private String name;
    private int age;

    public Student(){}

    public Student(String name, int age)
    {
        this.name = name;
        this.age = age;
    }

    public String getName()
    {
        return this.name;
    }

    public int getAge()
    {
        return this.age;
    }

    public void setName(String name)
    {
        this.name = name;
    }

    public void setAge(int age)
    {
        this.age = age;
    }

    @Override
    public String toString()
    {
        return "Student: name=" + this.name + ",age=" + this.age;
    }

    @Override
    public int hashCode()
    {
        return Objects.hash(this.name,this.age);
    }

    @Override
    public boolean equals(Object obj)
    {
        if (this == obj) return true;
        if (obj == null) return false;
        if (this.getClass() != obj.getClass()) return false;
        Student otherobj = (Student)obj;

        return Objects.equals(this.name,otherobj.name) && this.age == otherobj.age;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package setStudent;

import java.util.HashSet;

public class HashsetTest
{
    public static void main(String[] args) {
        HashSet<Student> hs = new HashSet<>();//创建HashSet集合

        //创建学生对象
        Student s1 = new Student("qwe",18);
        Student s2 = new Student("asd",19);
        Student s3 = new Student("zxc",18);
        Student s4 = new Student("asd",19);
        Student s5 = new Student("zxc",18);

        //把学生添加到集合
        hs.add(s1);
        hs.add(s2);
        hs.add(s3);
        hs.add(s4);
        hs.add(s5);

        //遍历集合
        for (Student s : hs)
        {
            System.out.println(s);
        }

    }
}

9.3.4 树集

TreeSet类与散列集十分类似，不过，它比散列集有所改进。树集是一个有序集合(sorted collection)。可以以任意顺序将元素插入到集合中。在对集合进行遍历时，值将自动地按照排序后的顺序呈现。例如，假设插入3个字符串，然后访问添加的所有元素。

1
2
3
4
5
6
7
8
TreeSet<String> sorter = new TreeSet<String>();
sorter.add("Bob");
sorter.add("Amy");
sorter.add("Carl");
for(String s : sorter)
{
    System.out.println(s);
}

这时，值按照有序打印：Amy Bob Carl。正如TreeSet类名所示，排序是用一个是数据结构完成的(当前实现使用的是红黑树(red-black tree))。每次将一个元素添加到树中时，都会将其放置在正确的排序位置上。因此，迭代器总是以有序的顺序访问每个元素。

将一个元素添加到树中要比添加到散列表中慢，但是，与检查数组或链表中的重复元素相比，使用树会快很多。如果树中包含了1000个元素，添加一个新元素大约需要比较10次。

你可能很想知道是否应该总是用树集而不是散列集。毕竟，添加一个元素所花费的时间上去并不很长，而且元素是自动排序的。到底应该怎样做取决于所要收集的数据。如果不需要数据是有序的，就没有必要付出排序。更重要的是，对于某些数据来说，对其进行排序要比给出一个散列函数更加困难。散列函数只需要将对象适当地打乱存放，而比较函数必须精确地区分各个对象。

想要具体了解它们之间的差异，可以考虑收集一个矩形集的任务。如果使用TreeSet，就需要提供Comparator\。如何比较两个矩形呢？比较面积吗？这行不通。可能会有两个不同的矩形，它们的坐标不同，但面积却相同。树的排序顺序必须是全序。也就是说，任意两个元素都必须是可比的，并且只有两个元素相等时结果才为0.矩形确实有一种排序方式(按照坐标的词典顺序排序)，但这很牵强，而且计算繁琐。相反地，Rectangle类已经定义了散列函数，它直接对坐标进行散列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package treeSet;

import java.util.Objects;

public class Item implements Comparable<Item>
{
    private String description;
    private int partNumber;

    public Item(String description, int partNumber)
    {
        this.description = description;
        this.partNumber = partNumber;
    }

    public String getDescription()
    {
        return this.description;
    }

    @Override
    public String toString()
    {
        return "[description=" + this.description + ",partNumber=" + this.partNumber + "]";
    }

    @Override
    public boolean equals(Object obj)
    {
        if (this == obj) return true;
        if (obj == null) return false;
        if (this.getClass() != obj.getClass()) return false;

        Item otherObj = (Item)obj;
        return Objects.equals(this.description,otherObj.description) && this.partNumber == otherObj.partNumber;
    }


    @Override
    public int hashCode()
    {
        return Objects.hash(this.description,this.partNumber);
    }

    @Override
    public int compareTo(Item obj)
    {
        int diff = Integer.compare(this.partNumber,obj.partNumber);
        return diff != 0? diff : this.description.compareTo(obj.description);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package treeSet;

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetTest
{
    public static void main(String[] args)
    {
        TreeSet<Item> parts = new TreeSet<>();
        parts.add(new Item("Toaster",1234));
        parts.add(new Item("Widget",4562));
        parts.add(new Item("Modem",9912));

        System.out.println(parts);

        TreeSet<Item> sortByDescription = new TreeSet<>(Comparator.comparing(Item::getDescription));

        sortByDescription.addAll(parts);
        System.out.println(sortByDescription);
    }
}

9.3.5 队列与双端队列

前面已经讨论过，队列允许你高效地在尾部添加元素，并在头部删除元素。双端队列(即deque)允许在头部和尾部都高效地添加或删除元素。不支持在队列中间添加元素。Java6中引入了Deque接口，ArrayDeque和LinkedList类实现了这个接口。这两个类都可以提供双端队列，其大小可以根据需要扩展。

9.3.6 优先队列

优先队列(priority queue)中的元素可以按照任意的顺序插入，但会按照有序的顺序进行检索。也就是说，无论何时调用remove方法，总会获得当前优先队列中最小的元素。不过，优先队列并没有对所有元素进行排序。如果迭代处理这些元素，并不需要对它们进行排序。优先队列使用了一个精巧且高效的数据结构，称为堆(heap)。堆是一个可以自组织的二叉树，其添加(add)和删除(remove)操作可以让最小的元素移动到根，而不必花费时间对元素进行排序。

与TreeSet一样。优先队列既可以实现了Comparable接口的类对象，也可以保存构造器中提供的Comparator对象。

优先队列的典型用法是任务调度。每一个任务有一个优先级，任务以随机顺序添加到队列中。每当启动一个新的任务时，都将优先级最高的任务从队列中删除。

9.4 映射

即时一个集合，允许你快速地查找现有的元素。但是，要查找一个元素，需要有所要查找的那个元素的准确副本。这不是一种常见的查找方式。通常，我们知道某些关键信息，希望查找与之关联的元素。映射(map)数据结构就是为此设计的。映射用来存放键/值对。如果提供了键，就能够查找到值。例如，可以存储一个员工记录表，其中键为员工ID，值为Employee对象。

9.4.1 基本映射操作

Java类库为映射提供了两个通用的实现：HashMap和TreeMap。这两个类都实现了Map接口。

散列映射对键进行散列，树映射根据键的顺序将元素组织为一个搜索树。散列或比较函数只应用于键。与键关联的值不进行散列或比较。

应该选择散列映射还是树映射呢？与集一样，散列稍微快一些，如果不需要按照有序的顺序访问键，最好选择散列映射。

以下代码将建立一个散列映射来存储员工信息：

1
2
3
HashMap<String,Employee> = new HashMap<>();
Employee harry = new Employee("Harry Hackr");
staff.put("983-98-996",harry);

每当往映射中添加一个对象，必须同时提供一个键。在这里，键是一个字符串，对应的值是Employee对象。

想要检索一个对象，必须使用键。

1
2
String id = "987-98-9996";
Employee e = staff.get(id);//gets harry

如果映射没有存储给定键对应的信息，get将返回null。

null返回值可能并不方便。有时对应没有出在映射中的键，可以使用一个好的默认值。

然后使用getOrDefault方法。

1
2
Map(String,Integer) scores = ...;
int scores = scores.getOrDefault(id,0);//gets 0 if the id is not present

键必须是唯一的。不能对同一个键存放两个值。如果对同一个键调用两次put方法，第二个值就会取代第一个值。实际上，put将返回与这个键参数关联的上一个值。

remove方法从映射中删除给定对应的元素。size方法返回映射中的元素数。

要迭代处理映射的键和值，最容易的方法是使用forEach方法。可以提供一个接收键和值的lambda表达式。映射中的每一项会依次调用这个表达式。

1
2
scores.forEach((k,v) ->
              System.out.println("key=" + k + ",value=" + v));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package map;

import java.util.HashMap;

public class MapTest
{
    public static void main(String[] args)
    {
        HashMap<String,Employee> staff = new HashMap<>();

        staff.put("144-25-5464",new Employee("Amy Lee"));
        staff.put("567-24-2546",new Employee("Harry Hacker"));
        staff.put("157-62-7935",new Employee("Gary Cooper"));
        staff.put("456-62-5527",new Employee("Francesca Cruz"));

        //print all entries

        System.out.println(staff);

        // remove an entry

        staff.remove("567-24-2546");

        //replace an entry

        staff.put("456-62-5527",new Employee("Francesca Miller"));

        //look up a value

        System.out.println(staff.get("157-62-7935"));

        //iterate through all entries

        staff.forEach((k,v) ->
                System.out.println("key" + k + ",value=" + v));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package map;

public class Employee
{
    private String name;

    public Employee(){}

    public Employee(String name)
    {
        this.name = name;
    }

    @Override
    public String toString()
    {
        return "Employee=" + this.name;
    }
}

9.4.2 跟新映射条目

处理映射的一个难点就是更新映射条目。正常情况下，可以得到与一个键关联的原值，完成更新，再放回更新后的值。不过，必须考虑一个特殊情况，即键第一次出现。下面看一个例子，考虑使用映射统计一个单词在文中出现的频度。看到一个单词(word)时，我们将计数器增1，如下所示：

1
counts.put(word,counts.get(word) + 1);

这是可以的，不过有一种特殊情况除外：就是第一次看到word时。在这种情况下，get会返回null，因此会出现一个NullPointerException异常。

一个简单的补救是使用getOrDefault方法：

1
counts.put(word,counts.getOrDefault(word,0) + 1);

另外一种方法是首先调用putIfAbsent方法。只有当键原先存在时才会放入一个值。

1
2
counts.putIfAbsent(word,0);
counts.put(word,counts.get(word) + 1);

不过还可以做得更好。merge方法可以简化这个常见操作。如果键原先不存在，下面调用：

1
counts.merge(word,1,Integer::sum);

将把word与1关联，否则使用Integer::sum函数组合原值和1

9.4.3 映射视图

集合框架不认为映射本身是一个集合。不过，可以得到映射的视图(view)——这是实现了Collection接口或某个子类接口的对象。

有三种视图：键值、值集合以及键/值对集。键和键/值对可以构成一个集，因为映射中一个键只能有一个副本。下面的方法：

1
2
3
Set<k> keySet()
Collection<v> values()
Set<Map.Entry<k,v>> entrySet()

会分别返回这3个视图。

需要说明的是，keySet不是HshSet或TreeSet，而是实现了Set接口的另外某个类的对象。Set接口扩展了Collection接口。因此，可以像使用任何集合一样使用keySet。

例如，可以枚举一个映射的所有键：

1
2
3
4
5
Set<String> keys = map.keySet();
for(String key : keys)
{
    do something with key
}

如果想同时查看键和值，可以通过枚举映射条目来避免查找值。使用以下代码：

1
2
3
4
5
6
for(Map.Entry<String,Employee> entry : staff.entrySet())
{
    String k = entry.getkey();
    Employee v = entry.getVaule();
    do something with k,v
}

【可以使用var声明避免笨拙的Map.Entry】

1
2
3
4
for(var entry : staff.entrySet())
{
    do something with entry.getkey(),entry.getVaule()
}

如今，只需要使用forEach方法：

1
2
map.forEach((k,v) ->
            {do something with k,v});

如果在键集视图上调用迭代器的remove方法，实际上会从映射中删除这个键和它关联的值。不过，不能向键集视图中添加元素。另外，如果添加一个键而没有同时添加值也是没有意义的。如果试图调用add方法，它会抛出一个UnsupportedOperationException。映射条目集视图有同样的限制，尽管理论上增加一个新的键/值对好像有意义。

9.4.4 弱散列映射

设计WeakHashMap类是为了解决一个有趣的问题。如果有一个值，它对应的键已经不再在程序中的任何地方使用，将会出现什么情况呢？假定对某个键的最后一个引用已经消失，那么不再有任何途径可以引用这个值的对象了。但是，由于程序中的任何部分不会再有这个键，所以，无法从映射中删除这个值/键对。为什么垃圾回收器不能删除它呢？删除无用的对象不就是垃圾回收器的工作吗？

遗憾的是，事情没有这么简单。垃圾回收器会跟踪活动的对象。只要映射对象是活动的，其中的所有桶也是活动的，他们不能被回收。因此，需要由程序负责从长期存活的映射表中删除那些无用的值。或者，你可以使用WeakHashMap。当对键的唯一引用来自散列表映射条目时，这个数据结构与垃圾回收器协同工作一起删除键/值对。

WeakHashMap使用弱引用(weak references)保存键。WeakReference对象将包含另一个对象的引用，在这里，就是一个散列表键。对于这种类型的对象，垃圾回收器采用一种特有的方式进行处理。正常情况下，如果垃圾回收器发现某个特定的对象已经没有他人引用了，就将其回收。然而，如果某个对象只能由WeakReference引用，垃圾回收器也会将其回收，但会将引用这个对象的弱引用放入一个队列。WeakHashMap将周期性地检查队列，以便找出新添加的弱引用。一个弱引用进入队列意味着这个键不再被他人使用，并且已经回收。于是，WeakHashMap将删除相关联的映射条目。

9.4.5 链接散列集与映射

LinkedHashSet和LinkedHashMap类会记住插入元素项的顺序。这样就可以避免散列表中的项看起来顺序是随机的。在表中插入元素项时，就会并入到双向链表中。

例如以下处理：

1
2
3
4
5
LinkedHashMap<String,Employee> staff = new LinkedHashMap<>();
staff.put("144-25-5464",new Employee("Ame Lee"));
staff.put("567-24-2546",new Employee("Harry Hacker"));
staff.put("157-62-7935",new Employee("Gary Cooper"));
staff.put("456-62-5527",new Employee("Francesca Cruz"));

然后，staff.keySet().iterator()以下面的次序枚举键：

1
2
3
4
144-25-5464
567-24-2546
157-62-7935
456-62-5527

staff.values()/iterator()以下面的顺序枚举值：

1
2
3
4
Ame Lee
Harry Hacker
Gary Cooper
Francesca Cruz

或者，链接散列映射可以使用访问顺序而不是插入顺序来迭代处理映射条目。每次调用get或put时，受到影响的项将从当前的位置删除，并放到项链表的尾部。要构造这样一个散列映射，需要调用

1
LinkedHashMap<K,V>(initialCapacity,loadFactor,true)

访问顺序对于实现缓存的“最近最少使用”原则十分重要。例如，你可能需要将访问频率高的元素放在内存中，而访问频率低的元素从数据库中读取。当在表中找不到元素项而且表已经相当满时，可以得到表的一个迭代器，并删除它枚举的前几个元素。这些项是近期最少用的几个元素。

甚至可以让这一过程自动化，构造LinkedHashMap的一个子类，然后覆盖下面这个方法：

1
protected boolean removeEldestEntry(Map.Entry<K,V> eldest)

每当你的方法返回true时，添加一个新映射条目就会导致删除eldset项。例如，下面的缓存最多可以存放100个元素：

1
2
3
4
5
6
7
LinkedHashMap<K,V> cache = new LinkedHashMap<K,V>(18,0.75F，true)
{
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest)
    {
        return size() > 100;
    }
};

或者，还可以考虑eldst元素，来决定是否将它删除。例如，可以检查与这一项一起存储的时间戳。

9.4.6 枚举集与映射

EnumSet是一个枚举类型元素集的高效实现。由于枚举类型只有有限个实例，所以EnumSet内部用位序列实现。如果对应的值在集中，则相应的位置为1。

EnumSet类没有公共的构造器。要使用静态工厂方法构造这个集：

1
2
3
4
5
enum Weekday {MONDAT,TUESDAY,WEDNESDAY,THURSDAY,FRIDAY,SATURADAY,SUNDAY};
EnumSet<Weekday> always = EnumSet.allOf(Weekday.class);
EnumSet<Weekday> never = EnumSet.noneOf(Weekday.class);
EnumSet<Weekday> workday = EnumSet.range(Weekday.MONDAY,Weekday.FRIDAY);
EnumSet<Weekday> mwf = EnumSet.of(Weekday.MONDAY,Weekday.WEDNESDAY,Weekday.FRIDAY);

可以使用Set接口的常用方法来修改EnumSet。

EnumMap是一个键类型为枚举类型的映射。它可以直接且高效地实现为一个值数组。需要在构造器中指定键类型：

1
EnumMap<Weekday,Employee> personInCharge = new EnumMap<Weekday,Employee>(WeekDay.class);

9.4.7 标识散列映射

类IdentityHashMap有特殊的用途。在这个类中，键的散列值不是用hashCode函数计算的，而是用System.identityHashCode方法计算的。这是Object.hashCode根据对象的内存地址计算散列码。而且，在对两个对象进行比较时，IdentityHashMap类使用==，而不使用equals。

也就是说，不同的键对象即使内容相同，也被视为不同的对象。在实现对象遍历算法时，这个类非常有用，可以用来跟踪哪些对象已经遍历过。

9.5 视图与包装器

9.5.1 小集合

9.5.2 子范围

9.5.3 不可修改的视图

9.5.4 同步视图

9.5.5 检查型视图

9.5.6 关于可选操作的说明

9.6 算法

除了实现集合类，Java集合框架还提供了一些有用的算法。

9.6.1 为什么使用泛型算法

泛型集合接口有一个很大的优点，即算法只需要实现一次。例如，考虑一下计算集合中最大元素的简单算法。使用传统方式，程序设计人员可能会用循环实现这个算法。可以如下找出数组中最大的元素：

1
2
3
4
5
6
7
if(a.length = 0) throw new NoSuchElementException();
T largest = a[0];
for(int i = 1; i < a.length; i++)
{
    if(largest.compareTo(a[i]) < 0)
        largest = a[i];
}

当然，要找到数组列表的最大元素，编写的代码会稍有差别。

1
2
3
4
5
6
7
if(v.size() == 0) throws new NoSuchElementException();
T largest = v.get(0);
for(int i = 1; i < v.size(); i++)
{
    if(largest.compareTo(v.get(i)) < 0)
        largest = v.get(i);
}

链表呢？链表没有高效的随机访问操作，不过可以使用迭代器。

1
2
3
4
5
6
7
8
9
if(l.isEmpty()) throw new NoSuchElementException();
Iterator<T> iter = l.iterator();
T largest = iter.next();
while(iter.hasNext())
{
    T next = iter.next();
    if(largest.compareTo(next) < 0)
        largest = next;
}

编写这些循环很繁琐，而且很容易出错。是否存在“差1”错误(off-by-one error)?这些循环对于空容器能正常工作吗？对于只含有一个元素的容器又会发生什么情况呢？我们不希望每次都测试和调试这些代码，也不想实现如下的一系列方法：

1
2
3
static <T extends Comparable> T max(T[] a)
static <T extends Comparable> T max(ArrayList<T> v)
static <T extends Comparable> T max(LinkedList<T> l)

这里就可以使用集合接口。请考虑为了高效地执行这个算法所需要的最小集合接口。采用get和set方法的随机访问要比直接迭代层次高。在计算链表中最大元素的过程中已经看到，这项任务不需要随机访问。可以直接迭代处理元素来得出最大元素。因此，可以将max方法实现为能够接收任何实现了Collection接口的对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static <T extends Comparable> T max(Collection<T> c)
{
    if(c.isEmpty()) throw new NoSuchElementException();
    Iterator<T> iter = c.iterator();
    T largest = iter.next();
    while(iter.hasNext())
    {
        T next = iter.next();
        if(largest.compareTo(next) < 0)
            largest = next;
    }
    return largest;
}

现在就可以使用一个方法计算链表、数组列表或数组中最大元素了。

9.6.2 排序与混排

Collections类中的sort方法可以对实现了List接口的集合进行排序。

1
2
3
LinkedList<String> staff = new LinkedList<>();
fill collection
Collections.sort(staff);

这个方法假定列表元素实现了Comparable接口。如果想采用其他方式对列表进行排序，可以使用List接口的sort方法并传入一个Comparator对象。可以如下按工资对一个员工列表排序：

1
staff.sort(Comparator.comparingDouble(Employee::getSalary));

如果想按照降序对列表进行排序，可以使用静态的便利方法Collections.reverseOrder()。这个方法将返回一个比较器，比较器则返回b.comparaTo(a)。例如，

1
staff.sort(Comparator.reverseOrder)

这个方法将根据元素类型的compareTo方法所给定的排序顺序，按逆序对列表staff中的元素进行排序。同样地，

1
staff.sort(Comparator.comparingDoble(Employee::getSalary).reversed())

按工资逆序排序。

人们可能会sort方法如何如何排序感到好奇。通常，在查看有关算法书籍中的排序算法时，会发觉介绍的都是有关数组的排序算法，而且使用的是随机访问方式。但是，链表的随机访问效率很低。实际上，可以使用一种归并排序对链表高效地排序。不过，Java程序设计语言并不是这样做的。它只是将所有元素转入一个数组，对数组进行排序，然后，再将排序后的序列复制回列表。

集合类库中使用排序算法比快速排序要慢一些，快速排序(QuickSort)是通过排序算法的传统选择。但是，归并排序有一个主要的优点：归并排序有一个主要的优点：归并排序是稳定的，也就是说，它不会改变相等元素的顺序。为什么要关注想等元素的顺序呢？下面来看一种常见的情况。假设有一个已经按照姓名排序的员工列表。现在，要按照工资再进行排序。如果两个员工的工资相等会发生什么情况？如果采用稳定的排序算法，将会保留按名字排序的顺序。换句话说，排序的结果是得到一个首先按照工资排序再按照姓名排序的列表。

因为集合不需要实现所有的“可选”方法，因此，所有接受集合参数的方法必须描述什么时候可以安全地将集合传递给算法。例如，显然不能将unmodifiableList列表传递给sort算法。那么，可以传递什么类型的列表呢？根据文档说明，列表必须是可修改的，但不一定可以改变大小。

下面是有关的术语定义：

  • 如果列表支持set方法，则是可以修改的(modifiable)
  • 如果列表支持add和remove方法，则是可改变大小的(resizeable)

Collections类有一个算法shuffle，其功能与排序刚好相反，它会随机地混排列表中元素的顺序。例如：

1
2
ArrayList<Card> cards = ...;
Collections.shuffle(cards);

如果提供的列表没有实现RandomAccess接口，shuffle方法会将元素复制到数组中，然后打乱数组元素的顺序，最后再将打乱顺序后的元素复制回列表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package shuffle;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ShuffleTest
{
    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<>();
        for(int i=1; i <= 49; i++)
        {
            numbers.add(i);
        }
        Collections.shuffle(numbers);//打乱
        List<Integer> winningCombination = numbers.subList(0,6);//取下标为0~5的放入List
        Collections.sort(winningCombination);//排序
        System.out.println(winningCombination);

    }
}

9.6.3 二分查找

要想在数组中查找一个对象，通常要依次访问数组中的每个元素，直到找到匹配的元素为止。不过，如果数组是有序的，可以检查中间的元素，查看是否大于要查找的元素。如果是，就在数组的前半部分继续查找；否则，在数组的后半部分继续查找。这样就可以将问题规模缩减一半，并以同样的方式继续下去。

Collections类的binarySearch方法实现了这个算法。注意，集合必须是有序的，否则算法会返回错误的答案。想要查找某个元素，必须提供集合以及要查找的元素。如果集合没有采用Comparable接口的compareTo方法进行排序，那么还要提供一个比较器对象。

1
2
i = Collections.binarySearch(c,element);
i = Collections.binarySearch(c,element,comparator);

如果binarySearch方法返回一个非负的值，这表示匹配对象的索引。也就是说，c.get(i)等于在这个比较顺序下的element。如果返回负值，则表示没有匹配的元素。不过，可以利用返回值来计算应该将element插入到集合的哪个位置，以保持集合的有序性。插入的位置是

1
insertionPoint = -i -1;

这并不是简单的-i，因为0值是不确定的。也就是说，下面这个操作：

1
2
if(i < 0)
    c.add(-i - 1,element)

将把元素插入到正确的位置上。

只有采用随机访问，二分查找才有意义。如果必须利用迭代方式查找链表的一半元素来找到中间元素，二分查找就完全失去了优势。因此，如果binarySearch算法提供一个链表，它将自动地退化为线性查找。

9.6.4 简单算法

Collections类中包含几个简单但很有用的算法。这一节最前面介绍的例子就是其中的一个算法，即查找集合中的最大元素。其他算法还包括：将一个列表中元素复制到另外一个列表中；用一个常量值填充容量；逆置一个列表的元素顺序。

为什么在标准库中提供这些简单算法呢？大多数程序员肯定可以很容易地采用简单的循环实现这些任务。我们之所以喜欢这些算法，是因为它们可以让程序员更轻松地读代码。当阅读由别人实现的循环时，必须要揣摩编程者的意图。例如，请看下面这个循环：

1
2
for(int i = 0; i < words.size(); i++)
    if(words.get(i).equals("C++")) words.set(i,"Java");

现在将这个循环与一下调用进行比较：

1
Collections.replaceAll(words,"C++","Java");

默认方法Colleciton.removeIf和List.replaceAll稍有复杂。要提供一个lambda表达式来测试或转换元素。例如，下面的代码将删除所有短词，并把其余单词改为小写：

1
2
words.removeIf(w -> w.length() <=3);
words.replaceAll(String::toLowerCase);

9.6.5 批操作

很多操作会“成批”复制或删除元素。以下调用

1
coll1.removeAll(coll2);

将从coll1中删除coll2中出现的所有元素。与之相反，

1
coll1.retainAll(coll2);

会从coll1中删除所有未在coll2中出现的元素。下面是一个典型的应用。

假设希望找出两个集的交集(intersection)，也就是两个集中共有的元素。首先，建立一个新集来存放结果：

1
HashSet<String> result = new HashSet<>(firseSet);

在这里，我们利用了一个事实：每一个集合都有这样一个构造器，其参数是包含初始值的另一个集合。

现在来使用retainAll方法：

1
result.retainAll(secondSet)

这会保留两个集中都出现的所有元素。这样就构成了交集，而无需编写循环。

可以把这个思路更进一步，对视图应用一个批操作。例如，假设有一个映射，将员工ID映射到员工对象，另外有一个不再聘用的所有员工的ID集。

1
2
Map<String,Employee> staffMap = ...;
Set<String> terminatedIDs = ...;

只需要建立一个键集，并删除终止聘用关系的所有员工的ID。

1
staffMap.keySet().removeAll(terminatedIds);

由于键集是映射的一个视图，所以键和相关联的员工名会自动从映射中删除。

通过使用子范围视图，可以把批操作限制在子列表和子集上。例如，假设希望把一个列表的前10个元素增加到另一个容器，可以建立一个子列表选出前10个元素：

1
relocated.addAll(staff.subList(0,10));

这个子范围还可以完成更改操作。

1
staff.subList(0,10).clear();

9.6.6 集合与数组的转换

如果需要把一个数组转换为集合，List.of包装器可以到达这个目的。例如：

1
2
String[] values = ...;
HashSet<> staff = new HashSet<>(List.of(values));

从集合得到数组会更困难一些。当然，可以使用toArray方法：

1
Object[] values = staff.toArray();

不过，这样做的结果是一个对象数组。尽管你知道集合中包含的是一个特定类型的对象，但不能使用强制类型转换：

1
String[] values = (String[]) staff.toArray();//ERROR

toArray方法返回的数组创建为一个Object[]数组，不能改变它的类型。实际上，必须使用toArray方法的一个变体，提供一个指定类型而且长度为0的数组。这样一来，返回的数组就会创建为相同的数组类型。

1
String[] values = staff.toArray(new String[0]);

如果愿意，可以构造一个大小正确的数组：

1
staff.toArray(new String[staff.size()]);

在这种情况下，不会创建新数组。

9.6.7 编写自己的算法

如果编写自己的算法(实际上，或者是以集合作为参数的任何方法)，应该尽可能地使用接口，而不要使用具体的实现。例如，假设你想处理集合元素。当然，可以实现类似下面的方法：

1
2
3
4
5
public void processItems(ArrayList<Item> items)
{
    for(Item item : items)
        do something with item
}

但是，这样会限制方法的调用者，即调用者必须在ArrayList中提供元素。如果这些元素正好在另一个集合中，首先必须对它们重新包装，因此，最好接受一个更加通用的集合。

要问问自己：完成这项工作的最通用的集合接口是什么？你关心顺序吗？如果顺序很重要，就应当接受List。不过，如果顺序不重要，那么可以接受任意类型的集合：

1
2
3
4
5
public void processItems(Collection<Item> items)
{
    for(Item item : items)
        do something with item
}

现在，任何人都可以用ArrayList或LinkedList(甚至用List.of包装器包装的数组)调用这个方法。

反过来，如果你的方法返回多个元素，你肯定不希望限制将来的改进。例如，考虑下面的代码：

1
2
3
4
5
6
public ArrayList<Item> lookupItems(...)
{
    ArrayList<Item> result = new ArrayList<>();
    ...;
    return result;
}

这个方法承诺返回一个ArrayList，尽管调用者并不关心它是什么类型的列表。如果你返回一个List，任何时候都可以通过调用List.of返回一个空列表或单例列表。

9.7 遗留的集合

9.7.1 Hashtable类

经典的Hashtable类与HashMap类的作用一样，实际上，接口也基本相同。与Vector类的方法一样，Hashtable方法也是同步的。如果对与遗留代码的兼容性没有任何要求，就应该使用HashMap。如果需要并发访问，则要使用ConcurrentHashMap。

9.7.2 枚举

遗留的集合使用Enumeration接口遍历元素序列。Enumeration接口有两个方法，即hasMoreElements和nextElement。这两个方法完全类似于Iterator接口的hasNext方法和next方法。

如果发现遗留的类实现了这个接口，可以使用Collections.list将元素收集到一个ArrayList中。例如，LogManager类只是将登录者的名字提供为一个Enumeration。可以如下得到所有登录者的名字：

1
ArrayList<String> loggerNames = Collections.list(LogManager.getLoggerNames());

或者，在Java9中，可以把一个枚举转换为一个迭代器：

1
LogManager.getLoggerNames().asIterator().forEachRemaining(n -> {...});

有时还会遇到遗留的方法希望得到的枚举参数。静态方法Collections.enumeration将产生一个枚举对象，枚举集合中的元素。例如：

1
2
List<InputStream> steams = ...;
SequenceInputStream in = new SequenceInputStream(Collections.enumeration(steams));

9.7.3 属性映射

属性映射(property map)是一个特殊类型的映射结构。他又下面3个特性：

  • 键与值都是字符串
  • 这个映射可以很容易地保存到文件以及从文件加载。
  • 有一个二级表存放默认值

实现属性映射的Java平台类名为Properties。属性映射对于指定程序的配置选项很有用。

例如：

1
2
3
Properties settings = new Properties();
settings.setProprety("width","600.0");
settings.setProprety("filename","/home/cay/cj11/code/v1ch11/raven.html");

可以使用store方法将属性映射列表保存到一个文件中。在这里，我们将属性映射保存在文件program.properties中。第二个参数是包含在这个文件中的注释。

1
2
FileOutStream out = new FileOutStream("program.properties");
settings.store(out,"Program Properties");

9.7.4 栈

1
2
3
E push(E item)//将item压入栈并返回item
E pop()// 弹出并返回栈顶的item。如果栈为空，不要调用这个方法
E peek()//返回栈顶元素，但不弹出。如果栈为空，不要调用这个方法

9.7.5 位集

Jav平台的BitSet类用于存储一个位序列。如果需要高效地存储位序列，就可以使用位集。由于位集将位包装在字节里，所以使用位集要比使用Boolean对象的ArrayList高效得多。

BitSet类提供了一个便于读取、设置或重置各个位得接口。使用这个接口可以避免掩码和其他调整位的操作，如果将位存储在int或long变量中就必须做这些繁琐的操作。

例如，对于一个名为bucketOfBits的BitSet

1
bucketOfBits.get(i)

如果第i位处于“开”状态，就返回true；否则返回flase。类似地

1
bucketOfBits.set(i)

将第i位置为“开”状态。最后，

1
bucketOfBits.clear(i)

将第i位置为“关”状态。

作为位集应用的一个示例，这里给出一个“埃拉托色尼筛选法”算法的实现，这个算法用来查找素数。这并不是查找素数的一种非常好的方法，但是由于某些原因，它已经成为测试编译器性能的一种流行的基准。

这个程序将计算2~2000000之间的所有素数。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package sieve;

import java.util.BitSet;

public class Sieve
{
    public static void main(String[] args) {
        int n = 2000000;
        long start = System.currentTimeMillis();
        BitSet bitSet = new BitSet(n+1);
        int count = 0;
        int i;
        for (i = 2;i <= n;i++)
            bitSet.set(i);
        i = 2;
        while ( i * i <= n)
        {
            if (bitSet.get(i))
            {
                count++;
                int k = 2* i;
                while (k <= n)
                {
                    bitSet.clear(k);
                    k += i;
                }
            }
            i++;
        }
        while (i <= n)
        {
            if (bitSet.get(i)) count++;
            i++;
        }
        long end = System.currentTimeMillis();
        System.out.println(count+"primes");
        System.out.println((end - start) + " milliseconds");
    }
}
Donate comment here