第9章 集合
Java标准库中的集合类，用以数据结构（Data Structures）
9.1 Java集合框架 9.1.1 将集合的接口与实现分离
Java集合类库将接口(interface)与实现(implementation)分离。
例如队伍接口的最简形式可能类似下面这样：
public interface Queue{void add(E element); E remove(); int size();}
这个接口没有说明队伍是如何实现的，每一个实现都可以通过一个实现了Queue接口的类表示
public class CircularArrayQueue implements Queue{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 implements Queue{private int head;private int tail;CircularArrayQueue(int capacity) {...} public void add(E element) { ..、} public E remove() {...} public int size() { ..、} private E[] elements;}
实际上，Java标准类库中没有名为CircularArrayQueue和linkedListQueue的类，这里只是做一个简单的说明，解释一下集合接口和实现在概念上的不同。如果需要一个循环数组队列，就可以使用ArrayDeque类，如果需要的是一个链表队列，就可以直接使用linkedList类，这个类实现了Queue接口
在API文档中，有另外一组名字以Abstract开头的类，例如AbstractQueue，这些类是为类库实现者而设计的。如果要实现自己的队伍类，会发现扩展AbstractQueue类要比实现Queue接口中的方法轻松的多。
9.1.2 Collection接口
Java类库中，集合类的基本接口是Collection接口，这个接口有两个基本方法：
public inteface Collection{boolean add(E element);Iterator iterator();}
add方法用于想集合中添加元素iterator方法用于返回一个实现Iterator接口的对象，可以使用这个迭代器对象依次访问集合中的元素 9.1.3 迭代器
Iterator接口包含4个方法：
public interface Iterator{ E next(); boolean hasNext(); void remove(); default void forEachRemaining(Consumer<? super E> action);}
如果想要查看及恶化中的所有元素，就请求一个迭代器，并在hasNext返回true时反复调用next方法
Collection c = ..、;Iterator iter = c.iterator();while(iter.hasNext()){ String element = iter.next(); // do something with element;}
或者是使用for each循环
for(String eleemnt : c){ // do something with element}
在Java SE 8中，甚至不用写循环，可以调用forEachRemaining方法并提供一个lambda表达式（它会处理一个元素）
iterator.forEachRemaining(element -> do something with element);
Iterator接口的remove方法将会删除上次调用next方法时返回的元素，注意在调用remove之前没有调用next将是不合法的
9.1.4 泛型实用方法
Collection和Iterator都是泛型接口，可以编写操作任何集合类型的实用方法
9.1.5 集合框架中的接口
Java集合框架为不同类型的集合定义了大量接口，如下流程图所示
9.2 具体的集合
Java库中的具体集合，除了以Map结尾的类之外，其他类都实现了Collection接口，而以Map结尾的类实现了Map接口
集合类型 | 描述 | ArrayList一种可以动态增长和缩减的索引序列linkedList一种可以在任何位置进行高效地插入和删除操作的有序序列ArrayDeque一种用循环数组实现的双端队列HashSet一种没有重复元素的无序集合TreeSet一种有序集EnumSet一种包含枚举类型值的集linkedHashSet一种可以记住元素插人次序的集PriorityQueue一种允许高效删除最小元素的集合HashMap一种存储键/值关联的数据结构TreeMap—种键值有序排列的映射表EnumMap一种键值属于枚举类型的映射表linkedHashMap一种可以记住键/值项添加次序的映射表WeakHashMap一种其值无用武之地后可以被垃圾回收器回收的映射表IdentityHashMap一种用=而不是用equals比较键值的映射表9.2.1 链表
在Java程序设计语言中，所有链表实际上都是**双向链接(doubly linked)**的——即每个结点都存放着指向前驱结点的引用。如下代码是Java中使用linkedList添加3个元素之后再将第2个元素删除的代码
List staff = new linkedList<>(); //linkedList implements Liststaff.add("Amy");staff.add("Bob")；staff,add("Carl");Iteratoriter=staff.iterator();String first =iter.next()；//visit first elementString second =iter.next(); //visit second elementiter.remove(); //remove last visited element
如果多次调用add方法，将按照提供的次序将元素添加到链表中。他们被依次添加到迭代器当前位置之前
9.2.2数组列表
ArrayList封装了一个动态再分配的对象数组，可以使用get和set方法随机地访问每个元素
9.2.3 散列集
散列集为每个对象计算一个整数，成为散列码(hash code)
散列码的计算只与散列的对象状态有关，而与散列表中的其他对象无关在Java中，散列表用链表数组实现
package chap9.set;import java.util.*;public class SetTest { public static void main(String[] args) { Set words = new HashSet<>(); long totalTime = 0; try (Scanner in = new Scanner(System.in)) { while (in.hasNext()) { String word = in.next(); long callTime = System.currentTimeMillis(); words.add(word); callTime = System.currentTimeMillis() - callTime; totalTime += callTime; } } Iterator iter = words.iterator(); for (int i = 1; i < 20 && iter.hasNext(); i++) System.out.println(iter.next()); System.out.println("..."); System.out.println(words.size() + " distinct words、" + totalTime + " milliseconds."); }}
9.2.4 树集
TreeSet是一个有序集合(sorted collection)。可以以任意顺序将元素插入到集合中
SortedSet sorter = new TreeSet<>();sorter.add("Bob");sorter.add("Amy");sorted.add("Carl");for(String s : sorted)System.out.println(s);
排序是用树结构完成的(当前实现使用的是红黑树(red-black tree)
要使用树集，必须能够比较元素。这些元素必须实现Comparable接口，或者构造集时必须提供一个Comparator
treeSet/TreeSetTest.java
package chap9.treeSet;import java.util.*;public class TreeSetTest { public static void main(String[] args){ SortedSet- 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); NavigableSet
- sortByDescription = new TreeSet<>(Comparator.comparing(Item::getDescription)); sortByDescription.addAll(parts); System.out.println(sortByDescription); } }
treeSet/Item.java
package chap9.treeSet;import java.util.*;public class Item implements Comparable- { private String description; private int partNumber; public Item(String aDescription, int aPartNumber) { description = aDescription; partNumber = aPartNumber; } public String getDescription() { return description; } public String toString() { return "[description=" + description + ", partNumber=" + partNumber + "]"; } 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; } public int hashCode() { return Objects.hash(description, partNumber); } public int compareTo(Item other) { int diff = Integer.compare(partNumber, other.partNumber); return diff != 0 ? diff : description.compareTo(other.description); }}
9.2.5 队伍和双端队列
队列可以让人们有效地在尾部添加一个元素，在头部删除一个元素
双端队列，可以让人们有效地在头部和尾部同时添加或删除元素
9.2.6 优先级队伍
优先级队列（priority queue)中的元素可以按照任意的顺序插人，却总是按照排序的顺序进行检索
优先级队列使用了一个优雅且高效的数据结构，称为堆(heap)
priorityQueue/PriorityQueueTest.java
package chap9.priorityQueue;import java.util.*;import java.time.*;public class PriotityQueueTest { public static void main(String[] args) { PriorityQueue 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 data : pq) System.out.println(data); System.out.println("Removing elements..."); while (!pq.isEmpty()) System.out.println(pq.remove()); } }
9.3 映射
映射是知道某些键的信息，并想要查找与之对应的元素，用来存放键/值对
9.3.1 基本映射操作
Java类库为映射提供了两个通用的实现
HashMapTreeMap
如果不按照排列顺序访问键，最后选择散列-HashMap
键必须是唯一的，对同一键调用两次put方法，第二个值就会取代第一个值
map/MapTest.java
package chap9.map;import java.util.*;public class MapTest { public static void main(String[] args) { Map staff = new HashMap<>(); staff.put("144-25-5464", new String("AmyLee")); staff.put("567-24-2546",new String("HarryHacker")); staff.put("157-62-7935",new String("CaryCooper")); staff.put("456-62-5527",new String("FrancescaCruz")); //print all entries System.out.println(staff); //remove an entry staff.remove("567-24-2546"); //replace an entry staff.put("456-62-5527",new String("FrancescaHiller")); //look up avalue System.out.println(staff.get("157-62-7935")); //iterate through all entries staff.forEach((k,v)->System.out.println("key=" + k + ", value=" + v)); }}
9.3.2 更新映射项
处理映射的一个难点就是更新映射项，例如统计单次出现的频度
counts.put(word, counts.get(word) + 1);
但是如果单词第一次出现，就会出现NullPointerException异常，一个简单的补救措施是
counts.put(word, counts.getOrDefault(word, 0) + 1);
另一种方法是调用putIfAbsent方法。只有当键原先不存在时才会放入一个值0
counts.putIfAbsent(word, 0);counts.put(word, counts.get(word) + 1);
9.3.3 映射视图
可以通过即可一样使用映射的keySet
Set keys = map.keySet();for(String key : keys){// do something with key}
如果想要同时查看键和值，可以通过枚举条目来避免查找值
for(Map.Entry entry: staff.entrySet()){String k = entry.getKey();Employee v = entry.getValue();// do something with k, v}
9.5 算法
泛型集合接口有一个很大的优点，即算法只需要实现一次。Java类库中的算法虽然没有C++类库的丰富，但是也包含了基本的排序、二分查找等实用算法
9.5.1 排序与混排
Collections类中的sort方法可以对实现了List接口的集合进行排序
List staff = new linkedList<>();// fill collectionCollections.sort(staff);
这个方法假定列表元素实现了Comparable接口。如果想采用其他方式对列表进行排序，可以使用List接口的sort方法并传入一个Comparator对象
staff.sort(Comparator.comparingDouble(Employee::getSalary));
sort方法的实现是直接将所有元素转入一个数组，对数组进行排序，然后，再将排序后的序列复制回列表。
集合类库中使用的排序算法比快速排序要慢一些，快速排序是通用排序算法的传统选择。但是，归并排序有一个主要的优点：稳定，即不需要交换相同的元素。
Collections类有一个算法shuffle,其功能与排序刚好相反，即随机地混排列表中元素的顺序。例如：
ArrayList cards = ...;Collections.shuffle(cards);
shuffle/ShuffleTest.java
package chap9.shuffle;import java.util.*;public class ShuffleTest { public static void main(String[] args) { List numbers = new ArrayList<>(); for(int i = 1; i <= 49; i++) numbers.add(i); Collections.shuffle(numbers); List winningCombination = numbers.subList(0, 6); Collections.sort(winningCombination); System.out.println(winningCombination); } }
9.5.2 二分查找
Collections类的binarySearch方法实现了这个算法。注意，集合必须是排好序的，否则算法将返回错误的答案。如果集合没有采用Comparable接口的compareTo方法进行排序，
i = Collections.binarySearch(c, element);i = Collections.binarySearch(c, element, comparator);
9.5.3 简单算法
在Collections类中包含了几个简单且很有用的算法，例如查找集合中最大元素的示例
9.5.4 批操作
// 删除所有coll2中元素coll1.removeAll(coll2);// 删除所有未在coll2中出现的元素coll1.retainAll(coll2);// 从一个子列表中选出前10个元素relocated.addAll(staff.subList(0, 10))
9.5.5 集合与数组的转换
将数组转换为集合
String[] values = ...;HashSet staff = new HashSet<>(Arrays.asList(values));
从集合中得到数组
Objects[] values = staff.toArray();
但是toArray方法返回的数组是一个Object[]数组，不能改变它的类型，实际上，必须使用toArray方法的一个变体形式
// 提供一个所需类型并且长度为0的数组String[] values = staff.toArray(new String[0]);// 或者构造一个指定大小的数组staff.toArray(new String[staff.size()]);
9.5.6 编写自己的算法
如果编写自己的算法（实际上，是以集合作为参数的任何方法)，应该尽可能地使用接口，而不要使用具体的实现
9.6 遗留的集合 9.6.1 Hashtable类
Hashtable类与HashMap类的作用一样，实际上，它们拥有相同的接口。与Vector类的方法一样。Hashtable的方法也是同步的。如果对同步性或与遗留代码的兼容性没有任何要求，就应该使用HashMap。如果需要并发访问，则要使用ConcurrentHashMap
9.6.2 枚举
遗留集合使用Enumeration接口对元素序列进行遍历，Enumeration接口有两个方法，即hasMoreElements和nextElement
Enumeration e = staff.elements();while(e.hasMoreElements()){ Employee e = e.nextElement(); // ...}
9.6.3 属性映射
属性映射是一个类型非常特殊的映射结构，有以下三个特性
键与值都是字符串表可以保存到一个文件中，也可以从文件中加载使用一个默认的辅助表
实现属性映射的Java平台类成为Properties
属性映射通常用于程序的特殊配置选项
9.6.4 栈
Stack是从Java 1.0版开始就包含在标准类库中的，以下是Stack的几个常用的方法
Stack stack = new Stack();// pushStack.push(1);Stack.push(2);// popSystem.out.println(stack.pop())// peekSystem.out.println(stack.peek())// isEmptySystem.out.println(stack.isEmpty())
9.6.5 位集
BitSet类提供了一个便于读取、设置或清除各个位的接口
// 获取第i位状态，处于"开"，返回true，否则，返回falsebucketOfBits.get(i);// 将第i位置为"开"bucketOfBits.set(i);// 将第i位置为"关"bucketOfBits.clear(i);