Java 集合框架

集合（有时称为容器）只是将多个元素组合成一个单元的对象。集合用于存储、检索、操作和通信聚合数据。

集合框架

集合框架是用于表示和操作集合的统一架构。所有集合框架都包含以下内容：

• 接口：这些是代表集合的抽象数据类型。接口允许独立于其表示的细节来操作集合。在面向对象的语言中，接口通常形成层次结构。
• 实现：这些是集合接口的具体实现。本质上，它们是可重用的数据结构。
• 算法：这些是对实现集合接口的对象执行有用计算的方法，例如搜索和排序。这些算法被称为是多态的：也就是说，相同的方法可以用于适当集合接口的许多不同实现。本质上，算法是可重用的功能。

除了 Java 集合框架，集合框架最著名的例子是 C++ 标准模板库 (STL) 和 Smalltalk 的集合层次结构。

• Collection 集合层次结构的根。集合表示一组称为元素的对象。接口是所有集合实现的Collection最小公分母，用于传递集合并在需要最大通用性时操纵它们。某些类型的集合允许重复元素，而另一些则不允许。有些是有序的，有些是无序的。Java 平台不提供此接口的任何直接实现，但提供更具体的子接口的实现，例如Set和List。

• Set— 不能包含重复元素的集合。该接口对数学集合抽象进行建模，并用于表示集合，例如构成扑克手的卡片、构成学生日程安排的课程或在机器上运行的进程。

• List— 有序集合（有时称为序列）。Lists 可以包含重复的元素。用户List通常可以精确控制每个元素在列表中的插入位置，并且可以通过它们的整数索引（位置）访问元素。如果你用过Vector，你就会熟悉它的一般味道List。

• Queue— 在处理之前用于保存多个元素的集合。除了基本Collection操作之外，Queue还提供了额外的插入、提取和检查操作。 队列通常但不一定以 FIFO（先进先出）方式对元素进行排序。例外情况是优先级队列，它根据提供的比较器或元素的自然顺序对元素进行排序。无论使用何种顺序，队列的头部都是将通过调用removeor删除的元素poll。在 FIFO 队列中，所有新元素都插入到队列的尾部。其他类型的队列可能使用不同的放置规则。每个Queue实现都必须指定其排序属性。

• Deque— 在处理之前用于保存多个元素的集合。除了基本Collection操作之外，Deque还提供了额外的插入、提取和检查操作。 双端队列可以用作 FIFO（先进先出）和 LIFO（后进先出）。在双端队列中，所有新元素都可以在两端插入、检索和删除。

• Map— 将键映射到值的对象。Map不能包含重复的键；每个键最多可以映射到一个值。如果您使用过Hashtable，那么您已经熟悉Map.

最后两个核心集合接口仅仅是Set和的排序版本Map：

• SortedSet— Set以升序保持其元素。提供了几个额外的操作来利用排序。排序集用于自然排序集，例如单词列表和会员卷。
• SortedMap— Map按升序键顺序维护其映射。这是 的Map类比SortedSet。排序映射用于键/值对的自然排序集合，例如字典和电话簿。

List

AbstractList, AbstractSequentialList, ArrayList, AttributeList, CopyOnWriteArrayList, LinkedList, RoleList, RoleUnresolvedList, Stack, Vector

List 是有序的 Collection（有时称为序列）。列表可能包含重复的元素。除了继承自 Collection 的操作外，该 List 接口还包括以下操作：

• Positional access 根据元素在列表中的数字位置操作元素。这包括诸如get、 set、add、addAll 和 remove 等方法。
• Search 在列表中搜索指定对象并返回其数字位置。搜索方法包括 indexOf 和 lastIndexOf。
• Iteration 扩展 Iterator 语义以利用列表的顺序性。这些 listIterator 方法提供了这种行为。
• Range-view 该 sublist 方法对 List 执行任意范围操作。

Java 平台包含两个通用 List 实现。 以及在某些情况下提供更好的性能的 LinkedList。

Set

AbstractSet, ConcurrentHashMap.KeySetView, ConcurrentSkipListSet, CopyOnWriteArraySet, EnumSet, HashSet, JobStateReasons, LinkedHashSet, TreeSet

Set 是不能包含重复元素的 Collection。它对数学集合抽象进行建模。该 Set 接口仅包含继承自的方法，Collection 并添加了禁止重复元素的限制。Set 也添加了更强的契约在 equals 与 hashCode 操作上，即使实例的实现类型不同，也可以进行有意义的比较。如果两个实例包含相同的元素，则它们是相等的。

Java 平台包含三个通用Set实现：HashSet、TreeSet 和 LinkedHashSet。 HashSet，它将其元素存储在哈希表中，是性能最好的实现；但是它不保证迭代的顺序。 TreeSet，它将元素存储在红黑树中，根据元素的值对其元素进行排序；它比 HashSet 慢得多。 LinkedHashSet，它被实现为一个带有链表的哈希表，它根据元素插入集合的顺序（插入顺序）对其元素进行排序。

Queue 队列

AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue, SynchronousQueue

Queue 用于在处理之前保存元素的集合。除了基本Collection操作之外，队列还提供额外的插入、删除和检查操作。

队列通常但不一定以 FIFO（先进先出）方式对元素进行排序。例外情况是优先级队列，它根据元素的值对元素进行排序。无论使用什么排序，队列的头部都是通过调用remove 或 poll删除的元素。在 FIFO 队列中，所有新元素都插入到队列的尾部。其他类型的队列可能使用不同的放置规则。每个Queue实现都必须指定其排序属性。

一个Queue实现可以限制它所拥有的元素的数量；这样的队列被称为有界的。java.util.concurrent 中的一些 Queue 实现是有界的，但 java.util 中的实现不是。

Deque 双端队列

ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList

双端队列是元素的线性集合，支持在两个端点插入和删除元素。该 Deque 接口是一种比 Stack，Queue 两者都更丰富的抽象数据类型因为它同时实现了堆栈和队列。

Summary of Deque methods

BlockingQueue 阻塞队列

ArrayBlockingQueue , DelayQueue , LinkedBlockingDeque , LinkedBlockingQueue , LinkedTransferQueue , PriorityBlockingQueue , SynchronousQueue

BlockingQueue 实现主要用于生产者-消费者队列，但另外支持Collection接口。因此，例如，可以使用 . 从队列中删除任意元素 remove(x)。但是，此类操作通常 不会非常有效地执行，并且仅用于偶尔使用，例如当取消排队的消息时。

BlockingQueue 实现是线程安全的。所有排队方法都使用内部锁或其他形式的并发控制以原子方式实现其效果。

BlockingQueue 本质上不支持任何类型的“关闭”或“关闭”操作来指示不会添加更多项目。此类功能的需求和使用往往取决于实现。

Summary of BlockingQueue methods

 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

class Producer implements Runnable {
   private final BlockingQueue queue;
   Producer(BlockingQueue q) { queue = q; }
   public void run() {
     try {
       while (true) { queue.put(produce()); }
     } catch (InterruptedException ex) { ... handle ...}
   }
   Object produce() { ... }
 }

 class Consumer implements Runnable {
   private final BlockingQueue queue;
   Consumer(BlockingQueue q) { queue = q; }
   public void run() {
     try {
       while (true) { consume(queue.take()); }
     } catch (InterruptedException ex) { ... handle ...}
   }
   void consume(Object x) { ... }
 }

 class Setup {
   void main() {
     BlockingQueue q = new SomeQueueImplementation();
     Producer p = new Producer(q);
     Consumer c1 = new Consumer(q);
     Consumer c2 = new Consumer(q);
     new Thread(p).start();
     new Thread(c1).start();
     new Thread(c2).start();
   }
 }

内存一致性效果：与其他并发集合一样，线程中的操作在将对象放入 BlockingQueue 之前的操作之前发生在BlockingQueue从另一个线程中 访问或删除该元素之后的操作。

Map

多态算法

Java 平台提供的可重用功能。它们都来自 Collections类，并且都采用静态方法的形式，其第一个参数是要对其执行操作的集合。Java 平台提供的绝大多数算法都在 List实例上运行，但也有少数算法在任意 Collection实例上运行。

排序 Sorting

• 根据元素的 natural ordering 排序
• 根据传递 Comparator 排序

 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

    public static <T> void sort(T[] a, Comparator<? super T> c) {
        if (c == null) {
            sort(a);
        } else {
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, c);
            else
                TimSort.sort(a, 0, a.length, c, null, 0, 0);
        }
    }

public class Sort {
    public static void main(String[] args) {
        List<String> list = Arrays.asList(args);
        Collections.sort(list);
        System.out.println(list);
    }
}


// Sort anagram groups according to size
Collections.sort(winners, new Comparator<List<String>>() {
    public int compare(List<String> o1, List<String> o2) {
        return o2.size() - o1.size();
    }});

1

java Sort i walk the line

洗牌 Shuffling

该算法在实现机会游戏时很有用。例如，它可以用来洗牌代表一副牌List的对象。Card此外，它对于生成测试用例也很有用。

 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

//java.util.Collections#shuffle
public static void shuffle(List<?> list)
public static void shuffle(List<?> list, Random rnd) {
        int size = list.size();
        if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
            for (int i=size; i>1; i--)
                swap(list, i-1, rnd.nextInt(i));
        } else {
            Object[] arr = list.toArray();

            // Shuffle array
            for (int i=size; i>1; i--)
                swap(arr, i-1, rnd.nextInt(i));

            // Dump array back into list
            // instead of using a raw type here, it's possible to capture
            // the wildcard but it will require a call to a supplementary
            // private method
            ListIterator it = list.listIterator();
            for (int i=0; i<arr.length; i++) {
                it.next();
                it.set(arr[i]);
            }
        }
    }   

常用数据操作

• reverse 反转 List 中元素的顺序。
• fillList 用指定的值覆盖 List 中的每个元素。此操作对于重新初始化 List 很有用。
• copy 接受两个参数，一个目标List和一个源List，并将源的元素复制到目标，覆盖其内容。目标List必须至少与源一样长。如果它更长，则目标List中的其余元素不受影响。
• swap— 交换 List 中指定位置的元素。
• addAll— 将所有指定元素添加到 Collection。 要添加的元素可以单独指定，也可以作为数组指定。

搜索 Searching

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

    public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }
       public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
        if (c==null)
            return binarySearch((List<? extends Comparable<? super T>>) list, key);

        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key, c);
        else
            return Collections.iteratorBinarySearch(list, key, c);
    }

构成 Composition

• frequency 计算指定元素在指定集合中出现的次数
• disjoint 确定两个Collections是否不相交；也就是说，它们是否不包含共同的元素

寻找极值

1
2
3
4

public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll){}
public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) {}
public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) {}
public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) {}

附录

• https://docs.oracle.com/javase/tutorial/collections/index.html
• https://docs.oracle.com/javase/tutorial/collections/interfaces/index.html