7 集合

1. Java 集合框架

1) 集合接口与实现分离

下面用队列(queue) 说明集合接口与实现分离。

Queue 接口指出可以在队尾添加元素、在队头删除元素（先进先出），并且可以查找队列中元素的序号。

public interface Queue<E> {
    void add(E element);
    E remove();
    int size();
}

Queue 并未说明队列的实现方式，通常有循环数组与链表两种实现方式，它们都可以用一个实现了 Queue 的类表示。

// 循环数组实现
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[] elements;
}
 
// 链表实现 
public class LinkedListQueue<E> implements Queue<E> {
    private Link head;
    private Link tail;
    
    LinkedListQueue() {}
    
    public void add(E element) {}
    public E remove() {}
    public int size() {}
}

某种程度上，循环数组比链表更高效，不过它是一个有界(bounded) 集合，容量有限。

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

2) `Collection` 接口

Java 类库中，集合类的基本接口为 Collection 接口。

public interface Collection<E> {
    boolean add(E element);
    Iterator<E> iterator();
    // ...
}

add()：向集合中添加元素，如果添加成功返回 true，否则返回 false，例如试图向集(set) 中添加一个已存在的对象时将返回 false，因为集中不允许有重复对象。

iterator()：返回一个实现了 Iterator 接口 的对象（迭代器），用于依次访问集合中的元素。

3) 迭代器

public interface Iterator<E> {
    E next();
    boolean hasNext();
    void remove();
    default void forEachRemaining(Consumer<? super E> action);
}

next()：访问迭代器的下一个位置上的元素，到达末尾时再次调用将抛出 NoSuchElementException，因此每次调用前需调用 hasNext() 检查。

要访问集合中的元素，可以构建一个迭代器 iter，当 hasNext() 返回 true 时反复调用 iter.next()。

Collection<String> c = // ...
Iterator<String> iter = c.iterator();
while (iter.hasNext()) {
    String element = iter.next();
    // ...
}

可以将 while 改为 for-each：

for (String element : c) { }

编译器自动将 for-each 转换为一个带迭代器的循环。

for-each 可以处理任何实现了 Iterable 接口 的类对象。

public interface Iterable<E> {
    Iterator<E> iterator();
}

Collection 扩展自 Iterable，因此 for-each 可以用于标准库的所有集合对象。

可以将循环改写为调用 forEachRemaining() 并提供一个 lambda。

iterator.forEachRemaining(element -> ... )

remove()：删除上次访问的元素，remove() 需在调用 next() 之后调用，连续调用 remove() 非法。

it.remove();
it.remove(); // 抛出 IllegalStateException

4) 泛型实用方法

Collection 与 Iterator 都为泛型接口，可以自己编写处理集合的方法，例如，检测某个集合中是否有指定元素：

public static <E> boolean contains(Collection<E> c, Object obj) {
    for (E element : c) {
        if (element.equals(obj)) return true;
    }
    return false;
}

Collection 声明了很多抽象方法，要求每个实现 Colletion 的类都实现全部方法将非常烦琐，所以 Java 类库中有一个 AbstractCollection 类，其中保持 size() 与 iterator() 为抽象，其他方法则已有默认实现，具体集合类可以继承 AbstractCollection。

2. 集合框架中的接口

集合的两个基本接口为 Collection、Map。

List 是一个有序集合，元素将添加到容器中的特定位置，可以采用两种方式访问元素，迭代器或整数索引，前者只能按顺序访问元素，后者则可以按任意顺序。

void add(int index, E element)
void remove(int index)
E get(int index)
E set(int index, E element)

ListIterator 接口 是 Iterator 的子接口，其中的 add() 用于在迭代器位置之前增加元素。

Set 接口 等同于 Collection，不过其方法的行为更加严谨，例如，add() 不允许增加重复元素。

SortedSet 接口 与 SortedMap 接口 提供用于排序的 Comparator 对象。

NavigableSet 接口 与 NavigableMap 接口 包含额外的用于搜索和遍历有序集合和映射的方法，它们由 TreeSet 类与 TreeMap 类实现。

3. 具体集合

Java 类库中的集合及其用途见 P386 表 9-1

除了 *Map 类实现 Map 外，其他类都实现 Collection。

结构	有序	修改开销	访问速度
链表	是	小	慢
数组列表
散列集	否	小	快
树集	是	中
队列	是

1) 链表 `LinkedList`

数组的缺陷在于每次删除元素时都要平移部分元素，开销很大，而链表(linked list) 能解决此问题。

数组在连续的存储位置上存放对象引用，而链表则将各个对象存放在单独的链接(link) 中，且每个链接中存放序列中下一个链接的引用。链表是一个有序集合，每个对象的位置很重要。Java 中链表是双向链接的，即链接还存有上一个链接的引用。

LinkedList::add：将对象添加到链表尾部。

从链表中删除元素的开销很小，只需更改其前后邻的链接引用即可。

var staff = new LinkedList<String>();
staff.add("Amy");
staff.add("Bob");
staff.add("Carl");
Iterator<String> iter = staff.iterator();
String first = iter.next();
String second = iter.next();
iter.remove(); // 删除上次访问的元素, 即第 2 个元素

只能对有序集合使用迭代器添加元素，例如，集(set) 是无序的，因此 add() 没有在 Iterator 中声明，而是在其子接口 ListIterator 中声明。

interface ListIterator<E> extends Iterator<E> {
    void add(E element);
    E previous();
    boolean hasPrevious();
    // ...
}

与 Collection::add 不同，ListIterator::add 假定操作总会成功，因此不返回 boolean。

与 next() 相同，previous() 将迭代器向前移动，并返回越过的对象。

add() 添加元素的位置只与迭代器的位置有关（在迭代器的当前位置）；而 remove() 将删除上一个访问的元素，所以其删除的元素还与迭代器的状态有关：

在调用 next() 后调用 remove()，将删除迭代器当前位置左侧的元素。
在调用 previous() 后调用 remove()，将删除迭代器当前位置右侧的元素。

set() 对元素的选择规则与 remove() 相同，不过它将选中元素替换为指定的新值。

如果有两个迭代器，当其中一个在遍历集合时、另一个在修改集合，那么很可能出现混乱。

List<String> list = // ...
ListIterator<String> iter1 = list.listIterator();
ListIterator<String> iter2 = list.listIterator();
iter1.next();
iter1.remove();
iter2.next(); // 抛出 ConcurrentModificationException

为了避免此异常，可以为一个集合关联多个只读迭代器，或者仅为其关联一个读写迭代器。

迭代器检测异常的原理是，每个迭代器都有一个自己的修改计数器，集合有一个总的修改计数器，如果某个迭代器的修改次数与集合的总修改次数不同，就会抛出异常。例外是，此计数器只计入结构性修改（add() 和 remove()），而set不被视为结构性修改，所以所有迭代器都可以调用 set() 来修改集合的内容，许多算法都依赖于此例外。

Collection 还声明了很多其他方法，它们大部分由 LinkedList 的父类 AbstractCollection 实现，例如：

toString() 对所有元素调用 toString() 并生成一个长字符串。
contains() 检测链表中是否存在指定元素，例如，如果 list 中存在元素 "Harry"，调用 list.contains("Harry") 将返回 true。

nextIndex()：返回下一次调用 next() 时返回的元素的索引。

previousIndex()：返回下一次调用 previous() 时返回的元素的索引。

访问链表的第 n 个元素时，只能从头开始、越过前 n - 1 个元素，没有捷径可走，效率非常低，如需按索引访问元素，通常不选择链表。

2) 数组列表 `ArrayList`

P396

3) 散列集 `HashSet`

数组与链表中的元素有序排列，如需查找某个特定元素，而其位置未知，则需遍历所有元素，时间开销较大。如果不在意元素的顺序，还有几种数据结构按照对自己最方便的顺序组织元素，它们不允许指定元素位置，但是查找元素耗时很短。

散列表(hash table) 为每个对象计算其散列值，它实现为链表数组，每个链接称为桶(bucket)。

查找某个元素时，计算其散列值，对桶的总数取余，即为该元素的桶索引（例如，某对象散列值为 76268，共有 128 个桶，那么该对象保存在 76268%128 = 108 号桶中）。

添加元素时，目标桶可能已经存在元素，称为 散列冲突(hash collision)，此时将新对象与原有对象进行比较（设计 hashCode() 时应选择合理的算法使不同对象的散列码尽可能分散）。

如果大致知道元素总数，可以设置桶数，通常设置为预计元素总数的 75%~150%。标准类库中的实现限定桶数为 2 的幂，默认为 16，提供的值将被调整为 2 的下一个幂。

散列表爆满时，需要 再散列(rehash)，原理是创建一个桶数为原先 2 倍的新链表，转移元素后删除旧链表。装填因子(load factor) 决定何时进行再散列，例如，如果装填因子为 0.75（默认值），当链表填充 75% 以上时将自动进行再散列。

散列表可以实现很多重要数据结构，其中一个为集，它是没有重复的元素集合，其 add() 在添加元素前先进行搜索，不存在时才会添加。

class SetTest {
    public static void main(String[] args) {
        PrintWriter out = new PrintWriter(System.out);
        Set<String> words = new HashSet<>();
        long time = 0;
        Path path = Paths.get("D:\\test.txt");
        
        try (Scanner in = new Scanner(path)) {
            while (in.hasNext()) {
                String word = in.next();
                long callTime = System.currentTimeMillis();
                words.add(word);
                callTime = System.currentTimeMillis() - callTime;
                time += callTime;
            }
        }
        catch (IOException e) {
            throw new RuntimeException(e);
        }
        
        Iterator<String> iter = words.iterator();
        for (int i = 1; i <= 20 && iter.hasNext(); i++) out.println(iter.next());
        out.println("...");
        out.println(words.size() + " distinct words. " + time + " milliseconds.");
        out.flush();
        out.close();
    }
}

4) 树集 `TreeSet`

树集(TreeSet) 类似于散列集，不过它是一个有序集合，可以按任意顺序将元素插入集合，遍历时，值将按照自动排列后的顺序出现。

TreeSet<String> sorter = new TreeSet<>();
sorter.add("Carl");
sorter.add("Amy");
sorter.add("Bob");
for (String s : sorter) System.out.println(s);
// "Amy"
// "Bob"
// "Carl"

排序是用一个树数据结构实现的（当前实现使用 红黑树(red-black tree)）。将元素添加到树中比添加到散列表中慢，不过与检查数组或链表中的重复元素相比还是快很多，其时间复杂度为 $O (lo g_{2} n)$ ，例如，对包含 1000 个元素的树，添加元素前平均需要比较 10 次。

要使用树集，必须能够比较元素，它们必须实现 Comparable，或者必须在构造集时提供一个 Comparator。

HashSet 与 TreeSet 的选择取决于要收集的数据，如果不需要数据有序，就没有必要付出排序的开销，更重要的是，对于某些数据，对其进行排序比给出一个散列算法更困难，后者只需将数据适当地打乱存放，而前者必须精确地区分各个对象。

class TreeSetTest {
    public static void main(String[] args) {
        Set<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);
    }
}
 
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 description;
    }
    
    @Override
    public String toString() {
        return "[description=" + description + ", partNumber=" + partNumber + "]";
    }
    
    @Override
    public boolean equals(Object otherObject) {
        if (this == otherObject) return true;
        if (otherObject == null) return false;
        if (getClass() != otherObject.getClass()) return false;
        Item other = (Item) otherObject;
        return Objects.equals(description, other.description) && partNumber == other.partNumber;
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(description, partNumber);
    }
    
    @Override
    public int compareTo(Item other) {
        int diff = Integer.compare(partNumber, other.partNumber);
        return diff != 0 ? diff : description.compareTo(other.description);
    }
}

5) 队列与双端队列 `Queue` / `Deque`

队列(queue) 可以在队尾添加元素、在队头删除元素，双端队列(deque, double-ended queue) 在队头与队尾都可以添加和删除元素。队列中间不能添加元素。

Deque 接口由 ArrayDeque 类与 LinkedList 实现，它们都可以提供双端队列，其大小可以根据需要扩展，12 章详细介绍。

6) 优先队列 `PriorityQueue`

优先队列(priority queue) 中的元素可以按任意顺序插入，获取时则按一定顺序，调用 remove() 时总会获得当前的最小元素。

优先队列并没有对元素排序，而是使用了堆(heap) 数据结构，后者是一个自组织的二叉树，其 add() 与 remove() 操作会将最小的元素移动至根，而不必花时间排序。

类似于 TreeSet，PriorityQueue 的元素也需要实现 Comparable，或者在构造时提供一个 Comparator。

PriorityQueue 的典型用法为任务调度，每个任务有一个优先级，任务以随机顺序添加到队列中，每次启动一个新任务时将从中删除优先级最高的任务（习惯上将1作为最高优先级）。

class PriorityQueueTest {
    public static void main(String[] args) {
        Queue<LocalDate> pq = new PriorityQueue<>();
        pq.add(LocalDate.of(1906, 12, 9));
        pq.add(LocalDate.of(1815, 12, 10));
        pq.add(LocalDate.of(1903, 12, 3));
        pq.add(LocalDate.of(1910, 6, 22));
        
        System.out.println("Iterating over elements...");
        for (LocalDate date : pq) System.out.println(date);
        System.out.println("Removing elements...");
        while (!pq.isEmpty()) System.out.println(pq.remove());
    }
}

Iterating over elements...
1815-12-10
1906-12-09
1903-12-03
1910-06-22
Removing elements...
1815-12-10
1903-12-03
1906-12-09
1910-06-22

4. 映射

集可以快速查找元素，但要求准确对应，有时查找元素时并不知道其准确副本，只知道与其关联的关键信息，映射(map) 数据结构就是为此设计的。

映射用来存放键/值对，提供键可以查找值，例如，存储一个员工记录表，键为员工 ID，值为 Employee 对象。

1) 基本映射操作

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

HashMap 对键进行散列，散列函数与比较函数只能应用于键，不能对值进行散列或比较。

TreeMap 根据键的顺序将它们组织为一个搜索树。

类似于 HashSet 与 TreeSet，HashMap 与 TreeMap 的选择取决于要收集的数据，如果不需要数据有序，可以优先选择 HashMap。

Map<String, Employee> staff = new HashMap<>();
Employee harry = new Employee("Harry Hacker");
staff.put("987-98-9996", harry);
 
String id = "987-98-9996";
Employee e = staff.get(id);

一个键只能对应一个值，如果对同一个键两次调用 put()，新值将覆盖旧值。

如果映射中没有存储与指定键对应的值，调用 get() 将返回 1，这可能不太方便，对于此情况可以调用 getOrDefault()，指定一个默认返回值。

Employee e = staff.getOrDefault(id, 0);

remove()：从映射中删除对应于指定键的值。

size()：返回总值数。

forEach()：迭代处理映射中的键与值，可以提供一个接收键与值的 lambda，映射中的每一项将依次调用此 lambda。

staff.forEach((k, v) -> System.out.println("key=" + k + ", value=" + v));

class MapTest {
    public static void main(String[] args) {
        Map<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"));
        System.out.println(staff);
        
        staff.remove("567-24-2546");
        staff.put("456-62-5527", new Employee("Francesca Cruz"));
        System.out.println(staff.get("157-62-7935"));
        staff.forEach((k, v) -> System.out.println("key=" + k + ", value=" + v));
    }
}

2) 更新映射条目

例如，使用映射统计一个单词在文本中出现的次数，读取到指定单词时计数器 +1：

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

不过，第一次读取到 word 时调用 get(word) 将返回 null，抛出 NullPointerException。

一种简单的补救措施是调用 getOrDefault()：

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

另一种方式是调用 putIfAbsent()，只有当键原先不存在或映射到 null 时才放入一个值：

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

merge()：可以简化此操作，如果键原先不存在，此调用：

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

将 word 对应的 value 置 1，否则调用 Integer::sum 将原值与指定值 1 相加作为新值。

3) 映射视图

映射的视图(view) 是实现了 Collection 或其子接口的对象，有 3 种视图，键集、值集、键/值对集，它们分别由以下方法返回：

Set<K> keySet()
Collection<V> values()
Set<Map.Entry<K, V>> entrySet()

keySet 是实现了 Set 的另外一个类的对象。

如需同时查看键与值，可以通过枚举映射条目避免查找值：

for (Map.Entry<String, Employee> entry : staff.entrySet()) {
    String k = entry.getKey();
    Employee v = entry.getValue();
    // ...
}

通过 var 可以避免 Map.Entry：

for (var entry : staff.entrySet())

或者调用 forEach()：

map.forEach((k, v) ->{
    // ...
});

4) 弱散列映射 `WeakHashMap`

P411

5) 链接散列集与映射

LinkedHashSet 与 LinkedHashMap 将记住插入元素的顺序，避免看上去随机的顺序。

Map<String, Employee> staff = new LinkedHashMap<>();
staff.put("001", new Employee("001"));
// ...
Iterator<String> iterByKeySet = staff.keySet().iterator();
Iterator<Employee> iterByValues = staff.values().iterator();

迭代时，除了按插入顺序，还可以按访问顺序，每次调用 get() 或 put() 时，受影响的条目将从当前位置移至条目链表的末尾（只影响条目链表中的位置，而不影响散列表的桶），如下构造：

LinkedHashMap<K, V>(*initialCapacity, *loadFactor, true);

实现“最近最常使用”时（例如将最近访问频率高的元素放在内存中、访问频率低的元素由数据库读取），访问顺序很重要，例如，在映射表满时删除前几个元素，也即最近最少使用的元素。

要自动完成此过程，可以构造 LinkedHashMap 的一个子类，覆盖 removeEldestEntry()：

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

当其返回 true 时，添加新元素将删除 eldest。

Map<K, V> cache = new LinkedHashMap<K, V>(128, 0.75F, true) {
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > 100;
    }
};

6) 枚举集与映射 `EnumSet` / `EnumMap`

EnumSet 的元素为枚举类型，由于枚举类型的实例数量有限，EnumSet 在内部实现为一个位序列，如果对应的值包含在其中，该位置值为 1。

enum Weekday { };
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 接口的常用方法。

EnumMap 的键为枚举类型，可以简单高效地实现为一个值数组。

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

7) 标识散列映射 `IdentityHashMap`

IdentityHashMap 中，键的散列值不由 hashCode() 计算，而由 System::identityHashCode 计算，Object::hashCode 也调用了后者。

比较对象时，IdentityHashMap 使用 == 而非 equals，也就是说，不同键对象即使内容相同，也被视为不同对象。

实现对象遍历算法时，如需跟踪已经遍历过的对象，可以使用 IdentityHashMap。

5. 副本与视图

通过视图(view)可以得到其他实现了 Collection 或 Map 的类对象，上文的 keySet() 返回一个实现了 Set 的类对象，后者的方法可以操纵原映射，这种集合就是视图。

1) 小集合

List<String> names = List.of("Peter", "Paul", "Mary");
Set<Integer> numbers = Set.of(2, 3, 5);
Map<String, Integer> scores = Map.of("Peter", 2, "Paul", 3, "Mary", 5);

List 与 Set 接口有 11 个 of()，分别接收 0 至 10 个参数，另有一个参数个数可变的 of()。

Map 接口无法提供参数个数可变的方法（因为参数需交替为键 / 值），它有一个静态方法 ofEntries()，接收任意数量的 Map.Entry<K, V> 对象。

import static java.util.Map.*;
 
Map<String, Integer> scores = ofEntries(
    entry("Peter", 2),
    entry("Paul", 3),
    entry("Mary", 5)
);

这些集合对象是不可修改的(unmodifiable)，尝试修改将产生 UnsupportedOperationException。

如需一个可修改的集合，可以将不可修改的集合传递给构造器：

List<String> names = new ArrayList<>(List.of("Peter", "Paul", "Mary"));

调用 Collections.nCopies(*n, *anObject) 给人一种错觉，好像有 n 个元素、每个元素是一个 anObject，但实际上，该对象只存储一次。

List<String> settings = Collections.nCopies(100, "DEFAULT");

将创建一个包含 100 个字符串 "DEFAULT" 的 List，不过该对象只存储一次，存储开销很小。

2) 不可修改的副本和视图

copyOf()：创建一个集合的不可修改副本(unmodifiable copy)。

List<String> names = // ...
Set<String> nameSet = Set.copyOf(names);
List<String> nameList = List.copyOf(names);

修改原集合时，其副本不受影响。

如果原集合不可修改，且副本与之类型相同，则会直接返回原集合。

Collections 类还有一些方法用于生成集合的不可修改的视图(unmodifiable view)：

Collections.unmodifiableCollection
Collections.unmodifiableList
Collections.unmodifiableSet
Collections.unmodifiableSortedSet
Collections.unmodifiableNavigableSet
Collections.unmodifiableMap
Collections.unmodifiableSortedMap
Collections.unmodifiableNavigableMap

与副本不同，原集合变化时，视图将同步变化。

lookAt()：读取集合的内容，但不修改。

List<String> staff = new LinkedList<>();
// ...
lookAt(Collections.unmodifiableList(staff));

可以通过 lookAt() 调用 List 的所有方法，而不只是访问器，但是所有的更改器方法已经重定义为抛出 UnsupportedOperationException。

由于视图只是包装了接口而不是具体的集合对象，所以只能访问接口中定义的方法，例如，LinkedList 有一些便利方法如 addFirst() 与 addLast()，但它们没有在 List 接口中定义，不能通过不可修改的视图访问。

3) 子范围

可以为很多集合建立子范围(subrange)视图，例如，假设有一个 List 为 staff，要从中取出第 10 至 19 个元素，可以使用 subList()：

List<Employee> subStaff = staff.subList(10, 20);

对子范围进行的所有操作将同步到整个集合。

对于有序集与映射，可以使用顺序排序而不是元素位置建立子范围，例如，sortedSet 接口声明的方法有：

SortedSet<E> subSet(E from, E to)
SortedSet<E> headSet(E to)
SortedSet<E> tailSet(E from)

SortedMap 也有类似方法：

SortedMap<K, V> subMap(K from, K to)
SortedMap<K, V> headMap(K to)
SortedMap<K, V> tailMap(K from)

NavigableSet 允许对子范围有更多控制，例如，指定是否包含边界：

NavigableSet<E> subSet(E from, boolean fromInclusive, E to, boolean toInclusive)
NavigableSet<E> headSet(E to, boolean toInclusive)
NavigableSet<E> tailSet(E from, boolean fromInclusive)

4) 检查型视图

将错误类型的元素混入泛型集合中的情况很常见：

List<String> strings = new ArrayList<>();
ArrayList rawList = strings; // WARNING, 无 ERROR
rawList.add(new Date()); // 一个 Date 类对象混入 ArrayList<String>

检查型视图可以探测此类问题，如下定义一个安全的 List：

List<String> safeStrings = Collections.checkedList(strings, String.class);

该视图的 add() 将检查插入的对象是否属于给定类，如果不是，则立即抛出 ClassCastException：

List rawList = safeStrings;
rawList.add(new Date()); // ClassCastException

5) 同步视图

如果从多个线程访问同一个集合，必须确保集合不会被意外破坏。类库设计者使用视图机制（而不是线程安全的集合类）来保证集合的线程安全性。

Collections::synchronizedMap：将任何 Map 转换成有同步访问方法的 Map。

Map<String, Employee> map = Collections.synchronizedMap(new HashMap<>());

6. 算法

1) 泛型算法的优点

泛型集合接口的优点是算法只需实现一次，例如，实现 max() 返回集合中的最大元素，传统实现是循环：

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];
}

如果集合是 ArrayList，还需要调用 get()；如果是 LinkedList，还需通过迭代器调用 next()。为每种集合编写自己的 max() 将极其繁琐。

此时可以使用集合接口，将 max() 实现为能够接收任何实现了 Collection 的类对象。

public static <T extends Comparable> T max(Collection<T> c) {
    if (c.isEmpty()) throw new NoSuchElementException();
    Iterator<T> iter = c.iterator();
    T max = iter.next();
    while (iter.hasNext()) {
        T next = iter.next();
        if (max.compareTo(next) < 0) max = next;
    }
    return max;
}

现在，max() 适用于数组、ArrayList、LinkedList 等一切集合。

2) 排序与混排

Collections::sort：对实现了 List 的集合排序。

List<String> staff = new LinkedList<>();
// ...
Collections.sort(staff);

sort() 假定列表元素是实现了 Comparable 的类对象，如需使用其他依据排序，可以使用 List 接口的 sort() 并传入一个 Comparator 对象：

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

如需降序排序，可以使用静态方法 Collections::reverseOrder，它将返回一个 Comparator，后者将返回 *b.compareTo(*a)：

staff.sort(Comparator.reverseOrder());

类似地，可以指定排序依据：

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

数组的排序算法通常采用随机访问，但链表的随机访问效率很低，对链表通常使用归并排序，而 Java 将所有元素存入一个数组，对数组排序后将序列复制到链表。

所有接收集合参数的方法必须描述何时能够安全地将集合传递给算法（例如，显然不能将 unmodifiableList 传递给 sort()），根据文档，List 必须为可修改的，而不限定可以改变大小，如果 List 支持——

set()，称为可修改的。
add() 和 remove()，称为可改变大小的。

Collections::shuffle：随机打乱 List 中元素的顺序。

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

3) 二分查找

Collections::binarySearch：对有序集合（需实现 List）进行二分查找（如果传入无序集合，将返回错误答案）。

除了集合与目标元素外，如果集合没有采用 Comparable::compareTo 排序，还需提供一个 Comparator：

*target = Collections.binarySearch(*c, *element);
*target = Collections.binarySearch(*c, *element, *comparator);

如果返回值非负，表示目标元素在有序状态下的索引，c.get(i) 即为 target；如果返回值为负，表示没有匹配到目标元素，不过可以利用返回值计算应该将目标元素插入到何处：记返回值为 i，则目标元素应该插入 -i - 1 处。

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

向 binarySearch() 传递一个 LinkedList 没有意义，因为链表只能按顺序访问。

4) 简单算法

Collections 中的简单算法见 P428-429 API 注释

5) 批操作

很多操作将成批复制 / 删除元素，例如，从 coll1 中删除 coll2 中出现的所有元素：

coll1.removeAll(coll2);

或从 coll1 中删除 coll2 中没有出现的所有元素：

coll1.retainAll(coll2);

利用 retainAll() 获取两个 Set 的交集(intersection)：

建立一个新 Set 存放结果

Set<String> result = new HashSet<>(*firstSet);

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

调用 retainAll()

result.retainAll(*secondSet);

可以更进一步，对视图应用批操作，例如，假设有一个 Map staff，另有一个 Set 包含不再聘用的员工 ID：

Map<String, Employee> staff = // ...
Set<String> terminatedIDs = // ...

只需建立一个键集，删除不再聘用的员工：

staff.keySet().removeAll(terminatedIDs);

由于键集是 Map 的一个视图，所以键以及与之关联的对象将自动从 Map 中删除。

6) 集合与数组的转换

包装器 List.of：将数组转换为集合。

String[] names = // ...
List<String> staff = List.of(names);

将集合转换为数组则较为困难，可以调用 toArray()：

Object[] names = staff.toArray();

不过，toArray() 只能返回一个 Object 数组，虽然其中的对象均为 String，但不能强制转换：

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

需要将 toArray() 传入一个数组构造器表达式，这样返回的数组才有正确的类型：

String[] names = staff.toArray(String[]::new);

JDK 11 之前，需写为：

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

或者重用原数组（而不构造新数组）：

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

7) 编写自己的算法

如需自定义算法，应尽可能使用接口（而不是具体实现），例如，如需对集合元素进行某种处理，当然可以实现为：

public void processItems(ArrayList<Item> items) {
    for (Item item : items) {
        // 处理 item
    }
}

但是，这样将方法调用者限制为必须提供一个 ArrayList，如果元素在另一种集合中，则需先对其重新包装。所以，最好编写更加通用的方法。

要先思考，最大的通用集合接口是什么，如果顺序很重要，应该接收 List，如果不重要，则可以接收 Collection：

public void processItems(Collection<Item> items) {
    for (Item item : items) {
        // 处理 item
    }
}

甚至可以更好，改为接收一个 Iterable<Item>（Collection 继承自Iterable）：

public void processItems(Iterable<Item> items) {
    for (Item item : items) {
        // 处理 item
    }
}

如果方法返回多个元素，例如：

public ArrayList<Item> lookupItems() {
    List<Item> result = new ArrayList<Item>();
    // ...
    return result;
}

可以改为返回一个 List，这样，任何时候都可以增加一个分支，通过调用 List.of 返回一个空 List 或单例。

7. 遗留的集合

P432-440

EmberNecrono

Explorer