本章内容：
* 集合接口
* 具体的集合
* 集合框架
* 算法
* 遗留的集合
Java集合类库将接口（interface）与实现（implementation）分离。
队列接口指出可以在队列的尾部添加元素，在队列的头部删除元素，并且可以查找队列中元素的个数。当需要收集对象，并按照“先进先出”的规则检索对象时就应该使用队列。
队列通常有两种实现方式：一种是使用循环数组；另一种是使用链表。
每一个实现都可以通过一个实现了Queue接口的类表示。
public interface Collection<E>
{
boolean add(E element);
Iterator<E> iterator();
...
}
public interface Iterator<E>
{
E next();
boolean hasNext();
void remove();
}
public interface Iterable<E>
{
Iterator<E> iterator();
}
| 集合类型 | 描述 |
|---|---|
| ArrayList | 一种可以动态增长和缩减的索引序列 |
| LinkedList | 一种可以在任何位置进行高效地插入和删除操作的有序序列 |
| ArrayDeque | 一种用循环数组实现的双端队列 |
| HashSet | 一种没有重复元素的无序集合 |
| TreeSet | 一种有序集 |
| EnumSet | 一种包含枚举类型的集 |
| LinkedHashSet | 一种可以记住元素插入次序的集 |
| PriorityQueue | 一种允许高效删除最小元素的集合 |
| HashMap | 一种存储键/值关联的数据结构 |
| TreeMap | 一种键值有序排列的映射表 |
| EnumMap | 一种键值属于枚举类型的映射表 |
| LinkedHashMap | 一种可以记住键/值项添加次序的映射表 |
| WeakHashMap | 一种其值无用武之地后可以被垃圾回收器回收的映射表 |
| IdentityHashMap | 一种用==而不是用equals比较键值的映射表 |
除了以Map结尾的类之外，其他类都实现了Collection接口。而以Map结尾的类实现了Map接口。
数组和数组列表都有一个重大的缺陷，就是从数组的中间位置删除一个元素要付出很大的代码，其原因是数组中处于被删除元素之后的所有元素都要向数组的前端移动。在数组中间的位置上插入一个元素也是如此。
在Java程序设计语言中，所有链表实际上都是双向链接的（doubly linked）。
链表与泛型集合之间有一个重要的区别。链表是一个有序集合（ordered collection），每个对象的位置十分重要。LinkedList.add方法将对象添加到链表的尾部。但是，尝尝需要将元素添加到链表的中间。由于迭代器是描述集合中位置的，所以这种依赖于位置的add方法将由迭代器负责。只有对自然有序的集合使用迭代器添加元素才有实际意义。因此，在Iterator接口中就没有add方法。相反地，集合类库提供了子接口ListIterator，其中包含了add方法。
LinkedList<String> list = ...;
String obj = list.get(n);
for (int i = 0; i<list.size();i++)
do something with list.get(i);
List接口用于描述一个有序集合，并且集合中每个元素的位置十分重要。有两种访问元素的协议：一种是用迭代器。另一种是用get和set方法随机地访问每个元素。后者不适用于链表，但对数组却很有用。集合类库提供了一种大家熟悉的ArrayList类，这个类也实现了List接口。ArrayList封装了一个动态再分配的对象数组。
在需要动态数组时，可能会使用Vector类。为什么要用ArrayList取代Vector呢？原因很简单：Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象。但是，如果由一个线程访问Vector，代码要在同步操作上耗费大量的时间。这种情况还是很常见的。而ArrayList方法不是同步的，因此，建议在不需要同步时使用ArrayLits，而不要使用Vector。
可以快速地查找所需要的对象的常见的数据结构就是散列表（hash table）。散列表为每个对象计算一个整数，称为散列码（hash code）。散列码是由对象的实例域产生的一个整数。更准确的说，具有不用数据域的对象将产生不同的散列码。
如果自定义类，就要负责实现这个类的hashCode方法。注意，自己实现的hashCode方法应该与equals方法兼容，即如果a.equals(b)俄日true，a与b必须具有相同的散列码。
在Java中，散列表用链表数组实现。每个列表被称为桶（bucket）。要想查找表中对象的位置，就要先计算它的散列码，然后与桶的总数取余，所得到的结果就是保存这个元素的桶的索引。如果在这个桶中没有其他元素，此时将元素直接插入到桶中就可以了。当然，有时候会遇到桶被占满的情况，这也是不可避免的。这种现象被称为散列冲突（hash colision）。这时，需要用新对象与桶中的所有对象进行比较，查看这个对象是否已经存在。如果散列码是合理且随机分布的，桶的数目也足够大，需要比较的次数就会很少。
树集是一个有序集合（sorted collection）。可以以任意顺序将元素插入到集合中。在对集合进行遍历时，每个值将自动地按照排序后的顺序呈现。
排序是用树结构完成的（当前实现使用的是红黑树（red-black tree））每次将一个元素添加到树中时，都被放置在正确的排序位置上。因此，迭代器总是以排好序的顺序访问每个元素。
将一个元素添加到树中要比添加到散列表中慢，但是，与将元素添加到数组或链表的正确位置上相比还是快很多的。如果树中包含n个元素，查找新元素的正确位置平均需要log2n次比较。
| 文档 | 单词总数 | 不同的单词个数 | HashSet | TreeSet |
|---|---|---|---|---|
| Alice in Wonderland | 28195 | 5909 | 5秒 | 7秒 |
| The Count of Monte Cirsto | 466300 | 37545 | 75秒 | 98秒 |
public interface Comparable<T>
{
int compreTo(T other);
}
使用Comparable接口定义排列排序显然有其局限性。对于一个给定的类，只能够实现这个接口一次。可以通过将Comparator对象传递给TreeSet构造器来告诉树集使用不用的比较方法。Comparator接口声明了一个带有两个显式参数的compare方法：
public interface Comparator<T>
{
int compare(T a,T b);
}
从Java SE 6起，TreeSet类实现了NavigableSet接口。这个接口增加了几个便于定位元素以及反向遍历的方法。
队列可以让人们有效地在尾部添加一个元素，在头部删除一个元素。有两个端头的队列，即双端队列，可以让人们有效地再头部和尾部同事添加或删除元素。不支持在队列中间添加元素。在Java SE 6中引入了Deque接口，并由ArrayDeque和LinkedList类实现。这两个类都提供了双端队列，并且在必要时可以增加队列的长度。
java.util.Queue 5.0
java.util.Deque< E > 6
java.util.ArrayDeque< E > 6
优先级队列（priority queue）中的元素可以按照任意的顺序插入，却总是按照排序的顺序进行检索。也就是说，无论何时调用remove方法，总会获得当前优先级队列中最小的元素。然而，优先级队列并没有对所有的元素进行排序。如果用迭代的方式处理这些元素，并不需要对它们进行排序。优先级队列使用了一个优雅且高效地数据结构，称为堆（heap）。堆是一个可以自我调整的二叉树，对树执行添加（add）和删除（remore）操作，可以让最小的元素移动到根，而不必花费时间对元素进行排序。
与TreeSet一样，一个优先级队列既可以保存实现了Comparable接口的类对象，也可以保存在构造器中提供比较器的对象。
java.util.PriorityQueue 5.0
映射表用来存放键/值对。如果提供了键，就能够查找到值。
Java类库为映射表提供了两个通用的实现：HashMap和TreeMap。这两个类都实现了Map接口。
散列映射表对键进行散列，树映射表用键的整体顺序对元素进行排序，并将其组织成搜索树。散列或比较函数只能作用于键。与键关联的值不能进行散列或比较。
弱散列映射表
设计WeakHashMap类是为了解决一个有趣的问题。如果有一个值，对应的键已经不在使用了，将会出现什么情况呢？假定对某个键的最后一次引用已经消亡，不会有任何途径引用这个值的对象了。但是，由于在程序中的任何部分没有再出现这个键，所以，这个键/值对无法从映射表中删除。为什么垃圾回收期不能够删除它呢？难道删除无用的对象不是垃圾回收器的工作吗？
垃圾回收器耿总活动的对象。只要映射表对象是活动的，其中的所有桶也是活动的，它们不能被回收。因此，需要由程序负责从长期存活的映射表中删除那些无用的值。或者使用WeakHashMap完成这件事情。当对键的唯一引用来自散列表条目时，这一数据结构将与垃圾回收器协同工作一起删除键/值对。
WeakHashMap使用弱引用（weak references）保存键。WeakReference对象将引用保存到另外一个对象中，在这里，就是散列表键。对于这种类型的对象，垃圾回收器用一种特有的方式进行处理。通常，如果垃圾回收器发现某个特定的对象已经没有他人引用了，就将其回收。然而，如果某个对象只能有WeakReference引用，垃圾回收器仍然回收它，但要将引用这个对象的弱引用放入队列中。WeakHashMap将周期性地检查队列，以便找出新添加的弱引用。一个弱引用进入队列意味着这个键不再被他人使用，并且已经被收集起来。于是，WeakHashMap将删除对应的条目。
链接散列集和链接映射集
Java SE 1.4增加了两个类：LInkedHashSet和LinkedHashMap，用来记住插入元素想的顺序。这样就可以避免在散列表中的项从表面上看是随机排列的。当条目插入到表中时，就会并入到双向链表中。
链接散列映射表将用访问顺序，而不是插入顺序，对映射表条目进行迭代。每次调用get或put，受到影响的条目将从当前的位置删除，并放到条目链表的尾部（只有条目在链表中的位置会受影响，而散列表中的桶不会受影响。一个条目总位于与键散列码对应的桶中）。
访问顺序对于实现高速缓存的“最近最少使用”原色十分重要。
枚举集与映射集
EnumSet是一个枚举类型元素集的高效实现。由于枚举类型只有有限个实例，所以EnumSet内部用位序列实现。如果对应的值在集中，则对应的位被置为1。
EnumSet类没有公共的构造器。可以使用静态工厂方构造这个集。
可以使用Set接口的常用方法来修改EnumSet。
EnumMap是一个键类型为枚举类型的映射表。它可以直接且高效地用一个值数组实现。在使用时，需要在构造器中指定键类型。
java.util.WeakHashMap< K,V > 1.2
java.util.LinkedHashSet 1.4
java.util.LinkedHashMap< K,V > 1.4
java.util.EnumSet< E extends Enum< E >> 5.0
java.util.EnumMap< K extends Enum< K >,V > 5.0
java.util.IdentityHashMap< K,V > 1.4
java.lang.System 1.0
框架（framework）是一个类的集，它奠定了创建高级功能的基础。框架包含很多超类，这些超类拥有非常有用的功能、策略和机制。框架使用者创建的子类可以扩展超类的功能，而不必重新创建这些基本的机制。
Java集合类库构成了集合类的框架，它为集合的实现者定义了大量的接口和抽象类，并且对其中的某些机制给予了描述。如果想要实现用于多种集合类型的泛型算法，或者是想增加新的集合类型，了解一些框架的知识是很有帮助的。
集合有两个基本的接口：Collection和Map。可以使用下列方法向集合中插入元素：
boolean add(E element)
但是，由于映射表保存的是键/值对，所以可以使用put方法进行插入。
V put(K key,V value)
要想从集合中读取某个元素，就需要使用迭代器访问它们。然而，也可以用get方法从映射表读取值：
V get(K key)
void add(int index,E element)
E get(int index)
void remove(int index)
List接口在提供这些随机访问方法时，并不管它们对某种特定的实现是否高效。为了避免执行成本较高的随机访问操作，Java SE 1.4引入了一个标记接口RandomAccess。这个接口没有任何方法，但可以用来检测一个特定的集合是否支持高效的随机访问：
if (c instanceof RandomAccess)
{
use random access algorithm
}
else
{
use sequential access algorithm
}
ArrayList类和Vector类都实现了RandomAccess接口。
ListIterator接口定义了一个方法，用于将一个元素添加到迭代器所处位置的前面：
void add(E element)
要想获取和删除给定位置的元素，值需要调用Iterator接口中的next方法和remove方法即可。
通过使用视图（views）可以获得其他的实现了集合接口和映射表接口的对象。映射表类的keySet方法就是一个这样的实例。初看起来，好像这个方法创建了一个新集，并将映射表中的所有键都填进去，然后返回这个集。但是，情况并非如此。取而代之的是：keySet方法返回一个实现Set接口的类对象，这个类的方法对原映射表进行操作。这种集合称为视图。
轻量级集包装器
Arrays类的静态方法asList将返回一个包装了普通Java数组的List包装器。这个方法可以将数组传递给一个期望得到列表或几个变元的方法。返回的对象不是ArrayList。
它是一个视图对象，带有访问底层数组的get和set方法。改变数组大小的所有方法（例如，与迭代器有关的add和remove方法）都会抛出一个Unsupported OperationException异常。
从Java SE 5.0开始，asList方法声明为一个具有可变数量参数的方法。除了可以传递一个数组之外，还可以将各个元素直接传递给这个方法。
如果调用下列方法Collections.singleton(anObject)则将返回一个视图对象。这个对象实现了Set接口（与产生List的ncopies方法不同）。返回的对象实现了一个不可修改的单元素集，而不需要付出建立数据结构的开销。singletonList方法与singletomMap方法类似。
子范围
可以为很多集合建立子范围（subrange）视图。可以使用subList方法来获得一个列表的子范围视图。
可以将任何操作应用于子范围，并且能够自动地反映整个列表的情况。
对于有序集和映射集，可以使用排序顺序而不是元素位置建立子范围。SortedSet接口声明了3个方法：
SortedSet< E > subSet(E from,E to)
SortedSet< E > headSet(E to)
SortedSet< E > tailSet(E from)
这些方法将返回大于等于from且小于to的所有元素子集。有序映射表也有类似的方法：
SortedMap< K,V > subMap(K from,K to)
SortedMap< K,V > headMap(K to)
SortedMap< K,V > tailMap(K from)
返回映射表视图，该映射表包含键落在指定范围内的所有元素。
Java SE 6引入的NavigableSet接口赋予自返回操作更多的控制能力。可以指定是否包括边界：
NavigableSet< E > subSet(E from, boolean fromInclusive,E to,boolean toInclusive)
NavigableSet< E > headSet(E to,boolean toInclusive)
Navigable< E > tailSet(E from,boolean fromInclusive)
不可修改的视图
Collections还有几个方法，用于产生集合的不可修改视图（unmodifiable views）。这些视图对现有集合曾姐了一个运行时的检查。如果发现视图对集合进行修改，就抛出一个异常，同时这个集合将保持未修改的状态。
可以使用下面6中方法获得不可修改视图：
Collections.unmodifiableCollection
Collections.unmodifiableList
Collections.unmodifianleSet
Collections.unmodifiableSortedSet
Collections.unmodifiableMap
Collections.unmodifiableSortedMap
每个方法都定义于一个接口。例如，Collections.unmodifiableList与ArrayList、LInkedList或者任何实现了List接口的其他类一起协同工作。
lookAt方法可以调用List接口中的所有方法，而不只是访问器。但是所有的更改器方法（例如，add）已经被重新定位为抛出一个UnsupportedOperationException异常，而不是将调用传递给底层集合。
不可修改视图并不是集合本身不可修改。仍然可以通过集合的原始引用对集合进行修改。并且仍然可以让集合的元素调用更改器方法。
由于视图只是包装了接口而不是实际的集合对象，所以只能访问接口中定义的方法。例如，LinkedList类有一些非常方便的方法，addFirst和addLast，它们都不是List接口的方法，不能通过不可修改视图进行访问。
unmodifiableCollection方法将返回一个集合，它的equals方法不调用底层集合的queals方法。相反，它继承了Object类的equals方法，这个方法只是检测两个对象是否是同一个对象。如果将集或列表转换成集合，就再也无法检测其内容是否相同了。视图就是以这种方式运行的，因为内容是否相等的检测在分层结构的这一层上没有定义妥当。然而，unmodifiableSet类和unmodifiableList类却使用底层集合的queals方法和hashCode方法。
同步视图
如果由多个线程访问集合，就必须确保集不会被意外地破坏。类库的设计者使用视图机制来确保常规集合的线程安全，而不是实现线程安全的集合类。例如，Collections类的静态synchronizedMap方法可以将任何一个隐射表转换成具有同步访问方法的Map。现在，就可以由多线程访问map对象了。像get和put这类方法都是串行操作的，即在另一个线程调用另一个方法之前，刚才的方法调用必须彻底完成。
List<String> safeStrings = Collections.checkedList(strings,String.class);视图的add方法将检测插入的对象是否属于给定的类，如果不属于给定的类，就立即抛出一个ClassCastException。这样做的好处是错误可以在正确的位置得以报告。关于可选操作的说明
通常，视图有一些局限性，即可能只可以读、无法改变大小、只支持删除而不支持插入，这些与映射表的键视图情况相同。如果试图进行不恰当的操作，受限制的视图就会抛出一个UnsupportedOperationException。
在集合和迭代器接口的API文档中，许多方法描述为“可选操作”。
是否应该将“可选”方法这一技术扩展到用户的设计中呢？不应该。集合类库的设计者必须解决一组特别严格且又相互冲突的需求。用户希望类库应该易于学习、使用方便，彻底泛型化，面向通用性，同时又与手写算法一样高效。要同时达到所有目标的要求，或者尽量兼顾所有目标完全是不可能的。但是，在自己的编程问题中，很少遇到这样极端的局限性。应该能够找到一种不必依靠极端衡量“可选的”接口操作来解决这类问题的方案。
java.util.Collections 1.2
java.util.List< E > 1.2
java.util.SortedSet< E > 1.2
java.uril.NavigableSet< E > 6
java.util.SortedMap< K,V > 1.2
java.util.NavigableMap< K,V > 6
可以使用类库中的批操作（bulk operation）避免频繁地使用迭代器。
通过使用一个子范围视图，可以将批处理限制于子列表和子集的操作上。
如果有一个数组需要转换为集合。Arrays.asList的包装器就可以实现这个目的。
由toArray方法返回的数组是一个Object[]数组，无法改变其类型。相反，必须使用另外一种toArray方法，并将其设计为所希望的元素类型且长度为0 的数组。随后返回的数组将与所创建的数组一样。
为什么不直接将一个Class对象传递给toArray方法。其原因是这个方法具有“双重职责”，不仅要填充已有的数组（如果足够长），还要创建一个新数组。
Collections类中的sort方法可以对实现了List接口的集合进行排序。这个方法假定列表元素实现了Comparable接口。如果想采用其他方式对列表进行排序，可以将Compaator对象作为第二个参数传递给sort方法。
如果想按照降序对列表进行排序，可以使用一种非常方便的静态方法Collections.reverseOrder()。这个方法将返回一个比较器，比较器则返回b.compareTo(a)。这个方法将根据元素类型的compareTo方法给定排序顺序。
集合类库中使用的归并算法比快速排序要慢一些，快速排序是通用排序算法的传统选择。但是，归并排序有一个主要的优点：稳定，即不需要交换相同的元素。
列表必须是可修改的，但不必是可以改变大小的。下面是有关的术语定义：
Collections类的binarySearch方法实现了二分查找算法。如果binarySearch方法返回的数值大于等于0，则表示匹配对象的索引。如果但会负值，则表示没有匹配的元素，但是，可以利用返回值计算应该将element插入到集合的哪个位置，以保证集合的有序性。插入的位置是（-i-1）。
binarySearch方法检查列表参数是否实现了RandomAccess接口。如果实现了这个接口，这个方法将采用二分查找；否则，将采用线性查找。
java.util.Collections 1.2
遗留集合使用Enumeration接口对元素序列进行遍历。Enumeration接口有两个方法，即hasMoreElements和nextEments。这两个方法与Iterator接口的hasNext方法next方法十分类似。
静态方法Collections.enumeration将产生一个枚举对象，枚举集合中的元素。
java.util.Enumeration< E > 1.0
java.util.Hashtable< K,V > 1.0
java.util.Vector< E > 1.0
属性映射表（property map）是一个类型非常特殊的映射表结构。它有下面3个特性：
java.util.Properties 1.0
从1.0版开始，标准库中就包含了Stack类，其中有push方法和pop方法。但是，Stack类扩展了Vector类，从理论角度看，Vector类并不太令人满意，它可以让栈使用不属于栈操作的insert和remove方法，即可以在任何方法进行插入或删除操作，而不仅仅是在栈顶。
java.util.Stack< E > 1.0
Java平台的BieSet类用于存放一个位序列（它不是数学上的集，称为位向量或位数组更为合适）。如果需要高效地存放位序列（例如，标志）就可以使用位集。由于位集将位包装在字节里，所以，使用位集要比使用Boolean对象的ArrayList更加高效。
BitSet类提供了一个便于读取、设置或清除各个位的接口。使用这个接口可以避免屏蔽和其他麻烦的位操作。如果将这些位存储在int或long变量中就必须进行这些繁琐的操作。
java.util.BitSet 1.0
原文：https://www.cnblogs.com/zhangmiao14/p/9931882.html