# 第九章 集合 ## 9.1 Java集合框架 ### 9.1.1 集合接口与实现分离 队列接口最简单实现 ``` public interface Queue<E> {     void add(E element);     E remove();     int size(); } ``` 队列有两种实现方式，一种是循环数组，另一种是链表 ``` 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; } ``` ### 9.1.2 Collection 接口 ``` public interface Collection<E> {     boolean add(E element);     Iterator<E> iterator; } ``` 集合中不允许有重复对象 所以若添加对象已存在则add方法返回false ### 9.1.3 迭代器 ``` public interface Iterator<E> {     E next();     boolean hasNext();//调用next()前使用hasnext检查是否有下一个     void remove();     default void forEachRemaining(Consumer<? super E> ction); } ``` 也可以使用foreach进行循环 编译器自动转换为带有迭代器的循环 ``` for(String element:c) {     //do something with element; } ``` Java迭代器位于两个元素之间，当调用next时，迭代器就越过下一个元素，并返回刚刚越过的那个元素的引用。 Iterator接口的remove方法将会删除上次调用next方法时返回的元素。调用remove之前没有调用next将是不合法的，会抛出异常。 ### 9.1.4 泛型实用方法 Java类库提供了一个类AbstractCollection，它保持基础方法size和iterator仍为抽象方法。 具体集合类可以扩展AbstractCollection类。由具体集合类提供iterator方法，contain方法由AbstractCollection超类提供 ## 9.2 集合框架中的接口 集合有两个基本接口：Collection和Map 使用boolean add(E element) 映射使用V put(K key,V value)添加键值对 迭代器必须顺序访问元素 Set接口等同于Collection接口，Set的add方法不允许添加重复元素，两个集包含相同元素即相同，不在乎顺序。 ## 9.3 具体集合 ### 9.3.1 链表 链表基于普通数组删除和插入元素开销大的原因（移动元素） 在Java中，链表都是双向链表 ``` 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(); ``` ListIterator提供了反向遍历链表的方法 ``` E previous(); boolean hasPrevious() ``` 与next方法一样，previous返回越过的对象 不能使用同时具有读写功能的两个迭代器 LinkedList提供访问某个特定元素的get方法，效率不高（每次从头开始） 可以使用System.out.println(a)//打印链表a所有元素 ### LinkedList.java ``` package javaSX.linkedList;
import java.util.*;
public class LinkedListTest {     public static void main(String[] args) {         var a = new LinkedList<String>();         a.add("Amy");         a.add("Bob");         a.add("Carl");
        var b = new LinkedList<String>();         b.add("Daivd");         b.add("Ethan");         b.add("Frank");         b.add("Gaussian");
        ListIterator<String> aIter = a.listIterator();         Iterator<String> bIter = b.iterator();
        while (bIter.hasNext()) {// merge from b to a             if (aIter.hasNext())                 aIter.next();             aIter.add(bIter.next());         }         System.out.println(a);         bIter = b.iterator();         while (bIter.hasNext()) {             bIter.next();             if (bIter.hasNext()) {                 bIter.next();                 bIter.remove();// remove every second word in b             }         }         System.out.println(b);         a.removeAll(b);         // remove all words in b from a         // 从a中删除b中的所有单词         System.out.println(a);     } } ``` ### 9.3.3 散列集 不在意元素存储顺序，快速查找元素，这就是散列表，散列表为每一个对象计算一个整数（散列码）。散列表用链表数组实现 ### SetTest.java ``` package javaSX.set;
import java.util.*;
public class SetTest {// print all unique words in System.in     public static void main(String[] args) {         var words = new HashSet<String>();         long totalTime = 0;         try (var 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<String> 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 + "mill seconds");     } } ``` ### 9.3.4 树集 树集是一个有序集合，使用红黑树完成。 将一个元素添加到树中比添加到散列表中慢，但是与检查数组或链表中的重复元素相比，使用树会快很多。使用树集的元素必须实现Comparable接口。
下面的程序创建了Item对象的两个树集，第一个按照部件编号排序，第二个使用一个定制的比较器按照描述信息排序。 ### TreeSetTest.java ``` package javaSX.treeSet;
import java.util.*;
public class TreeSetTest {     public static void main(String[] args) {         var parts = new TreeSet<Item>();         parts.add(new Item("Toaster", 24));         parts.add(new Item("widget", 13));         parts.add(new Item("modem", 2411));         System.out.println(parts);// 默认按照部件编号排序         var sortByDescription = new TreeSet<Item>(Comparator.comparing(Item::getDescription));// 按照描述信息排序
        sortByDescription.addAll(parts);         System.out.println(sortByDescription);     } } ``` ### Item.java ``` package javaSX.treeSet;
import java.util.Objects;
public class Item implements Comparable<Item> {     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;         var 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.3.5 队列与双端队列 Java6中引入了Deque接口，ArrayDeque和LinkedList类实现了这个接口，可以提供双端队列。 ### 9.3.6 优先队列 优先队列元素可以按任意顺序插入，但会按有序顺序检索。意味着调用remove，总会获得最小元素。优先队列使用堆来实现。 ### PriorityQueueTest.java ``` package javaSX.priorityQueue;
import java.util.*; import java.time.*;
public class PriorityQueueTest {     public static void main(String[] args) {         var pq = new PriorityQueue<LocalDate>();         pq.add(LocalDate.of(1906, 12, 9));         pq.add(LocalDate.of(1815, 1, 9));         pq.add(LocalDate.of(1920, 12, 19));         pq.add(LocalDate.of(1916, 2, 11));
        System.out.println("Iterating over elements....");         for (LocalDate date : pq) {             System.out.println(date);         }         System.out.println("Removeing elements...");         while (!pq.isEmpty())             System.out.println(pq.remove());     } } ``` ## 9.4 映射 存放键值对 ### 9.4.1 基本映射操作 ``` var staff=new HashMap<String,Employee>(); staff.put("123",new Employee("Amy")); staff.remove("123"); staff.forEach((k,v)->System.out.println("key="+k+",value="+v)); getorDefault()//有则取值，无则为默认值 ``` ### 9.4.3 映射视图 可以枚举一个映射的所有键 ``` Set<String> keys=map.keySet(); for(String key:keys) {     ... } ``` 使用以下代码查看键和值 ``` for(Map.Entry<String,Employee> entry:staff.entrySet()) {     String k=entry.getKey();     Employee v=entry.getValue();     ... } ``` 不能向键值视图添加元素 ### 9.4.4 弱散列映射 WeakHashMap使用弱引用保存键，WeakHashMap将删除不被引用条目 ### 9.4.5 链接散列表与映射 当你的方法返回true时,添加一个新映射条目就会导致删除eldest项，下面的缓存最多存放100个元素 ## 9.5 视图与包装器 ### 9.5.1 小集合 生成给定元素的集或列表，以及给定键/值对的对象。 ### 9.5.2 子范围 ``` List<Employee> group2=staff.subList(10,20);//第一个索引包含在内，第二个索引不包含在内。 SortedMap<K,V> subMap(K from,K to);//这些方法将返回大于等于from且小于to的所有元素构成的子集。 SortedMap<K,V> headMap(K to); SortedMap<K,V> tailMap(K from); ```