13.1 集合接口
本节将介绍Java结合框架的基本设计，展示使用他们的方法，并解释一些颇具争议的特性背后的考虑。
13.1.1 将集合的接口与实现分离
队列接口指出可以在队列的尾部添加元素，在队列的头部删除元素，并且可以查找队列中元素的个数。
队列的实现方式一般有两种：一种是循环数组；另一种的链表实现。
接口集合与实现在概念上的不同：如果需要一个循环数组队列->ArrayDeque类来实现；如果需要一个
链表队列，就直接使用->LinkeList类。这两个类实现了Queue接口。
我们说，接口的本身并不能说明哪种实现的效率高，循环数组要比链表更高效，但是容量有限，链表
相反。如果程序中要收集的对象数量没有上限，最好使用链表来实现。
13.1.2 Java类库中的集合接口和迭代器接口
集合类的基本接口就是Collection接口。
public interface Collection<E>{
boolean add(E element);
Iterator<E> iterator();
...
}
add 方法用于向集合中添加元素。添加元素成功返回ture，未成功【集合没有发生变化】返回false。例如
向集合中添加一个对象，而这个对象在集合中已经存在，这个添加没有成功，因为集合中不允许有重复的对象。
iterator 方法用于返回一个 实现了Iterator接口的对象。可以使用这个迭代器对象依次访问集合中的元素。
1）迭代器
Iterator接口包含3个方法：
public interface Iterator<E>{
E next();
boolean hasNext();
void remove();
}
next 方法可以逐个访问集合中的每个元素，但是到了集合的末尾，next方法将抛出一个NoSuchElementException。
因此，需要在调用next之前调用hasNext方法。
hasNext 方法 用于检查序列中是否还有元素。
Collection<String> c = ...;
Iterator<String> iter = c.iterator();
while(iter.hasNext()){
String element = iter.next();
do something with element
...
}
注：
从Java SE 5.0 起，这个循环可以采用一种更加优雅的缩进方法。
for(String element :c){
do something with element
...
}
编译器简单地将"for each" 循环翻译为带有迭代器的循环。
Collection接口扩展了Iterable接口。因此，对于标准库中的任何集合都可以使用"for each" 循环。
元素的访问的顺序取决于集合类型。ArrayList迭代，迭代器从索引 0 开始，每迭代一次，索引值 加1。
HashSet迭代之后，每个元素将会按照 某种随机的次序出现。但是对于计算总和 或者 统计某个条件的
元素个数这类与顺序无关来说不是什么问题。
2）删除元素
remove 方法用于删除上次调用next方法是返回的元素。如果想要删除指定位置上的元素，仍然需要越过这个元素。
if.remove();
it.remove();//错误
//删除两个相邻的元素
it.remove();
it.next();
it.remove();//正确
3）泛型实用方法
下面十一检测任意集合是否包含指定元素的泛型方式
//这样做的好处就是不必自己重新构建这些方法了。contains就是这样一个方法
public static <E> boolean contains(Collection<E> c,Object obj){
for(E element: c)
if(element.equals(obj))
return true;
return false;
}
Collection接口声明了很多有用的方法，所有实现类都必须提供这些方法。下面例举一部分：
int size();
boolean isEmpty();
boolean contains(Object obj);
boolean containsAll(Collection<?> c)
boolean equals(Object other);
boolean addAll(Collection<? extends E> from);
boolean remove(Object obj);
boolean removeAll(Collection<?> c>;
void clear();<pre name="code" class="java">
如果我们在实现每个类都要提供如此多的例行方法将是很麻烦的。为了实现者能够更容易地实
现这个接口，java库类提供了一个类AbstractCollection,它将基础方法size() 、iterator()抽象化。
public abstract class AbstractCollection<E> implements Collection<E>{
...
public abstract Iterator<E> iterator();
public boolean contains(Object obj){
for(E element: this)//迭代器 iterator
if(element.equals(obj))
return true;
return false;
}
...
}
boolean retainAll(Collection<?> c);
Object[] toArray();
<T> T[] toArray(T[] arrayToFill);
一个具体的集合类可以扩展AbstractCollection类。现在要由具体的集合类提供iterator方法，contains方法
是由AbstractCollection超类提供。如果子类有更加有效的方式去实现contains方法也可以由子类提供，这点
没有任何限制。
对于类框架来说，这个设计很好。集合类用户可以使用泛型接口（Collection 、Iterator等）中一组更加丰富的方法，而实际的数据结构
实现者并没有需要实现所有例行方法的负担。
13.2.1 链表
由于最近数据结构老师在将链表，对于c实现的链表的创建、查找、删除、略微懂，这里不说了。
链表 和 顺序表 相比，优势在于在一组数据中间添加和删除一个元素的代价。
下面代码实例中，先添加3个元素，再将第二个元素删除：
package com.test1;
import java.util.*;
/**
* linkedList 链表
* 一些需要注意的点：
* 1.链表与泛型集合的重要区别：链表是ordered collection 每个对象的位置很重要
* 2.链表的缺点是不能高效的随机访问对象元素，虽然LinkedList类提供了get方法，但其效率不敢恭维
* 3.使用链表的唯一理由就是 减少在列表中间插入或删除元素所付出的代价
* 4.List 中只有少数几个元素 我们可以使用ArrayList
* @author PeersLee
* 该代码首先创建两个链表，合并，然后从第二个链表中每隔一个元素删除一个元素，最后测试removeAll
*/
public class test2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
List<String> staff = new LinkedList<>();
staff.add("A");
staff.add("B");
staff.add("C");
ListIterator<String> iter = staff.listIterator();
String first = iter.next();
System.out.println("first:"+first);
String second = iter.next();
System.out.println("second:"+second);
//注意此时挡板在 AB|C
iter.previous();//此方法和next()一样，返回刚越过的对象
//A|BC
String testString = iter.previous();
//|ABC
System.out.println("testString:"+testString);
int ni = iter.nextIndex();
System.out.println("ni:"+ni);
int pi = iter.previousIndex();
System.out.println("pi:"+pi);
//ni = 0
//pi =-1
//说明游标在初始位置
}
}
链表与泛型集合之间有一个重要的区别。链表有序，对象的位置很重要。LinkedList.add() 方法将对象添加到链表的尾
部。如果将元素添加到链表的中间时，由于迭代器是描述集合中位置的，所以这种依赖位置的add()方法将由迭代器负
责。只有对自然有序的集合使用迭代器添加元素才有实际意义。集（set）类型，其中元素完全无序，因此，在Iterator
接口中就没有add()方法。然而子接口ListIterator包含add()方法[这个方法不返回boolean类型的值，它假定添加操作总
会改变链表]，并且还可以反向的遍历链表。
下面的代码实现ListIterrator中的一些方法：
package com.test1;
import java.util.*;
public class test2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
List<String> staff = new LinkedList<>();
staff.add("A");
staff.add("B");
staff.add("C");
ListIterator<String> iter = staff.listIterator();
String first = iter.next();
System.out.println("first:"+first);
String second = iter.next();
System.out.println("second:"+second);
//注意此时挡板在 AB|C
iter.previous();//此方法和next()一样，返回刚越过的对象
//A|BC
String testString = iter.previous();
//|ABC
System.out.println("testString:"+testString);
int ni = iter.nextIndex();
System.out.println("ni:"+ni);
int pi = iter.previousIndex();
System.out.println("pi:"+pi);
//ni = 0
//pi =-1
//说明游标在初始位置
}
<span style="font-size:18px;">}</span>
小结：
虽然链表随机访问元素的效率十分低，但是LinkedList还是提供了一个 get();方法，当然，如果你使用了这个方法
就说明你选择错了数据结构。
使用链表的唯一理由就是尽可能降低 在列表中间插入或者删除元素 的代价，如果链表只有几个元素，完全可以
使用ArrayList()。
下面的代码是通过调用AbstractCollection类中的toString方法打印出链表a中的所有元素:
package com.test1;
import java.util.*;
public class test3 {
public static void main(String[] args) {
// TODO Auto-generated method stub
List<String> a = new LinkedList<>();
a.add("A");
a.add("B");
a.add("C");
List<String> b = new LinkedList<>();
b.add("D");
b.add("E");
b.add("F");
b.add("G");
//将b中的对象移动到 a中
ListIterator<String> aIter = a.listIterator();
Iterator<String> bIter = b.iterator();
while(bIter.hasNext()){
if(aIter.hasNext()) aIter.next();
//个人理解 游标在新插入对象右边
aIter.add(bIter.next());
}
System.out.println(a);
System.out.println(b);
//删除位置代号是偶数的对象（坐标从‘1’开始）
bIter = b.iterator();
while(bIter.hasNext()){
bIter.next();
if(bIter.hasNext()){
bIter.next();
bIter.remove();
}
}
System.out.println(b);
//从链表a中将b中的所有元素删除
a.removeAll(b);
System.out.println(a);
}
}
13.2.2 数组列表
- ArraysList 封装了一个动态再分配的对象数组。
- ArraysList方法不是同步的，在需要同步时建议使用Vector。
13.2.3 散列表
- 散列表可以用于实现几个重要的数据结构，例如 set类型。
- set 是没有重复元素的元素集合。
- set的add方法首先在集合中查找要添加的元素，若不存在则将其加入
package com.test3;
import java.util.*;
/**
* 散列集
* 如果不在乎元素的顺序，则有几种能够快速查找元素的数据结构，他们是按照有利于其操作目的的原则组织数据
* HashTable 散列表 快速查找所需要的对象
* 散列码 由 hashCode 函数得出 由对象的实例域产生的一个整数
* 每个列表被称为一个 bucket 桶
* 要计算出对象的位置就要就算出散列码，与桶的总数取余，所得的结果就是保存这个元素的一个引索
*
* @author PeersLee
*
*该程序实现 读取输入的所有单词，将他们添加到散列集中，遍历，打印出数量
*/
public class SetTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
//HashSet 实现Set 其底层实现为HashMap
Set<String> words = new HashSet<>();
long totalTime = 0;
Scanner in = new Scanner(System.in);
/*
* hasNext()
* Returns true if this scanner has another token in its input.
*/
int n = 1;
while(in.hasNext() && n <= 20) {
/*
* next()
* Finds and returns the next complete token from this scanner.
*/
String word = in.next();
/*
* currentTimeMillis()
* Returns the current time in milliseconds.
*/
long callTime = System.currentTimeMillis();
words.add(word);
callTime = System.currentTimeMillis() - callTime;
totalTime += callTime;
n++;
}
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 + " milliseconds.");
}
}
}
13.2.4 树集 TreeSet
- 树集 TreeSet 也是个有序集合，其排序是树（red-black tree）机构完成的。
- 红黑树-> 每次将一个元素添加到树中时，都将其放在正确的排序位置。
- 将元素加入到TreeSet中要比HashSet中慢，不过TreeSet可以自动的对元素进行排序。
13.2.5 对象的比较
- 树集假定插入的元素实现了Comparable接口。
- 树的排序是全序的，任意两个元素必须是可比的。
目录：
TreeSetTest：
package com.test1;
import java.util.*;
/**
* 1.创建了两个Item对象的树集
* 2.第一个按照部件的编号排序，这是 Item 对象的默认顺序
* 3.第二个是通过定制的比较器来按照描述信息排序
* @author PeersLee
*
*/
public class TreeSetTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
/**
* SortedSet是个接口，它里面的（只有TreeSet这一个实现可用）中的元素一定是有序的。
* TreeSet类实现Set 接口，该接口由TreeMap 实例支持。此类保证排序后的 set 按照升序排列元素
*/
SortedSet<Item> parts = new TreeSet<>();
parts.add(new Item("Toaster[烤面包片机]", 1234));
parts.add(new Item("Widget[装饰品]", 4567));
parts.add(new Item("Modem[调制解调器]", 6789));
System.out.println("parts: " + parts);
SortedSet<Item> sortByDescription = new TreeSet<>(new Comparator<Item>() {
public int compare(Item a, Item b) {
String descrA = a.getDescription();
String descrB = b.getDescription();
return descrA.compareTo(descrB);
}
});
sortByDescription.addAll(parts);
System.out.println(sortByDescription);
}
}
Item
package com.test1;
import java.util.*;
public class Item implements Comparable<Item> {
//partNumber -> 零件号码
private String description;
private int partNumber;
// construct an item.
public Item(String aDescription, int aPartNumber) {
description = aDescription;
partNumber = aPartNumber;
}
//Gets
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) {
return Integer.compare(partNumber, other.partNumber);
}
}