第13章 集合

1.集合接口

1.1 将集合的接口与实现分离

队列通常有两种实现方式：循环数组、链表。

循环数组更高效，但是循环数组是一个有限集合。如果对象数量没有上限，就要用链表实现。

1.2 Java类库中的集合接口和迭代器接口

Java类库中，集合类的基本接口是Collection接口。

public interface Collection<E>{//集合接口的定义
	boolean add(E element);//添加元素，如果改变了集合，返回true
	boolean addAll(Collection<? extends E> other)//将other集合中的所有元素添加到这个集合
	Iterator<E> iterator();//返回访问集合元素的迭代器
	int size();//返回集合元素的个数
	boolean isEmpty();//如果集合为空，返回true
	boolean contains(Object obj);//如果集合包含obj元素，返回true
	boolean containsAll(Collection<?> other);//如果这个集合包含other集合中的所有元素，返回true
	boolean remove(Object obj);//删除obj元素
	boolean removeAll(Collection<?> other);//从这个集合中删除other集合中的所有元素
	void clear();//删除集合中的所有元素
	boolean retainAll(Collection<?> other);//从这个集合中删除与other集合中不同的元素
	Object[] toArray();//返回这个集合的对象集合
	<T> T[] toArray(T[] arrayToFill);//返回这个集合的对象集合。如果arrayToFill足够大，就将集合中的所有元素填入这个数组中；否则分配一个新数组，长度等于集合大小
}

1.2.1 迭代器

public interface Iterator<E>{
	E next();//返回将要访问的下一个对象。如果已经到达了集合的尾部，抛出一个NoSuchElement Exception
	boolean hasNext();//如果存在可访问的元素，返回true
	void remove();//删除上次访问的元素。这个方法必须紧跟在访问一个元素后执行，如果上次访问后集合发生了变化，这个方法将抛出一个IllegalStateException
}

通过反复调用next方法，可以逐个访问集合中的每个元素。

Collection<String> c=...;
Iterator<String> iter=c.iterator();
while(iter.hasNext()){
	String element=iter.next();
	do something with element
}

用for each循环可以更加简练的访问集合，for each循环可以与任何实现了Iterable接口的对象一起工作。

for(String element:c){
	do something with element
}


//Iterable接口
public interface Iterable<E>{
	Iterator<E> iterator();
}

Collection接口扩展了Iterable接口。

元素访问顺序取决于集合类型。ArrayList按照索引依次访问，HashSet则按照某种随机次序访问。

应该将Java迭代器认为是位于两个元素之间。当调用next时，迭代器就越过下一个元素，返回刚刚越过那个元素的引用。

1.2.2 删除元素

Iterator<String> it=c.iterator();
it.next();//越过第一个元素
it.remove();//删除这个元素

it.remove();
it.remove();//Error!

it.remove();
it.next();
it.remove();//Ok

2.具体的集合

集合类型	描述
ArrayList	一种可以动态增长和缩减的索引序列
LinkedList	一种可以在任何位置进行高效的插入和删除操作的有序序列
ArrayDeque	一种用循环数组实现的双端队列
HashSet	一种没有重复元素的无序集合
TreeSet	一种有序集
EnumSet	一种包含枚举类型值的集
LinkedHashSet	一种可以记录元素插入次序的集
PriorityQueue	一种允许高效删除最小元素的集合
HashMap	一种存储键/值关联的数据结构
TreeMap	一种键值有序排列的映射表
EnumMap	一种键值属于枚举类型的映射表
LinkedHashMap	一种可以记住键/值添加次序的映射表
WeakHashMap	一种其值无用武之地后可以被垃圾回收器回收的映射表
IdentityHashMap	一种用==而不是equals比较键值的映射表

2.1 链表

Java中所有链表实际上都是双向链表。

链表是一个有序集合。

常常需要将对象添加到链表的中间，而LinkedList.add方法是将对象添加到链表结尾，Iterator接口中没有add方法。所以结合类库提供了子接口ListIterator，包含add方法。

public interface List<E> implements Iterable<E>,Collection<E>{
	ListIterator<E> listIterator();//返回一个列表迭代器
	ListIterator<E> listIterator(int index);//返回一个列表迭代器，访问列表中的元素，这个元素是第一次调用next返回的给定索引的元素
	void add(int i,E element);//在给定位置添加一个元素
	void addAll(int i,Collection<? extends E> elements);//在给定位置添加某个集合的所有元素
	E remove(int i);//删除给定位置的元素并返回这个元素
	E get(int i);//获取给定位置的元素
	E set(int i,E element);//用新元素取代给定位置的元素，并返回原来的那个元素
	int indexOf(Object element);//返回给定元素第一次出现的位置，没有就返回-1
	int lastIndexOf(Object element);//返回给定元素最后一次出现的位置，没有就返回-1
}

public interface ListIterator<E>() implements Iterator<E>{
	void add(E newElement);//在当前位置添加一个元素
	void set(E newElement);//用新元素取代next或previous上次访问的元素
	boolean hasPrevious();//反向迭代列表，有可访问元素时返回true
	E previous();//返回前一个对象，如果已经到达列表头部，抛出NoSuchElementException
	int nextIndex();//返回下一次调用next方法时将返回的元素索引
	int previousIndex();//返回下一次调用previous方法时将返回的元素索引
}

public class LinkedList<E> implements List<E>{
	LinkedList();//构造器
	LinkedList(Collection<? extends E> elements);//构造器。将集合中所有的元素添加到链表中
	void addFirst(E elements);
	void addLast(E elements);//将元素添加到列表的头部或尾部
	E gatFirst();
	E getLast();//获取头部或尾部元素
	E removeFirst();
	E removeLast();//删除并返回头部或尾部元素
}

LinkedList.get方法的效率并不高，下面这段代码的效率极低。

for(int i=0;i<list.size();i++)
        do something with list.get(i);

每次查找一个元素都要从列表的头部重新开始搜索。LinkedList对象根本不做任何缓存位置信息的操作。get方法做了微小的优化，如果索引大于size()/2就从列表的尾部开始搜索元素。

2.2 数组列表

Vector类的所有方法都是同步的，一个线程访问Vector，代码要在代码同步上耗费大量的时间。ArrayList方法不是同步的。

Java中的ArrayList的初始容量和容量分配

2.3 散列集

散列表为每一个对象计算一个整数，称为散列码。散列码是有对象的实例域产生的一个整数，具有不同数据域的对象将产生不同的散列码。

在Java中，散列表用链表数组实现。每个列表称为桶（bucket）。要想查找表中的对象的位置，就要先计算它的散列码，然后与桶的总数取余，所得到的结果就是保存这个元素的桶的索引。有时候会遇到桶被占满的情况，被称为散列冲突，需要再散列。装填因子决定何时对散列表进行再散列。

Java集合类库提供一个HashSet类实现基于散列表的集。

public class HashSet<E> implements Set<E>{
        HashSet();//构造器
        HashSet(Collection<? extends E> elements);//构造器，将集合中所有元素添加到这个散列集中
        HashSet(int initialCapacity);//构造器，参数为容量
        HashSet(int initialCapacity,float loadFactor);//构造器，参数分别为容量和装填因子
}

2.4 树集

TreeSet类对散列集有所改进。树集是一个有序集合，可以以任何顺序将元素插入到集合中。在对集合进行遍历时，每个值将自动按照排序后的顺序呈现。TreeSet排序是用红黑树结构完成的。将一个元素添加到树（TreeSet）中要比添加到散列表（HashSet）中慢，但是要比添加到数组或链表中要快。

2.5 对象的比较

public interface Comparable<T>{
	int compareTo(T other);//将该对象与其他对象比较
	int compare(T a,T b);//比较两个对象
}

public interface SortedSet<E> implements Set<E>{
	Comparator<? super E> comparator();//返回用于对元素进行比较的比较器。如果元素用Comparable接口的compareTo方法进行比较则返回null
	E first();
	E last();//返回有序集中最小元素和最大元素
}

public interface NavigableSet<E> implements SortedSet<E>{
	E higher(E value);
	E lower(E value);//返回大于value的最小元素或者小于value的最大元素，没有则返回null
	E ceiling(E value);
	E floor(E value);//返回大于value的最大元素或者小于value的最小元素，没有则返回null
	E pollFirst();
	E pollLast();//删除并返回最大或者最小元素，集合为空返回null
	Iterator<E> decendingIterator();//返回一个按照递减顺序遍历集合的迭代器
}

public class TreeSet<E> implements SortedSet<E>,NavigableSet<E>{
	TreeSet();//构造器
	TreeSet(Comparator<? super E> c);//构造器，指定比较器
	TreeSet(SortedSet<? extends E> elements);//构造器，将有序集所有元素添加到树集中，并使用与给定集相同的比较器
}

Object类中没有提供compareTo的默认实现。如果在树集插入自定义对象，就必须通过实现Comparable接口自定义排列顺序。

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);
	}
});

2.6 队列与双端队列

Queue Deque ArrayDeque

2.7 优先级队列

优先级队列使用了堆。堆是一种二叉树，可以让最小的元素移动到根。使用优先级的典型示例是任务调度。每一个任务有一个优先级，任务随机添加到队列中。每当启动一个新任务时，都将优先级最高的任务从队列中删除（习惯“1”为最高优先级）。

2.8 映射表

HashMap和TreeMap实现Map接口。

HashMap与HashTable的区别

HashMap对键进行散列，TreeSet用键的整体顺序对元素进行排序，并将其组织为搜索树。散列和比较函数只能作用于键，与键关联的值不能进行散列或比较。

集合框架没有将映射表本身视为一个集合，有3个视图：键集、值集合（不是集）和键/值对集。键与键/值对形成了一个集，是因为映射表中一个键只能由一个副本。

返回3个视图

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

同时查看键和值，避免对值进行查找

for(Map.Entry<String,Employee> entry:staff.entrySet()){
	String key=entry.getKey();
	Employee value=entry.getValue();
	do something with key,value
}

Map的键仅可以有一个null值，因为键只能由一个副本，值不可以为null

public interface Map<K,V>{
	V get(Object key);//获取与键对应的值，没有返回null
	V put(Object key,Object value);//将键和值插入映射表中
	void putAll(Map<? extends K,? extends V> entries);//将给定映射表的所有条目插入该映射表中
	boolean containKey(Object key);//映射表中有这个键，返回true
	boolean contailValue(Object value);//映射表中有这个值，返回true
	Set<Map.Entry<K,V>> entrySet();//返回键/值对得集
	Set<K> keySet();//返回键集
	Collection<V> values();//返回值的集合
}

public interface Map.Entry<K,V>{
	K getKey();
	V getValue();//返回条目的键或值
	V setValue(V newValue);//设置映射表中与新值对应的值，并返回旧值
}

public interface SortedMap<K> implements Map<K,V>{
	Comparator<? super K> comparator();//返回用于对元素进行比较的比较器。如果元素用Comparable接口的compareTo方法进行比较则返回null
	K firstKey();
	K lastKey();//返回映射表中最小元素和最大元素
}

public class HashMap<K,V> implements Map<K,V>{
        HashMap();//构造器
        HashMap(int initialCapacity);//构造器，参数为容量
        HashMap(int initialCapacity,float loadFactor);//构造器，参数分别为容量和装填因子
}


public class TreeMap<K,V> implements SortedMap<K,V>{
	TreeMap(Comparator<? super K> entries);//构造器，指定比较器
	TreeMap(Map<? extends K,? extends V> entries);//构造器,将散列表中的所有条目添加到树映射表中
	TreeMap(SortedMap<? extends K,? extends V> elements);//构造器，将映射表所有条目添加到树映射表中，并使用与给定映射表相同的比较器
}

2.9 专用集和映射表类

WeakHashMap使用弱引用保存键，实现对“键值对”的动态回收。当“弱键”不再被使用到时，GC会回收它，WeakReference也会将“弱键”对应的键值对删除。

LinkedHashSet LinkedHashMap EnumSet EnumMap 

IdentityHashMap（散列值利用System.identityHashCode计算，不是用hashCode计算的，对象比较时用==而不是equals）

3.集合框架

4.算法

5.遗留的集合

Hashtable Enumeration Properties Stack BitSet

Properties的3个特性：

·键与值都是字符串

·表可以保存到一个文件中，也可以从文件中加载

·使用一个默认的辅助表