Java——集合框架

集合

三种集合：规则集Set（一组不重复的元素）、线性表List（元素构成的有序集合）、队列Queue（先进先出方式处理的集合）

Collection接口

Collection接口是处理对象集合的根接口，AbstractCollection类是提供Collection接口部分实现的便利类

boolean add(T o);
boolean addAll(Collection<? extends T> c);
void clear();
boolean contains(Object o);
boolean containsAll(Collection<?> c);
boolean equals(Object o);
int hashCode();
boolean isEmpty();
Iterator<T> iterator();
boolean remove(Object o);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
int size();
T[] toArray();

Iterator

boolean hasNext();
T next();
void remove();

Set

Set接口扩展了Collection，实现Set的具体类必须确保没有重复元素

AbstractSet是个便利类，它扩展AbstractCollection类并实现Set接口

Set接口的具体类是：散列类HashSet、链式散列集LinkedHashSet、树形集TreeSet

HashSet

用来存储互不相同的任何元素
LinkedHashSet

用链表实现来扩展HashSet类，其中的元素可以按照插入时的顺序提取
TreeSet

SortedSet是Set的一个子接口，它可以确保规则集中的元素是有序的
```
T first();
T last();
SortedSet<T> headSet(T toElement);
SortedSet<T> tailSet(T fromElement);
```
NavigableSet扩展了SortedSet
```
T pollFirst();
T pollLast();
T lower(T e);
T higher(T e);
T floor(T e);
T ceiling(T e);
```
TreeSet是SortedSet接口的一个具体类，只要对象是可以互相比较的，就可以添加到一个树形集中

可比较对象：

* 使用`Comparable`接口
* 如果没有使用`Comparable`接口，可以指定比较器

比较器接口`Comparator`

有两个方法compare()和equals()，比如

public class GeometricComparator implements Comparator<GeometricObject> {

    public int compare(GeometricObject o1, GeometricObject 02) {
        ...
    }
}

Set<GetmeticObject> set = new TreeSet<GeometricObject>(new GeometricComparator());

...

线性表

线性表允许存储重复的元素，允许指定他们存储的位置

List接口扩展了Collection接口，增加了面向位置的操作

boolean add(int index, T e);
boolean add(Collection<? extends T> c, int index);
T get(int index);
int indexOf(Object e);
int lastIndexOf(Object e);
ListIterator<T> listIterator();
ListIterator<T> listIterator(int startIndex);
T remove(int index);
T set(int index, T e);
List<T> subList(int from, int to);

ListIterator

支持双向遍历的迭代器

void add(T o);
boolean hasPrevious();
int nextIndex();
T previous();
int previousIndex();
void set(T o);

数组线性表类ArrayList通过数组创建，适合随机访问元素而不是插入；链表类LinkedList通过链表创建，适合插入和删除操作

Collections

操作线性表和集合的静态方法

void sort(List list);
void sort(List list, Comparator comparator);
void reverse(List list);
Comparator reverseOrder();
void shuffle(List list);
void shuffle(List list, Random random);

//  搜索方法要求线性表是已排序的
int binarySearch(List list, Object key);
int binarySearch(List list, Object key, Comparator comparator);

void copy(List des, List src);
void nCopies(int n, Object o);

void fill(List list, Object o);

Object max(Collection collection);
Object max(Collection collection, Comparator comparator);
Object min(Collection collection);
Object min(Collection collection, Comparator comparator);

boolean disjoint(Collection c1, Collection c2);
int frequency(Collection collection, Object object);

规则集比线性表更加高效，如果用规则集就足够则使用规则集，如果程序不需要特别的顺序，就选择散列集

在线性表中除结尾处做插入删除，链式线性表比数组线性表高效

Vector和Stack

Vertor实现了List接口，跟线性表的区别是同步操作的处理，如果不需要同步，最好使用ArrayList，会快很多

void addElement(T o);
int capacity();
void copyInto(Object[] array);
T elementAt(int index);
Enumeration<T> elements();
void ensureCapacity();
T firstElement();
void insertElementAt(T o, int index);
T lastElement();
void removeAllElements();
boolean removeElement(Object o);
void removeElementAt(int index);
void setElementAt(T o, int index);
void setSize(int newSize);
void trimToSize();

Stack是Vector的扩展

boolean empty();
T peek();
T pop();
T push(T o);
int search(Object o);

队列和优先队列

队列是先进先出的数据结构，优先队列中元素被赋予优先级

Queue接口用附加的插入提取和检验操作来扩展Collection

boolean offer(T e);
T poll();
T remove();
T peek();
T element();

双端队列Deque接口用附加的从队列两端插入和删除元素的办法扩展Queue接口

LinkedList实现了List和Deque接口，可以用它创建一个队列

PriorityQueue类实现一个优先队列

图

按照键值存储元素的容器，不能有重复的键值，图的类型有三种：散列图HashMap、链式散列图LinkedHashMap和树形图TreeMap

Map接口提供了查询、更新、获取集合键值的方法

void clear();
boolean containsKey(Object key);
boolean containsValue(Object value);
Set<Map.Entry<K, V>> entrySet();
V get(Object key);
boolean isEmpty();
Set<K> keySet();
V put(K key, V value);
void putAll(Map<? extends K, ? extends V> map);
V remove(Object key);
int size();
Collection<V> values();

Entry是Map接口的内部接口

K getKey();
V getValue();
void setValue(V value);

AbstractMap类是一个便利类，它实现了Map接口中除了entrySet()之外的所有方法

SortedMap接口扩展了Map接口，保持映射以升序排列

K firstKey();
K lastKey();
Comparator<? super K> comparator();
SortedMap<K, V> headMap(K to);
SortedMap<K, V> tailMap(K from);

NavigableMap扩展了SortedMap，以提供导航方法

K floorKey(K key);
K ceilingKey(K key);
K lowerKey(K key);
K higherKey(K key);
Map.EntrySet<K, V> pollFirstEntry();
Map.EntrySet<K, V> pollLastEntry();

TreeMap实现NavigableMap接口，扩展了AbstractMap类

HashMap扩展了AbstractMap类，LinkedHashMap扩展了HashMap类

不需要保持顺序用HashMap，需要保持顺序用LinkedHashMap，需要按键值排序，使用TreeMap

集合