第十二章 - 集合 - 《onJava8》

set
迭代器Iterators
- Iterable
- ListIterator
链表LinkedList
堆栈stack
集合Set
队列Queue
- 优先级队列PriorityQueue

Arrays.asList() 的输出作为一个 List,它的大小是固定的,没法add,也没法addAll, 因为其底层是一个数组

set

HashSet是检索元素最快的,treeSet(升序)跟linkedSet更强调元素的存储顺序

迭代器Iterators

迭代器并不关系它正在使用的集合的类型, 迭代器是一个对象, 它在序列中移动并选择这个序列中的每个对象, 而客户端程序员不知道也不需要关系这个序列的底层结构, 另外迭代器是一个轻量级对象, 创建它的代价很小
1.使用Iterators()方法, 要求返回一个Iterators, Iterators将返回序列中第一个元素
2.使用next()将获得序列中的下一个元素
3.使用hasNext()将检查序列中是否还有元素
4.使用remove()将会使迭代器最近一个返回的元素被删掉,它删除的是next()的返回值,所以使用它必须是前面有next()
有了Iterators 就不需要考虑集合的数量, 因为有next()跟hasNext(), 当然如果并不对list进行修改,只是单纯的遍历的话,用fori更方便

// collections/CrossCollectionIteration.java
import typeinfo.pets.*;
import java.util.*;
public class CrossCollectionIteration {
  public static void display(Iterator<Pet> it) {
    while(it.hasNext()) {
      Pet p = it.next();
      System.out.print(p.id() + ":" + p + " ");
    }
    System.out.println();
  }
  public static void main(String[] args) {
    List<Pet> pets = Pets.list(8);
    LinkedList<Pet> petsLL = new LinkedList<>(pets);
    HashSet<Pet> petsHS = new HashSet<>(pets);
    TreeSet<Pet> petsTS = new TreeSet<>(pets);
    display(pets.iterator());
    display(petsLL.iterator());
    display(petsHS.iterator());
    display(petsTS.iterator());
  }
}
/* Output:
0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug
7:Manx
0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug
7:Manx
0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug
7:Manx
5:Cymric 2:Cymric 7:Manx 1:Manx 3:Mutt 6:Pug 4:Pug
0:Rat
*/

Iterable

// collections/CrossCollectionIteration2.java
import typeinfo.pets.*;
import java.util.*;
public class CrossCollectionIteration2 {
  public static void display(Iterable<Pet> ip) {
    Iterator<Pet> it = ip.iterator();
    while(it.hasNext()) {
      Pet p = it.next();
      System.out.print(p.id() + ":" + p + " ");
    }
    System.out.println();
  }
  public static void main(String[] args) {
    List<Pet> pets = Pets.list(8);
    LinkedList<Pet> petsLL = new LinkedList<>(pets);
    HashSet<Pet> petsHS = new HashSet<>(pets);
    TreeSet<Pet> petsTS = new TreeSet<>(pets);
    display(pets);
    display(petsLL);
    display(petsHS);
    display(petsTS);
  }
}
/* Output:
0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug
7:Manx
0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug
7:Manx
0:Rat 1:Manx 2:Cymric 3:Mutt 4:Pug 5:Cymric 6:Pug
7:Manx
5:Cymric 2:Cymric 7:Manx 1:Manx 3:Mutt 6:Pug 4:Pug
0:Rat
*/

ListIterator

ListItertor是一个更强大的Iterator,它只能由各种List生成, Iterator只能向前移动, 单ListIterator可以双向移动, 也就是它在list中指向的位置当前元素previousIndex()跟后一个元素nextIndex(),还可以通过ListIterator()方法来获取集合的第一个元素, 同时它还是可set()对最近访问过的一个元素进行赋值,同时可以用ListIterator(n)来定位到索引为n的的元素

// collections/ListIteration.java
import typeinfo.pets.*;
import java.util.*;
public class ListIteration {
  public static void main(String[] args) {
    List<Pet> pets = Pets.list(8);
    ListIterator<Pet> it = pets.listIterator();
    while(it.hasNext())
      System.out.print(it.next() +
        ", " + it.nextIndex() +
        ", " + it.previousIndex() + "; ");
    System.out.println();
    // Backwards:
    while(it.hasPrevious())
      System.out.print(it.previous().id() + " ");
    System.out.println();
    System.out.println(pets);
    it = pets.listIterator(3);
    while(it.hasNext()) {
      it.next();
      it.set(Pets.get());
    }
    System.out.println(pets);
  }
}
/* Output:
Rat, 1, 0; Manx, 2, 1; Cymric, 3, 2; Mutt, 4, 3; Pug,
5, 4; Cymric, 6, 5; Pug, 7, 6; Manx, 8, 7;
7 6 5 4 3 2 1 0
[Rat, Manx, Cymric, Mutt, Pug, Cymric, Pug, Manx]
[Rat, Manx, Cymric, Cymric, Rat, EgyptianMau, Hamster,
EgyptianMau]
*/

链表LinkedList

它在中间插入跟删除比较高效,但是在随机访问上不那么效率,LinkedList 还添加了一些方法，使其可以被用作栈、队列或双端队列（deque)
相关方法

getFirst() 和 element() 是相同的，它们都返回列表的头部（第一个元素）而并不删除它，如果 List 为空，则抛出 NoSuchElementException 异常。 peek() 方法与这两个方法只是稍有差异，它在列表为空时返回 null 。
removeFirst() 和 remove() 也是相同的，它们删除并返回列表的头部元素，并在列表为空时抛出 NoSuchElementException 异常。 poll() 稍有差异，它在列表为空时返回 null 。
addFirst() 在列表的开头插入一个元素。
offer() 与 add() 和 addLast() 相同。它们都在列表的尾部（末尾）添加一个元素。
removeLast() 删除并返回列表的最后一个元素。

堆栈stack

后进先出,有时候也被称为叠加栈, 压入push(), 弹出pop()->返回并删除栈顶元素, peek()->返回并不删除栈顶元素

// onjava/Stack.java
// A Stack class built with an ArrayDeque
package onjava;
import java.util.Deque;
import java.util.ArrayDeque;
public class Stack<T> {
  private Deque<T> storage = new ArrayDeque<>();
  public void push(T v) { storage.push(v); }
  public T peek() { return storage.peek(); }
  public T pop() { return storage.pop(); }
  public boolean isEmpty() { return storage.isEmpty(); }
  @Override
  public String toString() {
    return storage.toString();
  }
}

这里用ArrayDeque来实现stack
注意java util 跟on java包里都有stack 是重名的

集合Set

set里面是非重复的, 用set的另一个目的是检查归属性, hashSet它来查数据是最快的,hashSet使用散列存储模式, treeSet是使用红黑树结构存储会进行排序,linkedSet也是使用散列,但其注重顺序

队列Queue

先进先出,因此被用作一种可靠的传输方法(因为插入跟取出的顺序是相同的)linkedList实现了Queue接口,并提供了一些方法实现队列
offer() 是与 Queue 相关的方法之一，它在允许的情况下，在队列的尾部插入一个元素，或者返回 false 。 peek() 和 element() 都返回队头元素而不删除它，但是如果队列为空，则 element() 抛出 NoSuchElementException ，而 peek() 返回 null 。 poll() 和 remove() 都删除并返回队头元素，但如果队列为空，poll() 返回 null ，而 remove() 抛出 *NoSuchElementException 。

优先级队列PriorityQueue

正常的先进先出出的那个是等待的时间最长的那个元素, 而这个优先级的先进先出出去的是优先级最高的那个元素
当在 PriorityQueue 上调用 offer() 方法来插入一个对象时，该对象会在队列中被排序。[^5]默认的排序使用队列中对象的自然顺序（natural order），但是可以通过提供自己的 Comparator 来修改这个顺序。 PriorityQueue 确保在调用 peek() ， poll() 或 remove() 方法时，获得的元素将是队列中优先级最高的元素。

可以看到，实际上只有四个基本的集合组件： Map ， List ， Set 和 Queue ，它们各有两到三个实现版本（Queue 的 java.util.concurrent 实现未包含在此图中）。最常使用的集合用黑色粗线线框表示。
虚线框表示接口，实线框表示普通的（具体的）类。带有空心箭头的虚线表示特定的类实现了一个接口。实心箭头表示某个类可以生成箭头指向的类的对象。例如，任何 Collection 都可以生成 Iterator ， List 可以生成 ListIterator （也能生成普通的 Iterator ，因为 List 继承自 Collection ）。

除了treeSet, 其他的set都具有collection相同的接口, list跟collection存在明显的不同,尽管list的方法都在collection中,Queue的方法是独立的, 不需要调用collection,Map跟collection唯一的交集是Map的entrySet跟value会产生collection