Java 集合类库

java类库的基本结构

Iterable

public interface Iterable<T>

实现这个接口允许对象成为 "foreach" 语句的目标。

也就是说，只有实现了Iterable接口的类才能使用foreache语法。

其实java在编译的时候讲foreach编译成了iterator操作。

方法摘要
Iterator<T>	iterator() 返回一个在一组 T 类型的元素上进行迭代的迭代器。

Collection

接口 Collection<E>

所有超级接口：

Iterable<E>

方法摘要

boolean

add(E o)
确保此 collection 包含指定的元素（可选操作）

boolean

addAll(Collection<? extends E> c)
将指定 collection 中的所有元素都添加到此 collection 中（可选操作）。

void

clear()
移除此 collection 中的所有元素（可选操作）。

boolean

contains(Object o)
如果此 collection 包含指定的元素，则返回 true。

boolean

containsAll(Collection<?> c)
如果此 collection 包含指定 collection 中的所有元素，则返回 true。

boolean

equals(Object o)
比较此 collection 与指定对象是否相等。

int

hashCode()
返回此 collection 的哈希码值。

boolean

isEmpty()
如果此 collection 不包含元素，则返回 true。

Iterator<E>

iterator()
返回在此 collection 的元素上进行迭代的迭代器。

boolean

remove(Object o)
从此 collection 中移除指定元素的单个实例，如果存在的话（可选操作）。

boolean

removeAll(Collection<?> c)
移除此 collection 中那些也包含在指定 collection 中的所有元素（可选操作）。

boolean

retainAll(Collection<?> c)
仅保留此 collection 中那些也包含在指定 collection 的元素（可选操作）。

int

size()
返回此 collection 中的元素数。

Object[]

toArray()
返回包含此 collection 中所有元素的数组。

<T> T[]

toArray(T[] a)
返回包含此 collection 中所有元素的数组；返回数组的运行时类型与指定数组的运行时类型相同。

Iterator

对集合进行迭代的迭代器。迭代器代替了 Java Collections Framework 中的 Enumeration。迭代器与枚举有两点不同：

迭代器允许调用方利用定义良好的语义在迭代期间从迭代器所指向的集合移除元素。

方法名称得到了改进。

java.util
接口 Iterator<E>

所有已知子接口：

ListIterator<E>

方法摘要
boolean	hasNext() 如果仍有元素可以迭代，则返回 true。
E	next() 返回迭代的下一个元素。
void	remove() 从迭代器指向的集合中移除迭代器返回的最后一个元素（可选操作）。每次调用 next 只能调用一次此方法。如果进行迭代时用调用此方法之外的其他方式修改了该迭代器所指向的集合，则迭代器的行为是不明确的。

List

有序的 collection（也称为序列）。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。

List 接口提供了特殊的迭代器，称为 ListIterator，除了允许 Iterator 接口提供的正常操作外，该迭代器还允许元素插入和替换，以及双向访问。还提供了一个方法来获取从列表中指定位置开始的列表迭代器。

注意：标注扩展的是，List扩展的。其他的是继承自Collection的。

方法摘要

boolean

add(E o)
向列表的尾部追加指定的元素（可选操作）。

void

add(int index, E element)
在列表的指定位置插入指定元素（可选操作）。扩展

boolean

addAll(Collection<? extends E> c)
追加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序（可选操作）。

boolean

addAll(int index, Collection<? extends E> c)
将指定 collection 中的所有元素都插入到列表中的指定位置（可选操作）。扩展

void

clear()
从列表中移除所有元素（可选操作）。

boolean

contains(Object o)
如果列表包含指定的元素，则返回 true。

boolean

containsAll(Collection<?> c)
如果列表包含指定 collection 的所有元素，则返回 true。

boolean

equals(Object o)
比较指定的对象与列表是否相等。

get(int index)
返回列表中指定位置的元素。扩展

int

hashCode()
返回列表的哈希码值。

返回列表的哈希码值。列表的哈希码定义为以下计算的结果：

hashCode = 1;

Iterator i = list.iterator();

while (i.hasNext()) {

Object obj = i.next();

hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());

}

这确保了 list1.equals(list2) 意味着对于任何两个列表 list1 和 list2 而言，可实现 list1.hashCode()==list2.hashCode()，正如 Object.hashCode 的常规协定所要求的。

int

indexOf(Object o)
返回列表中首次出现指定元素的索引，如果列表不包含此元素，则返回 -1。扩展

返回列表中首次出现指定元素的索引，如果列表不包含此元素，则返回 -1。更正式地说，返回满足下面条件的最低索引 i：(o==null ? get(i)==null :o.equals(get(i)))，如果没有这样的索引，则返回 -1。

boolean

isEmpty()
如果列表不包含元素，则返回 true。

Iterator<E>

iterator()
返回以正确顺序在列表的元素上进行迭代的迭代器。

int

lastIndexOf(Object o)
返回列表中最后出现指定元素的索引，如果列表不包含此元素，则返回 -1。扩展

ListIterator<E>

listIterator()
返回列表中元素的列表迭代器（以正确的顺序）。扩展

ListIterator<E>

listIterator(int index)
返回列表中元素的列表迭代器（以正确的顺序），从列表的指定位置开始。扩展

remove(int index)
移除列表中指定位置的元素（可选操作）。扩展

boolean

remove(Object o)
移除列表中出现的首个指定元素（可选操作）。

boolean

removeAll(Collection<?> c)
从列表中移除指定 collection 中包含的所有元素（可选操作）。

boolean

retainAll(Collection<?> c)
仅在列表中保留指定 collection 中所包含的元素（可选操作）。

set(int index, E element)
用指定元素替换列表中指定位置的元素（可选操作）。扩展

int

size()
返回列表中的元素数。

List<E>

subList(int fromIndex, int toIndex)
返回列表中指定的 fromIndex（包括）和 toIndex（不包括）之间的部分视图。扩展

Object[]

toArray()
返回以正确顺序包含列表中的所有元素的数组。

<T> T[]

toArray(T[] a)
返回以正确顺序包含列表中所有元素的数组；返回数组的运行时类型是指定数组的运行时类型。

Queue

java.util
接口 Queue<E>

所有超级接口：

Collection<E>, Iterable<E>

所有已知子接口：

BlockingQueue<E>

所有已知实现类：

AbstractQueue, ArrayBlockingQueue, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingQueue, LinkedList, PriorityBlockingQueue, PriorityQueue, SynchronousQueue

队列通常（但并非一定）以 FIFO（先进先出）的方式排序各个元素。不过优先级队列和 LIFO 队列（或堆栈）例外，前者根据提供的比较器或元素的自然顺序对元素进行排序，后者按 LIFO（后进先出）的方式对元素进行排序。无论使用哪种排序方式，队列的头都是调用 remove() 或 poll() 所移除的元素。在 FIFO 队列中，所有的新元素都插入队列的末尾。其他种类的队列可能使用不同的元素放置规则。每个 Queue 实现必须指定其顺序属性。

也就是说，不管是先进先出还是后进先出，我们不需要考虑从头部还是从尾部取出数据，数据时在插入的时候排好序的，如果是先进先出那么插入在尾部，如果是后进先出，那么就插入在头部。我们使用queue只需要定义了合适的类，然后每次都是从头部取数据的。

这三个是普通Queue的实现类：

LinkedList是将数据插入在尾部的，所以它是先进先出的。

PriorityQueue是根据优先级来插入到相应的位置，它的内部实现是一个可以自我调整的二叉树。

ConcurrentLinkedQueue是并发安全的LinkedQueue

其他的：ArrayBlockingQueue, DelayQueue, LinkedBlockingQueue, PriorityBlockingQueue, SynchronousQueue都是BlockingQueue的实现类。分别实现有界，无界，延时，优先级等阻塞队列。

插入操作：

add和offer

add插入失败会报错，offer插入失败会返回false。比如，对于有界的队列。

取出操作：

remove() 和 poll() 方法可移除和返回队列的头。

remove() 和 poll() 方法仅在队列为空时其行为有所不同：remove() 方法抛出一个异常，而 poll() 方法则返回 null。

element() 和 peek() 返回，但不移除队列的头。

element () 和 peek () 方法仅在队列为空时其行为有所不同：element () 方法抛出一个异常，而 peek () 方法则返回 null。

Queue 接口并未定义阻塞队列的方法，而这在并发编程中是很常见的。BlockingQueue 接口定义了那些等待元素出现或等待队列中有可用空间的方法，这些方法扩展了此接口。

Queue 实现通常不允许插入 null 元素，尽管某些实现（如 LinkedList）并不禁止插入 null。即使在允许 null 的实现中，也不应该将 null 插入到 Queue 中，因为 null 也用作 poll 方法的一个特殊返回值，表明队列不包含元素。

方法摘要
E	element() 检索，但是不移除此队列的头。
boolean	offer(E o) 如果可能，将指定的元素插入此队列。
E	peek() 检索，但是不移除此队列的头，如果此队列为空，则返回 null。
E	poll() 检索并移除此队列的头，如果此队列为空，则返回 null。
E	remove() 检索并移除此队列的头。
从接口 java.util.Collection 继承的方法
add, addAll, clear, contains, containsAll, equals, hashCode, isEmpty, iterator, remove, removeAll, retainAll, size, toArray, toArray

堆栈

堆栈是一种后进先出的结构，最早的时候Java是使用Stack类来实现的。不过这个是继承自Vector，是线程安全的。设计不合理。所以不适用。

可以使用java.util.Deque接口来实现后进先出，他是一个双端队列，支持在头尾分别插入和取出数据。我们保证在头部插入，头部取出，就是一个堆栈了。

LinkedList是Deque的实现。

ListIterator

方法摘要
void	add(E o) 将指定的元素插入列表（可选操作）。扩展
boolean	hasNext() 以正向遍历列表时，如果列表迭代器有多个元素，则返回 true（换句话说，如果 next 返回一个元素而不是抛出异常，则返回 true）。
boolean	hasPrevious() 如果以反向遍历列表，列表迭代器有多个元素，则返回 true。扩展
E	next() 返回列表中的下一个元素。
int	nextIndex() 返回对 next 的后续调用所返回元素的索引。扩展
E	previous() 返回列表中的前一个元素。扩展
int	previousIndex() 返回对 previous 的后续调用所返回元素的索引。扩展
void	remove() 从列表中移除由 next 或 previous 返回的最后一个元素（可选操作）。
void	set(E o) 用指定元素替换 next 或 previous 返回的最后一个元素（可选操作）。扩展

LinkedList

java.util
类 LinkedList<E>

所有已实现的接口：

Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>, Queue<E>

List 接口的链接列表实现。

此类也实现 Queue 接口，为 add、poll 等提供先进先出队列操作。其他堆栈和双端队列操作可以根据标准列表操作方便地进行再次强制转换。虽然它们可能比等效列表操作运行稍快，但是将其包括在这里主要是出于方便考虑。

所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）（指get操作，get操作可以根据传入的index决定从头部还是尾部开始检查找因为链表只能从头尾开始所以要对LinkedList慎用get 因为每次都是从头尾开始查找的如果要遍历全部即使使用for循环也是每次都是从头尾开始要使用iterator）。

此类的 iterator 和 listIterator 方法返回的迭代器是快速失败的：在迭代器创建之后，如果从结构上对列表进行修改，除非通过迭代器自身的 remove 或 add 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒将来不确定的时间任意发生不确定行为的风险。

方法列表：注意，如果既不是List接口也不是Queue接口的方法，这里将标注扩展。

方法摘要

boolean

add(E o)
将指定元素追加到此列表的结尾。

void

add(int index, E element)
在此列表中指定的位置插入指定的元素。

boolean

addAll(Collection<? extends E> c)
追加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序。

boolean

addAll(int index, Collection<? extends E> c)
将指定集合中的所有元素从指定位置开始插入此列表。

void

addFirst(E o)
将给定元素插入此列表的开头。扩展

void

addLast(E o)
将给定元素追加到此列表的结尾。扩展

void

clear()
从此列表中移除所有元素。

Object

clone()
返回此 LinkedList 的浅表复制。

boolean

contains(Object o)
如果此列表包含指定元素，则返回 true。

element()
找到但不移除此列表的头（第一个元素）。

get(int index)
返回此列表中指定位置处的元素。

getFirst()
返回此列表的第一个元素。扩展

getLast()
返回此列表的最后一个元素。扩展

int

indexOf(Object o)
返回此列表中首次出现的指定元素的索引，如果列表中不包含此元素，则返回 -1。

int

lastIndexOf(Object o)
返回此列表中最后出现的指定元素的索引，如果列表中不包含此元素，则返回 -1。

ListIterator<E>

listIterator(int index)
返回此列表中的元素的列表迭代器（按适当顺序），从列表中指定位置开始。

boolean

offer(E o)
将指定元素添加到此列表的末尾（最后一个元素）。

peek()
找到但不移除此列表的头（第一个元素）。

poll()
找到并移除此列表的头（第一个元素）。

remove()
找到并移除此列表的头（第一个元素）。

remove(int index)
移除此列表中指定位置处的元素。

boolean

remove(Object o)
移除此列表中首次出现的指定元素。

removeFirst()
移除并返回此列表的第一个元素。扩展

removeLast()
移除并返回此列表的最后一个元素。扩展

set(int index, E element)
将此列表中指定位置的元素替换为指定的元素。

int

size()
返回此列表的元素数。

Object[]

toArray()
以正确顺序返回包含此列表中所有元素的数组。

<T> T[]

toArray(T[] a)
以正确顺序返回包含此列表中所有元素的数组；返回数组的运行时类型即为指定数组的类型。

ArrayList

ArrayList 只实现了List接口，没有实现Queue。

List 接口的大小可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。（此类大致上等同于 Vector 类，除了此类是不同步的。）

在添加大量元素前，应用程序可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。

此类的 iterator 和 listIterator 方法返回的迭代器是快速失败的：在创建迭代器之后，除非通过迭代器自身的 remove 或 add 方法从结构上对列表进行修改，否则在任何时间以任何方式对列表进行修改，迭代器都会抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

时间复杂度：

数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)。

链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但查找的时间复杂度很大，达O（N）。

HashSet（散列集）

此类实现 Set 接口，由哈希表（实际上是一个 HashMap 实例）支持。它不保证集合的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用 null 元素。

参考HashMap，因为HashSet是HashMap的一个实例。

构造方法摘要
HashSet() 构造一个新的空集合，其底层 HashMap 实例的默认初始容量是 16，加载因子是 0.75。
HashSet(Collection<? extends E> c) 构造一个包含指定 collection 中的元素的新 set。
HashSet(int initialCapacity) 构造一个新的空集合，其底层 HashMap 实例具有指定的初始容量和默认的加载因子（0.75）。
HashSet(int initialCapacity, float loadFactor) 构造一个新的空集合，其底层 HashMap 实例具有指定的初始容量和指定的加载因子。

注意：如果对HashSet进行迭代，那么结果的排序规则可以看成是随机的。不可控的。

TreeSet（树集）

此类实现 Set 接口，由 TreeMap 实例支持。此类保证排序后的 set 按照升序排列元素，根据使用的构造方法不同，可能会按照元素的自然顺序进行排序（参见 Comparable），或按照在创建 set 时所提供的比较器进行排序。

此实现为基本操作（add、remove 和 contains）提供了可保证的 log(n) 时间开销。如总共有1000个元素，那么这些操作大约需要10次。

TreeSet是有序集合，不论插入的顺序如何，取出的都是排好序的。

TreeSet对元素的排序和存储依赖于Comparable接口。

TreeSet只用到Comparable，不会用到equals。所以没有要求compareTo的结果要和equals保持一致。

应该选择散列还是树？

散列的速度回比较快，不管是增加删除还是查找，所以如果是不考虑排序的因素，优先使用散列。这个结论对Set和Map都适用。

PriorityQueue

一个基于优先级堆的极大优先级队列。此队列按照在构造时所指定的顺序对元素排序，既可以根据元素的自然顺序来指定排序（参阅 Comparable），也可以根据 Comparator 来指定，这取决于使用哪种构造方法。优先级队列不允许 null 元素。依靠自然排序的优先级队列还不允许插入不可比较的对象（这样做可能导致 ClassCastException）。

此队列的头是按指定排序方式的最小元素。如果多个元素都是最小值，则头是其中一个元素——选择方法是任意的。队列检索操作 poll、remove、peek 和 element 访问处于队列头的元素。

优先级队列是无界的，但是有一个内部容量，控制着用于存储队列元素的数组的大小。它总是至少与队列的大小相同。随着不断向优先级队列添加元素，其容量会自动增加。无需指定容量增加策略的细节。

优先级队列使用了一种高级而优雅的数据结构，称为堆（heap）。堆是一个可以自我调整的二叉树。对树执行添加和删除操作，可以让最小的元素移动到根节点，而不必花费时间去排序。

Map

将键映射到值的对象。一个映射不能包含重复的键；每个键最多只能映射一个值。

注：将可变对象用作映射键时必须格外小心。当对象是映射中某个键时，如果以影响 equals 比较的方式更改了对象的值，则映射的行为就不是特定的。此项禁止的一个特殊情况是不允许某个映射包含其自身作为键。

Map的key的equals方法和hashCode非常重要，如果两个对象equals，那么他们的hashCode也要一样。

keyset和entrySet既不是HashSet，也不是TreeSet，而是一个实现了Set接口的其他类。该 set 受Map支持，所以对Map的改变可在此 set 中反映出来，反之亦然。如果修改Map的同时正在对该 set 进行迭代（除了通过迭代器自己的 remove 操作外），则迭代结果是不明确的。set 支持通过 Iterator.remove、Set.remove、removeAll retainAll 和 clear 操作实现元素移除，即从Map中移除相应的Key-Value关系。它不支持 add 或 addAll 操作。

HashMap（散列表）

在java中，散列表用链表数组实现。每个链表被称为桶。想要查找表中对象的位置，就要先计算它的散列码，然后与桶的总数求余，得到的结果就是保存这个元素的桶的索引。如：如果某个对象的散列码是76768，总共有128个桶，那么对象就保存在第108号桶，如果这个时候这个桶被沾满了，就会出现"散列冲突"。（这个地方不理解，链表的空间没有限制才对）

在插入之前，还需要将新对象与对应的桶中已有的对象进行比较，确认这个对象是否已经存在。

如果想要控制散列表的运行性能，应该指定一个初始的桶数。通常，将桶数设置为预计元素个数的75%-150%。

HashMap 的实例有两个参数影响其性能：初始容量和加载因子。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，通过调用 rehash 方法将容量翻倍。

通常，默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地降低 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。

HashMap使用的桶是2的幂，默认为16。

如果对HashMap进行迭代，那么结果的排序规则可以看成是随机的。不可控的。

构造方法摘要
HashMap() 构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity) 构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity, float loadFactor) 构造一个带指定初始容量和加载因子的空 HashMap。
方法摘要
void		clear() 从此映射中移除所有映射关系。
Object		clone() 返回此 HashMap 实例的浅表复制：并不克隆键和值本身。
boolean		containsKey(Object key) 如果此映射包含对于指定的键的映射关系，则返回 true。
boolean		containsValue(Object value) 如果此映射将一个或多个键映射到指定值，则返回 true。
Set<Map.Entry<K,V>>		entrySet() 返回此映射所包含的映射关系的 collection 视图。
V		get(Object key) 返回指定键在此标识哈希映射中所映射的值，如果对于此键来说，映射不包含任何映射关系，则返回 null。
boolean		isEmpty() 如果此映射不包含键-值映射关系，则返回 true。
Set<K>		keySet() 返回此映射中所包含的键的 set 视图。
V		put(K key, V value) 在此映射中关联指定值与指定键。
void		putAll(Map<? extends K,? extends V> m) 将指定映射的所有映射关系复制到此映射中，这些映射关系将替换此映射目前针对指定映射的所有键的所有映射关系。
V		remove(Object key) 如果此映射中存在该键的映射关系，则将其删除。
int		size() 返回此映射中的键-值映射关系数。
Collection<V>		values() 返回此映射所包含的值的 collection 视图。

TreeMap

没有什么可说的了。

都在TreeSet中说了。

LinkedHashMap和LinkedHashSet

LinkedHashMap是Map 接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现与 HashMap 的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序通常就是将键插入到映射中的顺序（插入顺序）。注意，如果在映射中重新插入 键，则插入顺序不受影响。

提供特殊的构造方法（通过accessOrder属性）来创建链接哈希映射，该哈希映射的迭代顺序就是最后访问其条目的顺序，从近期访问最少到近期访问最多的顺序（访问顺序）。这种映射很适合构建 LRU 缓存。调用 put 或 get 方法将会访问相应的条目（假定调用完成后它还存在）。

视图与包装器

比如Map的keySet，看似返回了一个新的集合，其实返回的是一个包装的对象，对这个对象的操作直接映射到元Map的数据。

Arrays. asList(T[])

返回一个受指定数组支持的固定大小的列表。对返回列表的更改会"直写"到数组。(此方法同 Collection.toArray 一起，充当了基于数组的 API 与基于 collection 的 API 之间的桥梁)。

List. subList (int fromIndex,int toIndex)

返回列表中指定的 fromIndex（包括）和 toIndex（不包括）之间的部分视图。（如果 fromIndex 和 toIndex 相等，则返回的列表为空）。返回的列表由此列表支持，因此返回列表中的非结构性更改将反映在此列表中，反之亦然。(从结构上修改是指更改列表的大小)(那就是说只能获取和修改，不能删除和增加)

还有一个类似的视图，如下：

TreeSet. subSet(E from ,E to)

TreeSet. headSet(E to)

TreeSet. tailSet(E from)

TreeMap subMap(E from ,E to)

TreeMap headMap(E to)

TreeMap tailMap(E from)

不可修改的视图

可以使用下列6种方法获得不可修改视图：

Collections.unmodifiableCollection

Collections.unmodifiableList

Collections.unmodifiableSet

Collections.unmodifiableSortedSet

Collections.unmodifiableMap

Collections.unmodifiableSortedMap

举例：

Collections.unmodifiableList返回指定列表的不可修改视图。此方法允许使用模块，为用户提供对内部列表的"只读"访问。在返回的列表上执行的查询操作将"读完"指定的列表。试图修改返回的列表，不管是直接修改还是通过其迭代器进行修改，都将导致抛出 UnsupportedOperationException。

同步视图

同样是使用 Collections 类的静态 synchronized..方法

如Collections 类的静态 synchronizedMap 方法将任何一个映射表转换成具有同步访问方法的 Map

集合与数组间的转换

数组转换为集合： Arrays.asList 的包装器提供了这个功能：

HashSet<String> numbers = new HashSet<String>(Arrays.asList(new String[]{"1", "7", "6"}));

集合转换为数组：toArray（）

toArray

Object[] toArray()

这个方法返回的是Object[]类型，即使你把一个List<string>使用它来装换，转换后的结果也不能强转换为String[]型的。

toArray <T> T[] toArray(T[] a)

像 toArray 方法一样，此方法充当了基于数组的 API 与基于 collection 的 API 之间的桥梁。更进一步说，此方法允许在输出数组的运行时类型上进行精确控制，并且在某些情况下，可以用来节省分配开销。

假定 l 是只包含字符串的一个已知 List。以下代码用来将该列表转储到一个新分配的 String 数组：

String[] x = (String[]) v.toArray(new String[0]);

注意，toArray(new Object[0]) 和 toArray() 在功能上是相同的。

排序与混排

Collections.sort

public static <T extends Comparable<? super T>> void sort(List<T> list)

根据元素的自然顺序对指定列表按升序进行排序。列表中的所有元素都必须实现 Comparable 接口。此排序被保证是稳定的：不会因调用 sort 方法而对相等的元素进行重新排序。

指定列表必须是可修改的，但不必是大小可调整的。

该排序算法是一个经过修改的合并排序算法（其中，如果低子列表中的最高元素小于高子列表中的最低元素，则忽略合并）。此算法提供可保证的 n log(n) 性能。此实现将指定列表转储到一个数组中，并对数组进行排序，在重置数组中相应位置处每个元素的列表上进行迭代。这避免了由于试图对适当位置上的链接列表进行排序而产生的 n2 log(n) 性能。

关于合并排序算法的大概实现：

sort(a)方法：

{

将数组评分a1和a2

调用sort(a1)(进入了递归)

调用sort(a2)(进入了递归)

merge(a1,a2) 这里的a1 a2 已经是排序好的所以merge它们只需要循环的比较a1 a2的第一个元素就可以了

}

因为merge有序数列的效率是比较高的，可以达到O(n)，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)。

详细参考：http://www.cnblogs.com/yangecnu/p/Introduce-Merge-Sort.html

几种常见的排序算法：

冒泡排序算法：http://blog.csdn.net/cbs612537/article/details/8294960/

设有一数组，其大小为10个元素（int str[10]）数组内的数据是无序。现在要求我们通过编程将这个无序的数组变成一个从小到大排序的数组（从下标为0开始）

首先，把10个数里最小的个数放到下标为0的位置上（str[0]）
通过将下标为0的数（str[0]）与剩下其余9个数进行对比交换（将较少者放置在下标为0的位置上），就可以得到这10个数最小的那个
10个数最小的那位确定后，接下来就要找剩下9个数最小的那个。
因为已经确定出一个最小的数，所以就不要动str[0]，直接从str[1]开始，与剩下的8个数对比交换，找出9个数中最小的那位放到下标为1（str[1]）的位置上
继续按照这个思路就可以将这十个数变成有序的（从小到大）的数组

冒泡排序最坏情况的时间复杂度是O(n²)

快速排序算法

快速排序由于排序效率同为O(N*logN)。

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

该方法的基本思想是：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

代码实现：

/*
* 排序的核心算法
*
* @param array
* 待排序数组
* @param startIndex
* 开始位置
* @param endIndex
* 结束位置
*/
private void sortCore(int[] array, int startIndex, int endIndex) {
if (startIndex >= endIndex) {
return;
}
int boundary = boundary(array, startIndex, endIndex);
sortCore(array, startIndex, boundary - 1);
sortCore(array, boundary + 1, endIndex);
}
/*
* 交换并返回分界点
*
* @param array
* 待排序数组
* @param startIndex
* 开始位置
* @param endIndex
* 结束位置
* @return
* 分界点
*/
private int boundary(int[] array, int startIndex, int endIndex) {
int standard = array[startIndex]; // 定义标准
int leftIndex = startIndex; // 左指针
int rightIndex = endIndex; // 右指针
while(leftIndex < rightIndex) {
while(leftIndex < rightIndex && array[rightIndex] >= standard) {
rightIndex--;
}
array[leftIndex] = array[rightIndex];
while(leftIndex < rightIndex && array[leftIndex] <= standard) {
leftIndex++;
}
array[rightIndex] = array[leftIndex];
}
array[leftIndex] = standard;
return leftIndex;
}

参考：http://blog.csdn.net/lemon_tree12138/article/details/50622744

二分查找

使用二分搜索算法来搜索指定列表，以获得指定对象。在进行此调用之前，必须根据列表元素的自然顺序 对列表进行升序排序（通过上面的 sort(List) 方法）。如果没有对列表进行排序，则结果是不明确的。如果列表包含多个等于指定对象的元素，则无法保证找到的是哪一个。

此方法对"RandomAccess"的列表运行 log(n) 次（它提供了一个接近固定时间的位置访问）。如果指定列表没有实现 RandomAccess 接口并且是一个大型列表，将自动舍弃二分查找，使用线性查找。

RandomAccess：

List 实现所使用的标记接口，用来表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。

将操作随机访问列表的最佳算法（如 ArrayList）应用到连续访问列表（如 LinkedList）时，可产生二次项的行为。

Collections：

addAll(Collection<? super T> c, T... a)
将所有指定元素添加到指定 collection 中。

binarySearch(List<? extends Comparable<? super T>> list, T key)
使用二进制搜索算法来搜索指定列表，以获得指定对象。

binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
使用二进制搜索算法来搜索指定列表，以获得指定对象。

copy(List<? super T> dest, List<? extends T> src)
将所有元素从一个列表复制到另一个列表。

disjoint(Collection<?> c1, Collection<?> c2)
如果两个指定 collection 中没有相同的元素，则返回 true。

emptyList()
返回空的列表（不可变的）。

emptyMap()
返回空的映射（不可变的）。

emptySet()
返回空的 set（不可变的）。

fill(List<? super T> list, T obj)
使用指定元素替换指定列表中的所有元素。

frequency(Collection<?> c, Object o)
返回指定 collection 中等于指定对象的元素数。

indexOfSubList(List<?> source, List<?> target)
返回指定源列表中第一次出现指定目标列表的起始位置，如果没有出现这样的列表，则返回 -1。

lastIndexOfSubList(List<?> source, List<?> target)
返回指定源列表中最后一次出现指定目标列表的起始位置，如果没有出现这样的列表，则返回 -1。

max(Collection<? extends T> coll)
根据元素的自然顺序，返回给定 collection 的最大元素。

max(Collection<? extends T> coll, Comparator<? super T> comp)
根据指定比较器产生的顺序，返回给定 collection 的最大元素。

min(Collection<? extends T> coll)
根据元素的自然顺序返回给定 collection 的最小元素。

min(Collection<? extends T> coll, Comparator<? super T> comp)
根据指定比较器产生的顺序，返回给定 collection 的最小元素。

replaceAll(List<T> list, T oldVal, T newVal)
使用另一个值替换列表中出现的所有某一指定值。

reverse(List<?> list)
反转指定列表中元素的顺序。

reverseOrder()
返回一个比较器，它强行反转实现 Comparable 接口那些对象 collection 上的自然顺序。

reverseOrder(Comparator<T> cmp)
返回一个比较器，它强行反转指定比较器的顺序。

rotate(List<?> list, int distance)
根据指定的距离循环移动指定列表中的元素。

shuffle(List<?> list)
使用默认随机源随机更改指定列表的序列。

shuffle(List<?> list, Random rnd)
使用指定的随机源随机更改指定列表的序列。

sort(List<T> list)
根据元素的自然顺序对指定列表按升序进行排序。

sort(List<T> list, Comparator<? super T> c)
根据指定比较器产生的顺序对指定列表进行排序。

swap(List<?> list, int i, int j)
在指定列表的指定位置处交换元素。

synchronizedCollection(Collection<T> c)
返回由指定 collection 支持的同步（线程安全的）collection。

synchronizedList(List<T> list)
返回由指定列表支持的同步（线程安全的）列表。

synchronizedMap(Map<K,V> m)
返回由指定映射支持的同步（线程安全的）映射。

synchronizedSet(Set<T> s)
返回由指定 set 支持的同步（线程安全的）set。

synchronizedSortedMap(SortedMap<K,V> m)
返回由指定有序映射支持的同步（线程安全的）有序映射。

synchronizedSortedSet(SortedSet<T> s)
返回由指定有序 set 支持的同步（线程安全的）有序 set。

unmodifiableCollection(Collection<? extends T> c)
返回指定 collection 的不可修改视图。

unmodifiableList(List<? extends T> list)
返回指定列表的不可修改视图。

unmodifiableMap(Map<? extends K,? extends V> m)
返回指定映射的不可修改视图。

unmodifiableSet(Set<? extends T> s)
返回指定 set 的不可修改视图。

unmodifiableSortedMap(SortedMap<K,? extends V> m)
返回指定有序映射的不可修改视图。

unmodifiableSortedSet(SortedSet<T> s)
返回指定有序 set 的不可修改视图。