Java 的集合框架
集合
用于存储和管理数据的实体被称为数据结构（data structure）。数据结构可用于实现具有不同特性的集合对象，这里所说的集合对象可以看作一类用于存储数据的特殊对象。
集合内部可以采用某种数据结构（数组或链表）来保存元素。例如 ArrayList 就采用数组作为内部数据结构。TreeSet 则使用了二叉搜索树（binary search tree）作为内部数据结构。
Java 语言中提供了很多有用的集合类型。这些内置的集合类统称为 Java 集合框架（Java Collections Framework, JCF）。常用的集合类型包括：
- 线性表（list）：一组有序元素的集合，可以使用整数索引或者顺序来访问其中的元素。
- 栈（stack）：具备后入先出特性的集合。
- 队列（queue）：具备先入先出特性的集合。
- 数学集合（set）：一组没有重复元素的集合。
- 映射（map）：一组存放（键，值）对的集合，其中每一个健都对应着一个值。
java.util 包中提供了 Collection 接口的定义，每一个集合类型（Map 除外）都需要实现这个接口。Collection 接口定义了大多数集合类型支持的方法。
| 方法 | 描述 |
|---|---|
| add(element) | 向当前集合添加指定的新元素 |
| addAll(collection) | 将指定集合中的所有元素添加到当前集合中 |
| clear() | 删除当前集合中的所有元素 |
| contains(element) | 如果当前集合包含指定的元素，则返回真（true） |
| containsAll(collection) | 如果当前集合包含指定集合中的所有元素，则返回真（true） |
| isEmpty() | 如果当前集合不包含任何元素，则返回真（true） |
| iterator() | 返回一个可以用来遍历当前集合元素的对象 |
| remove(element) | 如果当前集合包含指定的元素，则将其删除 |
| removeAll(collection) | 删除当前集合中与指定集合所含元素相同的元素 |
| retain(collection) | 删除当前集合中与指定集合所含元素不同的元素 |
| size() | 返回当前集合中元素的个数 |
| toArray() | 返回一个包含当前集合所有元素的数组 |
ArrayList 与 LinkedList
ArrayList 底层是一个 Object[]，是一个非线程安全的集合。Java 集合 ArrayList 原理及使用 这篇博客描述的比较详细，可以参考。
当我们 add(element)一个元素的时候，ArrayList 会自动扩容，并且把元素保存到集合的尾部。
从列表 remove(element)删除一个元素时，需要将该元素的所有后续元素向前移动一个位置。
了解了 ArrayList 的工作原理后，发现有些情况下，不适合使用 ArrayList 集合。例如，我们编写一段程序用于删除某个字符串列表中的每一个长度为偶数的元素。程序如下：
1 | public ArrayList<String> removeEvenLength(ArrayList<String> list) { |
我们来分析一下上面这段代码。注意注释的那段话，每次删除元素的时候，该元素后续的所有元素都要向前移动一位。所以这段代码虽然可以得到正确的结果，但是每次删除数据都会消耗很多时间用在移动元素的操作上。当集合元素少的时候看不出什么差距，但是如果集合中有包含几万几十万的元素时，那所浪费的时间也是巨大的。
根据上述情况，需要更高效的处理在列表头部或者中间进行大量的插入或者删除操作，可以使用另一种 LinkenList（链表）的集合类型。
链表（linked list）是一种集合类型，它将元素存储在节点中，而所有节点又连城一条链。
使用链表的主要优点是可以快速地在链表头部插入元素。在链表中插入新元素时不需要像数组那样移动其他的元素，只需要创建一个新的节点对象，并将其链入链表即可。
说了这么多，还不是为了使刚刚那个例子更高效的执行？但是使用 LinkedList 就会比 ArrayList 更高效了么？
首先我们要清楚一点，ArrayList 数组集合，可以高效的随机（根据索引位置）访问或者修改元素。但是链表不具备随机访问的特性。因为链表中的每个元素都存储在一个独立的节点中，而且通常只保留指向第一个节点的指针，所以不可能很快速的定位任意一个元素的位置。
当我们使用链表提供的 add、remove、set、get 等方法时，这些方法内部会创建一个指向链表第一个元素的临时指针。然后使用这个指针遍历整个链表，直到找到需要的元素位置。链表本身不会保存上次访问元素的位置，找到一个元素之后，再去找另一个元素的时候（使用上述几个方法），指针只能再次从头部开始。
上述例子使用了 ArrayList 删除集合中长度为偶数的字符串的方法，我们知道了 ArrayList 的执行效率不高。如果仅仅使用 LinkedList 替换 ArrayList 来完成同样的工作，我们会发现 LinkedList 所花费的时间开销仍然很大。因为它很多次的调用了 get 和 remove 方法。
1 | public LinkedList<String> removeEvenLength(LinkedList<String> list) { |
如果我们需要顺序访问链表中的每个元素，可以使用更高效的访问方法，通过一个特殊的迭代器（iterator）对象，可以在遍历过程中始终保留指针位置。
迭代器 允许用户以顺序的方式高效率地访问链表中每个元素的一种特殊对象。
使用迭代器可以简化遍历元素的过程，使我们在访问元素时不必每次都从链表的头部开始以逐个节点的方式移动到所需位置。
| 方法 | 描述 |
|---|---|
| hasNext() | 如果列表中还存在其他元素，则返回真（true） |
| next() | 返回列表中的下一个元素，并将迭代器当前位置前移一个位置 |
| remove() | 删除由上一次 next()方法所返回的元素 |
所以上述方法可以修改为：
1 | public LinkedList<String> removeEvenLength2(LinkedList<String> list) { |
Java 中 for-each 循环的实现也采用了迭代器，如果像下面一样使用 for-each 时，实际上也是通过迭代器来访问每一个元素的：
1 | for (String element : list) { |
总结
| 集合类 | 特点 |
| ArrayList | 1. 随机访问：可以快速访问每一个元素 | 2. 可以快速地在列表的结尾处添加或删除元素 |
| LinkedList | 1. 可以快速地在列表的开头或结尾处添加或删除元素 |
| 2. 通过迭代器进行顺序访问过程中可以快速地在当前位置添加或者删除元素 | |
| 3. 不会像数组那样出现空间已满的情况 | |
| 4. 很容易实现队列 |
LinkedList 类案例分析：筛法
要找出某个给定数字内的所有素数。素数是只能被 1 和它本身整除的一类特殊数字。数字 2 是最小的素数。
埃拉托塞尼筛法 是一个经典的素数发现算法。
算法思路
筛法开始时创建两个列表：一个用于存放所有待检查的数字，另一个用于存放已经发现的素数。数字：[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25]
素数：[]- 将数字列表中的第一个元素删除，并添加到素数列表中。
- 算法将数字列表中是该素数的整数倍的所有整数删除。
- 从数字列表的头部获得的元素可以保证是素数。
分析
在第一轮筛法中，2 是第一个从数字列表中选出的数字，所以要把 2 放到素数列表中，并把数字列表中 2 和所有 2 的倍数删除。这一轮过后，数字列表中的第一个元素变为数字 3。在算法的下一轮中，3 又会被放到素数列表中，同时删除数字列表中所有 3 的倍数，以此类推。数字：[3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]
素数：[2]数字：[5, 7, 11, 13, 17, 19, 23, 25]
素数：[2, 3]数字：[7, 11, 13, 17, 19, 23]
素数：[2, 3, 5]使用 LinkedList 来实现筛法
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
41public static void main(String[] args) {
// 数字列表
List<Integer> numbers = new LinkedList<>();
// 素数列表
List<Integer> primes = new LinkedList<>();
// 生成一个数字列表
for (int i = 2; i <= 25; i++) {
numbers.add(i);
}
System.out.println(" 数字列表 " + numbers);
System.out.println(" 素数列表 " + primes);
// 当数字列表不为空时，则一直计算
while (!numbers.isEmpty()) {
// 数字列表中的第一个数字
int firstNumber = numbers.remove(0);
// 添加到素数列表中
primes.add(firstNumber);
// JDK1.8 可以使用该方法
// numbers.removeIf(currentNumber -> currentNumber % firstNumber == 0);
// 使用迭代器
Iterator<Integer> iterator = numbers.iterator();
while (iterator.hasNext()) {
// 获得数字中的下一个数字
int currentNumber = iterator.next();
// 删除数字列表中第一个数字的倍数
if (currentNumber % firstNumber == 0) {
iterator.remove();
}
}
}
System.out.println(" 数字列表 " + numbers);
System.out.println(" 素数列表 " + primes);
}输出结果
1
2
3
4数字列表 [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
素数列表 []
数字列表 []
素数列表[2, 3, 5, 7, 11, 13, 17, 19, 23]
数学集合
快速查找元素和高效防止重复元素
数学集合 存储一系列没有重复的元素的集合
无论是链表还是数组都会面临一个主要的问题：查找操作执行的效率不高。一般来说，如果需要在一个列表中查找一些特定的元素，就必须逐个检查所有的元素是否满足条件，对于一个很大的列表来说，这会花费很长时间。
列表的另一个不足之处在于它不能轻易的阻止重复元素的加入。当你希望集合中没有重复元素并且能够从集合中很快速的找到某个特定的元素时，最好选用另一种抽象数据类型：数学集合（set）。
HashSet
Set 接口提供了 Collection 接口所定义的全部操作（如 add、contains、remove 等），通常情况下，Set 类型的这些操作会有更高的效率。在 Java 集合框架中，有两个实现了 Set 接口的具体数学集合类：HashSet 和 TreeSet。
无与伦比的查询速度是 Set 集合类型的最大优点之一。回想 ArrayList 或者 LinkedList 类型的 contains 方法，它们都需要逐个检查列表中的每一个元素，直到发现匹配的元素位置。但是在 HashSet 类中，contains 方法只需要检查集合中的一个元素就可以操作完成。
在 HashSet 的内部实现方法中使用了一种称为 散列表 （hash table）的特殊数组，散列表会根据一个特殊的整数—— 散列码（hash code）来决定该元素在数组中的存储位置。（每一个 Java 对象都会有一个独一无二的散列码，可以通过 hashCode 方法查看）所以它是一种可以高效的添加、删除和查找元素的集合类型。HashSet 的缺点体现在其中保存的元素没有特定的顺序。
HashSet 类有一个非常方便的构造函数允许通过一个现有的集合类型来构造一个数学集合，该函数会将现有的集合中所有不重复的元素加入数据集合中。
1 | List<String> list = new LinkedList<>(); |
输出结果
1 | LinkedList: [aaa, bbb, ccc, bbb, aaa] |
TreeSet
TreeSet 中的元素以有序的方式保存在 二叉搜索树（binary seach tree）中，二叉搜索树是一种用链接方式组织元素的数据结构。TreeSet 同样可以以高效地进行添加、删除和查找操作，不过相对于 HashSet 还是要慢一些。但是如果需要以一定的顺序操作 Set 中的元素，那还是应该选择 TreeSet。
TreeSet 可以用来保护具有自然顺序（顺序关系）的数据类型这点表明 TreeSet 中的元素可以是实现了 Comparable 接口的任意类型，例如 Integer 或 String 类。其他操作与 HashSet 类似。
总结
| 集合类 | 特点 |
| HashSet | 1. add、contains 和 remove 方法非常高效 | 2. 其中的元素可以是任何类型 |
| TreeSet | 1. 其中的元素按一定的顺序保存 |
| 2. 其中的元素必须可以比较（比如 Integer 或 String） |
数学集合上的运算
| 集合运算 | 方法 | 描述 |
|---|---|---|
| 并集 | addAll | 包含在 A 或 B，或者同时包含在 A 和 B 中的所有元素集合 |
| 交集 | retainAll | 同时包含在 A 和 B 中的元素的集合 |
| 差集 | removeAll | 包含在 A 中，但是不包含在 B 中的元素的集合 |
| 超集或子集 | containsAll | 如果 A 是 B 的一个超集（包含 B 的所有元素）就反回 true |
映射
抽象数据类型映射（map）也是一种集合，其中保存的元素都是具有某种单向关联关系的对象组。
映射 将值对象（value）和键对象（key）关联起来的一种集合。
一个键只能映射到一个具体的值。但是却允许多个不同的键映射到同一个值。可以将映射理解为两个相互关联的集合：一个保存键的数学集合（set）和一个由每个键对应的值组成的集合（collection）。
HashMap 与 TreeMap
Java 集合框架中有两个实现了 Map 接口的类：HashMap与TreeMap。这两个类的命名与数学集合类的命名类似，因为它们内部实现非常相似。HashMap 是一种更为通用的映射；TreeMap 能够以有序的方式存放可以比较大小的键对象。
HashMap 的执行效率比 TreeMap 略高一些，并且可以存储各种类型的数据。但却无法控制其中键对象的顺序。TreeMap 只能保存可以比较大小的数据对象（例如 Integer 或 String 类，有自己的比较器），而且执行效率稍低一些，但它独一无二的优势在于能使键对象按照某种顺序排列。
| 方法 | 描述 |
|---|---|
| clear() | 删除 map 中的所有键和值对象 |
| containsKey(key) | 如果给定的键对象在 map 中映射了某个值对象就返回 true |
| containsValue(value) | 如果给定的值对象在 map 中被某些键对象映射就返回 true |
| get(key) | 返回与给定键对象关联的值对象，如果找不到则返回 null |
| isEmpty() | 如果 map 中不包含任何键和值对象则返回 true |
| keySet() | 返回包含 map 中所有键对象组成的数学集合（Set） |
| put(key, value) | 将给定的键和值对象加入 Map 中 |
| putAll(map) | 将给定 map 中的所有键值对加入当前 Map 中 |
| remove(key) | 删除 map 中给定键对象及其所关联的值对象 |
| size() | 返回 map 中已经建立的键值对的个数 |
| values() | 返回 map 中所有值的集合（Collection） |
映射视图（KeySet 和 values）
与其他集合对象不同，map 类型没有 iterator 方法。因为 map 不知道用户想要遍历的内容是什么。但是，map 类提供了一对方法：keySet 和 values。两者分别返回由散列表中所有键对象所构成的数学集合（Set）和包含所有值对象的集合（Collection）。这两个返回的集合一般被称为 map 的集合视图（collection view）。
集合综述
抽象数据类型（abstract data type, ADT） 对某种数据类型以及该类型允许的各种操作的一个规定。
列表、数学集合与映射的比较
| ADT | 实现 | 描述 / 特点 | 缺点 |
|---|---|---|---|
| List | ArrayList, LinkedList | 一组按照插入顺序排列的元素 | 查询速度慢，在任意位置插入、删除元素也很慢 |
| Set | HashSet, TreeSet | 一组各不相同的元素，查询速度快 | 没有索引；不能随机访问任意元素 |
| Map | HashMap, TreeMap | 一组键 和 值的关联 | 通用性不好；不能反向从值获得对应的键 |
参考文章：
《Java 程序设计教程 第三版》
微信
支付宝
