Java-7-类集框架

在 java 中，Java API 为我们实现了一些基本的数据结构以及相关的算法，这一篇，将复习这些数据结构的组织关系，重点方法。

A. 类集框架总览

类集框架（collections Framework）在 Java 中的接口，类之间的继承、实现关系如下图所示：

Java 提供类集框架使得工程师不需要重复实现相关的数据结构，此外，一些常见的算法、数据操作（e.g. sort，shuffle，rotate) 在 Java API 中都做了实现，使得我们不再需要重复 造轮子（reinvent the wheel）。

a. 接口关系简介

如上图中，各个具体的框架都实现了 Collection 接口。这一接口中，Java 规定了一些最为基础、公共的方法，例如 add(), remove(), clear(), size(), isEmpty() 等。实现 Collection 接口的为三种具体数据结构的接口：list, set, queue.

List 接口描述的是一种顺序存储结构，它有两个实现类，ArrayList 和 LinkedList。二者的底层实现方法不同（一个底层是可变数组，一个底层是双向链表），一般情况下，我们比较常使用 ArrayList。（两个 list 其他小不同：ArrayList 实现了 RandomAccess 接口（a tagging interface，没有具体方法），而 LinkedList 不实现该接口）。

Set 接口不同于 List，元素不用存储在特定位置，并且不允许复制元素。

Queue 为队列，是一种特殊的顺序存储结构，只允许在尾部插入，头部移除元素。Dueue 是队列的升级版，允许在两端进行元素增删。

b. 注意点

集合接口 为泛型类，使用 类型变量 E 表示传入其中的 element：Collection<E>, List<E>。对于 Map<K, V> 接口，k 表示 Key 的类型，V 表示 value 的类型。

声明 集合类型的时候尽量使用范围大的类型来声明，例如：

List<String> words = new ArrayList<>();

一般的，Collection, List, Map 作为类型名即可，不推荐过度细化（for portability,可移植性）。

B. 迭代器（Iterators）

每一个集合都会提供一个遍历方法， Collection 接口的 超接口 Iterable<T> 定义了 Iterator<T> iterator() 方法，用于遍历集合。

下面通过代码展示 使用 Iterator 来对集合进行元素的遍历和增删操作。

遍历

// 使用 iterator 的 hasNext(), next(), 方法，遍历集合
Collection<String> coll = ...;
Iterator<String> iter = coll.iterator();
while(iter.hasNext()){
    String element = iter.next();
    ...//do sth
}

// 对于实现了 Iterator<E> 接口的类的对象，可以使用增强型 for 循环来遍历
for(String element : coll){
    ...// do sth
}

元素增删

// remove() 方法
while(iter.hasNext()){
    String element = iter.next();
    if(element fullfills the condition)
        iter.remove();  //注意remove的是 iter 最后一次操作返回的元素，也就是上面的 element
}
// removeIf() 方法
coll.removeIf(e -> e fullfills the conditions)

// 增加元素，add(), 设置元素，set() - 为 ListIterator 接口的方法
// add(), set(), 都是改变 iterator 前面的元素
List<String> friends = new LinkedList<>();
ListIterator<String> iter = friends.listIterator();
iter.add("Fred");   // Fred | 
iter.add("Wilma");  //Fred Wilma| 
iter.previous();    // Fred | Wilma
iter.set("Barney");     // Fred| Barney

C. 典型集合

a. Sets

Set 可以方便的判断一个元素是否在集合中，但是它不会记住元素的顺序信息。

Set 有两个实现类， HashSet 和 TreeSet, 分别是根据 利用 hash表 和 二叉树 进行实现。

一般的使用 Set 来存储及判断元素是否在 Set 中 (contains() 方法), 使用 HashSet 效率高。

如果需要 Set 有一定的顺序性，使用 TreeSet。它可以按照一定的顺序遍历整个 Set, TreeSet 中的元素需要实现 Comparable 接口，或者在新建 TreeSet 实例的时候，在构造函数中传入 Comparator。TreeSet 类实现了 SortedSet 和 NavigableSet 接口，可以进行一些 元素的排列、有序增删操作。

b. Maps

Maps 存储 keys 与 values 之间的关系（associations），向 Maps 中添加元素以及根据 keys 查询 values 如下所示：

// 添加，修改元素 put(), add()
// 两个方法不同之处在于返回值，
// put(): 返回更新前与key值对应的value，如果无，返回 null
// add(): 返回boolean 值，如果添加的值原先不存在返回 ture。
Map<String, Integer> counts = new HashMap<>();
counts.put("Alice",1);   
counts.add("Alice",2);  

// 查询，get(), getOrDefault()
int count = counts.get("Alice");    //查询，不推荐这么写！！
// 如果没有对应的 键，返回 null，在 unbox 的时候会引起 NullPointerException 异常
int count = counts.getOrDefault("Alice",0);    //推荐写法.
// 如果有 “Alice”，返回对应值，否则返回0

// 修改元素 merge()
counts.merge(word, 1, Integer::sum);    //更新元素
// 如果 word 不存在，添加 word 键与 值 1
// 如果 word 存在，word 的值 加一 Integer::sum

此外，可以通过下面的方法获得 Maps 的 views。

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

利用 views，我们可以遍历 Map 中的元素。例子如下：

for(Map.Entry<String, Integer> entry : counts.entrySet()){
    String k = entry.getKey();
    Integer v = entry.getValue();
    ...// 处理 k，v 值
}

// 一个更加简洁的遍历方法 	forEach(BiConsumer<? super K,? super V> action)（Java8 onwards）
counts.forEach((k.v) -> {
    ...// 处理 k，v 值
});

需要注意的是，views 并不会复制 Map 中的内容，只是建立一个连接到 Map 中的引用。如果对 View 中的元素进行操作，Map 中的元素也会发生变化。

此外，LinkedHashMap 可以实现 Map 中元素带有规定的顺序，在 遍历时可以按照 规定好的顺序进行输出。

c. 栈、队列

栈(stack)是一种只允许 在一端（栈顶）添加 删除元素的数据结构，队列(queue)是允许在一端（队尾 tail）添加元素，另一端（队首 head）移除元素的结构，双向队列（double-queue）则允许在 两端 添加或者移除元素。

在 Java 中，Queue 和 Deque 接口定义了 这些数据结构的操作方法。（注意没有 Stack 接口，有一个比较 老的 Stack 类，但是不推荐使用）。如果不关心 线程安全性，可以使用 ArrayDeque 类 来实现 stack 以及 queue, 例子如下：

// 实现 stack， 添加删除元素 使用 push() 和 pop() 方法
ArrayDeque<String> stack = new ArrayDeque<>();
stack.push("Peter");   
stack.push("Paul");
while(!stack.isEmpty())
    System.out.println(stack.pop());

// 实现 queue， 添加删除元素使用 add() 和 remove() 方法
Queue<String> queue = new ArrayDeque<>();
queue.add("Peter");
queue.add("Paul");
while(!queue.isEmpty())
    System.out.println(queue.remove());

PriorityQueue: 是一个类，实现了 Queue 接口。它在添加（add）元素的时候随意添加，在 移除元素的时候，会按照一定的优先级顺序进行 移除（remove）（最先移除 queue 中最小的元素）。

向 PriorityQueue 中添加的元素需要实现 Comparable 接口，或者在构造 PriorityQueue 对象的时候，需要传入一个 Comparator。

应用场景例如 可以向任务池中随意添加任务，但是处理任务时，按照任务的优先级 进行处理。

d. 其他常用类

Properties 类

Properties 类实现了 Map 接口，他可以非常容易的以纯文本的形式 存储及加载配置信息。一个例子如下：

// 配置信息 写入文件
Properties settings = new Properties();
settings.put("width", "200");
settings.put("title", "Hello world!");
try(OutputStream out = Files.newOuputSream(path)){
    settings.store(out, "Program Properties");
}

// 从文件读取配置信息
try(InputStream in = Files.newInputStream(path)){
    settings.load(in);
}

// 读取配置信息
String title = settings.getProperty("title", "New document");
// 读取 title 中的值，如果没有该 键，则添加该键并且写入 值 "New document"。

此外，可以通过 System.getProperties() 方法获取系统的配置信息。

BitSet 与 枚举Sets/Maps

BitSet 的作用是存储 一系列的 位信息，它可以将位信息 打包放置在 一个数组或者 long 型的数值中, 且可以非常方便的 读取、设置 特定的位。相比 boolean 数组，他的存储效率更高。

可用于 存储一系列 的标志位（flags）。

需要注意的是，BitSet 类不是 一个集合类 - 没有实现 Collection<Integer> 接口。

如果存储在 Set 和 Map（key值） 中的内容为 枚举内容，则推荐使用 EnumSet 类 和 EnumMap 类。

WeakHashMap

WeakHashMap 可以优化 Map 资源的利用。对于一般的 Map 对象，如果 Map 对象仍然在活动，Map 对象的所有 条目（Entries）都会处于活动中，而不会被 GC 回收。

WeakHashMap 使用 weak references 来控制 Map 中的 key 值，如果在程序中，除了 Map 之外，其他地方不再使用某个 key 值，则程序中仅存在对 该 entry 的 WeakReference ，GC 则会回收该 key 以及对应的 value。WeakReference 对象则被存放在一个特定的队列中，如果需要再次调用，则从该队列中寻找，然后重新在程序中生成对象。

D. 集合类的静态构造法 及 视图(Views)

a. 构造集合的静态方法

List, set, Map 接口提供了静态方法 of() 来生成集合对象，例子如下：

List<String> names = List.of("Peter", "Paul", "Mary");
Set<Integer> numbers = set.of(1,2,3);
Map<String, Integer> scores = Map.of("Peter", 2, "Paul", 3);
// Map 额外的方法，传入 使用静态方法 entry() 生成的 Entry<K, V> 对象
Map<String, Integer> scores = ofEntries(
    entry("Peter", 2),
    entry("Paul", 3);
)

需要注意的是，使用 of() 方法生成的 对象 都是不可以修改的，此外，还有 Arrays.asList() 方法，可以生成元素可修改，但大小不可修改的 list 对象。

如果想利用 of() 方法生成可以修改的 集合对象，如下：

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

b. 视图(views)

集合的 view 提供了一个用于访问原集合中所有对象的集合，它实现了 Collection 接口，但是并不存储任何元素，所有对 view 的操作，会直接反映到原集合上。

我们可以利用 集合对象的 实例方法 subList(), tailList(), headList()（set, map 也有类似方法）生成 view。具体的，subList() 截取一个子串，包含第一个边界量，不包含第二个边界量（也就是集合 左包右不包，$[..)$）, headSet 得到一个子集合，只有上边界；tailSet 得到一个子集合，只有下边界。看一些例子：

List<String> sentence = ...;
// 返回第 5 到 第9个 元素的 view
List<String> nextFive = sentence.subList(5,10); 

此外，我们还可以通过 Collections 的静态方法 Collections.unmodifiableList 获得集合的只读 view，例子如下：

public class Person{
    private ArrayList<Person> friends;
    public List<Person> getFriends(){
        return Collections.unmodifiableList(friends);
    }
}