Collection集合体系

除了以Map结尾的类之外，其他类都实现Collection接口，而以Map结尾的类实现了Map接口

1、List

1.1、LinkedList

1.1.1、简介

尽管数组在连续存储位置上存放对象引用，但链表却将每个对象存放在独立的节点中。

每个节点还存放着序列中下一个节点的引用；

在Java中，所有链表实际上是双向链表-----即每个节点还存放着指向前驱节点的引用

1.1.2、API

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

所有已实现的接口：

Serializable，Cloneable，Iterable，Collection，Deque，List，Queue

• List和Deque 接口的双链表实现。
• 实现所有可选的列表操作，并允许存放所有元素（包括null）。
• 所有操作都按照双向链接列表的预期执行。索引到列表中的操作将从列表的开头或结尾开始遍历列表，以更接近指定索引的位置为准。
• 请注意，此实现未同步。 如果多个线程同时访问一个链表，并且至少有一个线程在结构上修改了链表，则必须在外部进行同步。
• 有序的；每个对象的位置十分重要
• 由于迭代器是集合中位置的，所以这种依赖位置的add方法将由迭代器负责；只有自然有序的集合使用迭代器添加元素才有实际意义；因此，在Iterator接口中没有add方法；在集合类库提供的子接口ListIterator，其中包含了add方法

1.1.3、ListIterator

列表迭代器，允许程序员在任一方向上遍历列表，在迭代过程中修改列表，并获取迭代器在列表中的当前位置

ListIterator 没有当前元素；其光标位置始终位于调用返回previous()的元素和调用返回的元素之间next()。

public interface ListIterator<E> extends Iterator<E> {
}

LinkedList类的listIterator方法返回一个实现了ListIterator接口的迭代器对象

ListIterator<String> iter = staff.listIterator();

add方法在迭代器位置之前添加一个新对象；下面代码将越过链表中的第一个元素，并在第二个元素之前juliet

List<String> staff = new LinkedList<>();
staff.add("Amy");
staff.add("Bob");
staff.add("Carl");
ListIterator<String> iter = staff.listIterator()://返回链表迭代器
iter.next();//skip past first element
iter.add('jULIET');

如果多次调用add方法，将按照提供的次序把元素添加到链表中；

它们被依次添加到迭代器当前位置之前。

当用一个刚刚由Iterator方法返回，并且指向链表标题与的迭代器调用add操作时，新添加的元素将变成链表的新表头

1.1.4、toString

在Collection接口中声明了许多用于对链表操作的有用方法。其中大部分方法都是在LinkedList类的超类AbstractCollection中实现的。例如：toString

 /**
     * Returns a string representation of this collection.  The string
     * representation consists of a list of the collection's elements in the
     * order they are returned by its iterator, enclosed in square brackets
     * (<tt>"[]"</tt>).  Adjacent elements are separated by the characters
     * <tt>", "</tt> (comma and space).  Elements are converted to strings as
     * by {@link String#valueOf(Object)}.
     *
     * @return a string representation of this collection
     */
    public String toString() {
        Iterator<E> it = iterator();//使用迭代器进行迭代
        if (! it.hasNext()) //没有元素则返回空
            return "[]";

        StringBuilder sb = new StringBuilder()//构造返回的StringBuilder
        sb.append('[');
        for (;;) { //循环遍历元素
            E e = it.next();
            sb.append(e == this ? "(this Collection)" : e);
            if (! it.hasNext()) //向StringBuilder中添加元素
                return sb.append(']').toString();
            sb.append(',').append(' ');
        }
    }

1.1.5、注意事项

在程序中需要采用整数索引访问元素时 ，通常不选用链表

==绝对不应该使用这种让人误解的随机访问方法来遍历链表；==下面这段代码效率较低:

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

每次查找一个元素都要从链表的头部重新开始搜索；LinkedList对象根本不做任何缓存位置信息的操作

使用链表的唯一理由是尽可能的减少在列表中间插入和删除元素所付出的代价；如果列表中只有少数几个元素，就完全可以使用ArrayList

1.2、ArrayList

List接口用于描述一个有序集合；并且集合中每个元素的位置十分重要

有两种访问元素的协议:

1. ​ 用迭代器
2. 用set与get方法随机的访问每个元素（这种不适用于链表，但对数组却很有用）

底层采用动态再分配的对象数组

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

• 所有已实现的接口：

  Serializable，Cloneable，Iterable，Collection，List，RandomAccess

• 直接已知子类：

  AttributeList，RoleList，RoleUnresolvedList

---

---

2、Set

链表和数组可以按照人们的医院排列元素的次序；

但是，如果想要查看某个指定的元素，却又忘记了它的位置，就需要访问所有元素，直到找到为止；

如果集合中包含的元素很多，将会消耗很多时间；如果不在意元素的顺序，可以有几种能够快速查找元素的数据结构。

其缺点是无法控制元素出现的次序，它们将按照有利于其操作目的的原则组织数据

无序；不可重复

2.1、HashSet（散列集，无序）

2.1.1、Hash基础

有一种众所周知的数据结构，可以快速的查找所需的对象，这就是散列表(hash table)

散列码:由对象的实例域产生的一个整数。更准确的说，具有不同数据域的对象将产生不同的散列码。

如果自定义类，就要负责实现这个类的hashCode方法。

注意自己实现的hashCode方法应该与equals方法兼容，即如果a.equals(b)为true则a与b必须具有相同的散列码

2.1.2、如何实现存储

• 在Java中，散列表用链表数组实现。每个链表称为桶
• 要想找表中对象的位置，就要先计算它的散列码，然后与桶的总数取余，所得到的结果就是保存这个元素的桶的索引，或许会很幸运，在这个桶中没有其他元素，此时将元素直接插入到桶中就可以了。当然，有时候会遇到桶被占满的情况，这也是不可避免的，这中现象被称为散列冲突；这时需要用新对象与桶中的所有对象进行比较，查看这个对象是否已经存在。如果散列码是合理且随机分布的，桶的数目足够大，需要比较的次数就会很少
• 在JAVA8中，桶满时会从链表变为平衡二叉树。如果选择的散列函数不当，会产生很多冲突，或者如果有恶意的代码视图在
• 如果想更多的控制散列表的运行性能，就要指定一个初始的桶数。桶数是指用于收集具有相同散列值的桶的数目。如果要插入到散列表中的元素数目太多，就会增加冲突的可能性，降低运行的性能
• 通常将桶数设置为预计元素个数的75%~159%
• 如果散列表太满，就需要再散列，如果要对散列表再散列，就需要创建一个桶数更多的表，并将所有元素插入到这个新表中，然后丢弃原来的表。装填因子（load factor)决定何时对散列表再散列。

2.1.3、HashSet特点

散列表可以用于实现几个重要的数据结构，其中最简单的是Set类型

Set类型是没有重复元素的元素集合；set的add方法首先在集中查找要添加的对象，如果不存在，就将对象添加进去

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

此类实现Set由哈希表（实际上是HashMap实例）支持的接口。它不保证集合的迭代顺序。特别是，它不能保证顺序会随着时间的推移保持恒定。此类允许该null 元素。

为基本操作（这个类提供了固定的时间性能add，remove，contains和size），假定哈希函数将分散的元素正确的桶中。对此集合进行迭代需要的时间与HashSet实例的大小（元素的数量）加上后备HashMap实例的“容量” （存储桶的数量）之和成比例。因此，如果迭代性能很重要，则不要将初始容量设置得过高（或负载因子过低），这一点非常重要。

---

2.2、TreeSet(树集，有序)

• TreeSet类与散列集十分类似，不过，它比散列集有所改进

• 树集是一个有序集合(Sorted collection)。可以任意顺序将元素插入到集合中。在对集合进行遍历时，每个值将自动的按照排序后的顺序进行呈现

• 每次将一个元素添加到树中时，都被放置在正确的排序位置上。因此，迭代器总是以排序好的顺序访问每个元素

• 将一个元素添加到树中要比添加到散列表中慢

• 使用树集，必须能够比较元素；这些元素必须实现Comparable接口，或者构造集合时必须提供一个Comparator

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable//TreeSet实现了NavigableSet<E>接口
    
public interface NavigableSet<E> extends SortedSet<E> {   //NavigableSet继承了SortedSet类
    

查看器Api

所有已实现的接口：

Serializable，Cloneable，Iterable，Collection，NavigableSet，Set，SortedSet

NavigableSet的实现类，基于TreeMap实现。元素使用其，或者通过在设置创建时提供来进行排序，具体取决于所使用的构造函数。

此实现提供了基本的操作保证的log（n）的时间成本（add，remove和contains）。

建设者	描述
TreeSet()	构造一个新的空树集，并根据其元素的自然顺序对其进行排序。
TreeSet(Collection c)	构造一个包含指定集合中元素的新树集，并根据其元素的自然顺序对其进行排序。
TreeSet(Comparator comparator)	构造一个新的空树集，根据指定的比较器排序。
TreeSet(SortedSet s)	构造一个新的树集，其中包含与指定的排序集相同的元素，并使用相同的顺序。

3、队列

• 队列可以让人们有效的在尾部添加一个元素，在头部删除一个元素。有两个端头的队列，即双端队列。可以有效的在头部和尾部同时添加或删除元素。不支持在队列中间添加元素

3.1、双端队列Deque

在Java SE 6中引入Deque接口。并由ArrayDeque和LinkedList类实现

这两个类都提供了双端队列，而且在必要时增加队列的长度

支持在两端插入和删除元素的线性集合。名称双端队列是“双端队列”的缩写，通常发音为“ deck”。

大多数Deque 实现对它们可能包含的元素数量没有固定的限制，但是此接口支持容量受限的双端队列以及没有固定大小限制的双端队列。

• 该接口扩展了Queue接口。当双端队列用作队列时，将导致FIFO（先进先出）行为。元素在双端队列的末尾添加，并从开头删除。
• 双端队列也可以用作LIFO（后进先出）堆栈。该接口应优先于旧Stack类使用。当双端队列用作堆栈时，元素从双端队列的开始处被压入并弹出。 (不建议使用)
• 虽然Deque并非严格要求实现禁止插入null元素，但强烈建议这样做。任何用户Deque认为做实现允许我们强烈建议空元素没有采取插入空的能力优势。之所以如此，null是因为 各种方法都将其用作特殊的返回值，以指示双端队列为空。

public interface Queue<E> extends Collection<E> { } //定义的	Queue接口


public interface Deque<E> extends Queue<E> { //定义的 Deque接口

• 所有超级接口：

  Collection，Iterable，Queue

• 所有已知的子接口：

  BlockingDeque

• 所有已知的实施类：

  ArrayDeque，ConcurrentLinkedDeque，LinkedBlockingDeque，LinkedList

3.2、ArrayDeque

Deque接口的可调整大小的数组实现。

阵列双端队列没有容量限制。

它们会根据需要增长以支持使用。

它们不是线程安全的。

在没有外部同步的情况下，它们不支持多个线程的并发访问。

空元素是禁止的。

此类可能比Stack用作堆栈时要快 ，并且比LinkedList 用作队列时要快。

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable

• Type Parameters:

  E - the type of elements held in this deque

• All Implemented Interfaces:

  Serializable, Cloneable, Iterable, Collection, Deque, Queue

3.3、优先级队列