集合

2017-08-01

Java

集合接口和迭代器接口
Java库中的具体的集合
集合框架

集合接口和迭代器接口

集合类的基本接口是Collection接口（扩展了Iterable接口）：

public interface Collection<E> extends Iterable<E> 
{
  boolean add(E element);
  Iterator<E> iterator();
  int size();
    boolean isEmpty(); 
    void clear();
    boolean contains(AnyType X); 
    boolean add(AnyType x); 
    boo1ean remove(AnyType X);
  ....
}

在 Collection 接口中的许多方法所做的工作由它们的英文名称可以看出，因此 size 返回集合中的项数；isEmpty 返回 true 当且仅当集合的大小为 0。如果 x 在集合中，则 contains 返回true。注意，这个接口并不规定集合如何决定 x 是否属于该集合一这要由实现该 Collection 接口的具体的类来确定。add 和 remove 从集合中添加和删除 x，如果操作成功则返回 true，如果因某个看似有理（非异常）的原因失败则返回false。例如，如果要删除的项不在集合中，则 re move 可能失败，而如果特定的集合不允许重复，那么当企图插人一项重复项时，add 操作就可能失败。
Collection接口扩展了Iterable接口，实现Iterable接口的集合必须提供iterator()方法，该方法返回一个 Iterator 类型的对象。该 Iterator 是一个在 java. Util 包中定义的接口。

//Iterator接口
public interface Iterator<E>
{
  E next();
  boolean hasNext();
  void remove();
}

每次对 next 的调用都给出集合的（尚未见到的）下一项。因此，第 1 次调用 next 给出第 1 项，第 2 次调用给出第 2项，等等。hasNext用来告诉是否存在下一项。通过反复调用next()可以逐个访问集合中的所有元素。如果到达了集合的末尾，next()会抛出一个NoSuchElementException,因此需要在调用next()之前调用hasNext()(如果还有多个供访问的对象时就返回true)。
例：

Collection<String> collection = new ArrayList<>();
Iterator<String> iterator = collection.iterator();
while (iterator.hasNext()) {
      iterator.next();
      .....
}

java 5之后提供了foreach循环，foreach循环可以和任何实现了Iterable接口的对象一起工作,Collection扩展了Iterable接口，所以所有的标准集合都可以使用foreach循环。

public interface Iterable<T> {
    Iterator<T> iterator();
    ....
}

用于 Iterable 的对象的增强的 for 循环的时候，它用对 iterator 方法的那些调用代替增强的 for 循环以得到一个 Iterator对象，然后调用next和hasNext。因此，增强型for循环由编译器重写，如下所示。

Iterator <AnyType> itr = coll.Iterator();
while(itr.HasNext()){
    AnyType item = itr.Next();
    System.Out.Println(item);
}

Java的迭代器的查找操作和位置变更是紧密相联的，在执行查找操作（next）的同时迭代器位置移动(将Java的迭代器认为是位于两个元素之间，当调用next()时迭代器就越过下一个元素并返回刚刚越过的那个元素的引用)。

Iterator接口的remove方法将会删除上次调用next()时返回的元素；如果在调用remove()之前没有调用next()时不合法的，抛出一个IllegalStateException异常。

Collection中的其他方法以及AbstractCollection（待补充）。

Java库中的具体的集合

此处输入图片的描述

集合框架的类

此处输入图片的描述

集合框架的接口如下所示：
此处输入图片的描述

此处输入图片的描述

List接口

List接口继承了Collection接口，因此他包含Collection接口的所有方法，外加其他一些方法。

AnyType get(int idx);
AnyType set(int idx, AnyType newVa1); 
void add(int idx, AnyType x); 
void remove(int idx);

ListIterator<AnyType> ListIterator(int pos);

get和set方法使得用户可以访问或改变通过由位置索引idx给定的表中指定位置上的项。索引 0 位于表的前端，索引size()-1代表表中的最后一项，而索引 size（）则表示新添加的项可以被放置的位置。add使得在位置idx处置入一个新的项（并把其后的项向后推移一个位置）。于是，在位置 0 处 add 是在表的前端进行的添加，而在位置size（）处的add是把被添加项作为新的最后项添入表中。除以 AnyType 作为参数的标准的 remove 外，remove 还被重载以删除指定位置上的项。最后，List 接口指定 listIterator 方法，它将产生比通常认为的还要复杂的迭代器。ListIterator 接口将在后面进行介绍。

实现List有两种方式：

使用链表插入删除操作比较便捷，但是查找比较麻烦，需要遍历
使用数组插入删除代价比较大，需要移动其他元素，但是查找操作比较便捷，可以根据索引直接查找到元素。

LinkedList和ArrayList都实现了List接口，其中LinkedList使用双向链表实现的，ArrayList是用数组实现的。

List接口用于描述一个有序的集合，有两种访问元素的协议：

1.迭代器 (适合于链表)
2.get和set方法随机的访问每个元素（适用于数组）

链表列表（LinkedList）

建议先阅读：表-简单链表章节。
Java提供了链表形式的List，LinkedList，LinkedList使用双向链表实现的。

List<String> list = new LinkedList();
list.add("a");
list.add("b");
list.add("c");
Iterator<String> iterator = list.iterator();
String first = iterator.next();
String second= iterator.next();
iterator.remove();

通常需要将新的元素添加到链表的各个位置，添加操作和位置有关，迭代器是用来描述位置的，所以add操作交给迭代器实现，但是只有List的add操作是依赖于位置的，像是set是不依赖于位置的，所以Iterator中并没有定义add操作，集合类库中提供了他的子接口，ListIterator，提供了add操作。

public interface List<E> extends Collection<E> {
    ....
    Iterator<E> iterator();
    ListIterator<E> listIterator();
    ListIterator<E> listIterator(int index);
    ....
}

listIterator(int index) 返回一个迭代器，这个迭代器指向索引为index的元素的前面。

public interface ListIterator<E> extends Iterator<E> {
    
    boolean hasNext();

    E next();

    void remove();
    
    void add(E e);
    
    boolean hasPrevious();

    E previous();

    int nextIndex();

    int previousIndex();

    void set(E e);
    
}

boolean hasPrevious()和hasNext()作用类似，判断是否还有前一个元素；
E previous()和next()作用类似，返回前一个元素；
int nextIndex() 返回下一次调用next方法的时候返回的元素的整数索引
int previousIndex() 返回下一次调用previous方法的时候返回的元素的整数索引，这个值比nextIndex()小一。
void set(E e) 用一个新的元素取代next方法或者previous方法返回的上一个元素。

注意一个问题：

当若干个迭代器修改集合的时候，另一个迭代器对这个集合进行遍历，会出错。

List<String> list = new LinkedList();
list.add("a");
list.add("b");
list.add("c");
Iterator<String> iteratorA = list.iterator();
Iterator<String> iteratorB = list.iterator();
String first = iteratorA.next();
iteratorA.remove();
iteratorB.next();

检测的原理：集合可以跟踪改写操作，比如添加或者删除元素的次数。每个跌打起都维护一个独立的计数值。在每个集合的方法开始处检查自己维护的计数值和集合的计数值是否一致，如果不一致的话就抛出异常。

迭代器只是检测结构性的修改，非结构性的改变并不会被检测到，例如使用set操作进行修改，并不会被检测到。

数组列表（ArrayList）

建议先阅读：表-表的简单数组实现章节。

List描述的是一个有序的集合，集合中元素的位置很重要。List提供了两种遍历方式，第二种方式不适合链表但是比较适合于数组，Java提供了ArrayList，ArrayList实现了List接口，ArrayList内部封装了动态可分配的对象数组。

Vector与ArrayList

对于一个经验丰富的Java程序员来说，在需要动态数组时，可能会使用Vector类。Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象，但是，如果由一个线程访问Vector，代码要在同步操作上耗费大量的时间。而ArrayList方法不是同步的，因此，建议在不需要同步时使用ArrayList，而不是Vector。

比较

链表可以减少在链表中间插入和删除元素所付出的代价，但是不适合根据索引查找某个元素，当查找元素的时候需要对整个列表进行遍历。

数组可以根据索引对元素进行查找操作，但是在列表的中间进行插入和删除操作的时候，需要付出移动其他元素的代价。

我们需要根据自己需要选择合适的列表实现，如果插入删除比较多的话，选择使用链表列表，如果查找操作比较多的话，建议选择数组列表。

注意上面所说的两种实现方式的各自的特点，只有当列表的元素足够多的时候才能体现出来，如果本身元素较少，则没有必要纠结究竟使用哪种数据结构实现的List。

建议阅读：表-一些情况下的时间复杂度对比章节。

Set接口

散列表（HashSet）

散列表:一种数据结构,可以快速查找所需要的对象.–>为每个对象计算hashcode(散列码)。
Java中，散列表用链表数组实现。每个列表称为桶。查表中对象的位置，先计算它的散列码。与桶总数取余，所得结果就是保存这个元素的桶的索引。如果这个桶被没有其他元素，就可以直接将元素插入桶中。
此处输入图片的描述
如果散列冲突(桶占满)，这时需要用新对象与桶中的所有对象进行比较，查看这个对象是否已经存在。如果散列码是合理且随机分布的，桶的数目也足够大，那么此时各个链表将会是短的，需要比较的次数就会很少。
想更多的控制散列表的运行性能，就要指定一个初始的桶数，如果插入散列表中的内容太多，会增加冲突的可能性，降低散列表的性能。
如果大致知道最终会有多少个元素插入到表中，就可以设置桶常数。通常，将桶的数目设置为预计元素的个数的75%-150%。有一个经验，为了防止键的聚集，最好将桶的数目设置为一个素数。标准库使用的桶数是2的次幂，默认值为16。
如果散列表太满，就需要再散列。如果对散列表再散列，就需要创建一个桶数更多的表，并将所有元素插入到这个新表中，然后丢弃原来的表。填装因子(loadfactor)决定何时对散列表进行再散列。如果填装因子为0.75(默认值)，而表中超过75%的位置已经填入元素，这个表就会用双倍的桶数自动的进行再散列，对于大多数的应用程序来说，装填因子为0.75是比较合理的。
散列表可以用于实现几个重要的数据结构，如set类型。

更详细的内容，建议阅读：散列。
面试必备：HashMap源码解析（JDK8）。

树集（TreeSet）

树集对散列集进行了改进。树集是一个有序的集合。可以以任意的顺序将元素插入到集合中。在对集合进行遍历的时候，每个值将自动的按照排序后的顺序呈现。排序使用树结构来实现的（使用的是红黑树）。每次插入元素的时候，元素都被放到正确的位置上。将一个元素添加到树中比添加到散列表中要慢，但是比添加到数组或者链表的正确位置上要快很多。如果数中包含n个元素,查找新元素的位置平均需要log2n次比较。

对象的比较

两种方式:
1.需要排序的对象实现Comparable接口,重新compareto方法.
2.实现comparable接口有局限性。接口只能实现一次，但是不同的集合可能要求这个类的对象按照不同的成员变量进行比较排序。这个时候可以将Comparator对象传给TreeSet构造器(可使用匿名内部类)，重写compare方法。

Queue接口

队列，尾部添加元素，头部删除元素。
双端队列，可以在头部和尾部添加和删除元素。

Java 6 引进了Dequeue接口，并由ArrayDequeue和LinkedList类实现。这两个类都提供了双端队列，并且在必要的时候，可以增加队列的长度。

优先级队列

优先级队列中的元素可以按照任意的顺序插入，却总是按照排序的顺序进行检索。也就是说无论何时调用remove方法，总是会删除最小的元素。然而优先级队列并没有对元素进行排序。优先级队列使用了一个优雅且高效的数据结构，称为堆。堆是一个可以自我调整的二叉树，对树执行添加和删除操作，可以让最小的元素移动到根，而不必花费时间对元素进行排序。

优先级队列既可以保存实现了Comparable接口的对象，也可以保存在构造器中提供比较器的对象。

典型场景：任务调度。

关于堆，建议阅读：优先队列（堆）。

Map接口

Java类库为映射表提供了两个通用的实现：HashMap和TreeMap是映射的两个实现，这两个类都实现了Map接口。

散列映射表对键进行散列，树映射表用键的整体顺序对元素进行排序，并将其组织成搜索树。散列或者映射函数只是作用于键。

散列稍微快一些，如果不需要进行排序，建议选择使用散列映射表。

有 3 种视图：键集、值集合（不是一个集）以及键 / 值对集。

1
2
3

Set<K> keySet()
Collection<V> values
Set<Map.Entry<K, V» entrySet

集合框架

Java集合类库构成了集合的框架。他为集合的实现者定义了大量的接口和抽象类，并且对其中的某些机制进行了描述，例如迭代协议。如果仅仅是使用集合的话，可以不用了解框架。但是如果想要深入学习的话，还是需要了解这些知识的。

接口

集合框架的接口如下所示：
此处输入图片的描述

两个基本接口：

Collection

Map

put添加，get获取。

List是一个有序的集合。元素可以添加到集合的任意的位置。将对像放置到某个位置上可以采用两种方法：使用整数索引或者使用迭代器。
List接口定义了如下几个随机访问的方法：

E set(int index, E element);

void add(int index, E element);

E get(int index);

E remove(int index);

为了避免执行较高成本的随机访问操作，Java 1.4引进了RandomAccess。这个接口可以检测特定的集合是否支持高效的随机访问操作。

if(c instanceOf RandomAccress){
}
else{
}

ArrayList和Vector都实现了这个接口。

ListIterator接口定义了一个方法，用于讲一个元素添加到迭代器所处位置的前面：

1	void add(E item)

要想获取和删除指定位置的元素，需要调用ListIterator的next和remove方法。

Set接口和Collection接口是一样的，只是其方法的行为有着更加严谨的定义。集的add方法拒绝添加重复的元素。集的equals方法定义两个集相等的条件是他们包含相同的元素但是顺序不必相同。hashCode方法的定义应该保证具有相同元素的集能得到相同的散列码。

抽象类

AbstractCollection
AbstractList
AbstractSequentialList
AbstractSet
AbstractQueue
AbstractMap

如果想要实现自己的集合类就可能需要对上面的类进行扩展。

具体实现

LinkedList
ArrayList
ArrayDeque
HashSet
TreeSet
PriorityQueue
HashMap
TreeMap

集合框架中的类：
此处输入图片的描述

第一版遗留下的容器类：

Vector
Stack
HashTable
Properity

此处输入图片的描述

上一篇：异常情况下的生命周期

下一篇：双亲委派模型