写在前面
自开始在公司实习以来，经常都要用到集合框架。不仅后台要用，在前台做数据交互的时候用得也多。所以我想着是时候深入地学习一下Java的集合框架，搞搞它们的源码了。
下面先把Java集合框架的结构图放出来(摘自《Thinking in Java》)：
其实呢，把上面的图提炼一下，Java集合框架的简略UML类图如下：
- Collection接口简要类图:
- Map接口简要类图:
PS:上面两个UML图真的画得非常非常简略，其实Collection和Map接口下面还有很多的子接口以及实现类，具体有哪些可以参照官方文档
Collection接口介绍
Collection接口继承自超级接口Iterator,是Collection层次结构中的根接口。Collection表示一组对象，这些对象也被称为Collection的元素。一些Collection允许有重复的元素（例如List），但是另一些则不允许有重复的元素，即可为无序的（如Set）。JDK不提供此接口的任何直接实现---它会提供更为具体的子接口(如Set和List),这从上面的UML也可以看出来。此接口用来传递Collection,并在需要最大普遍性的地方操作这些Collection。
- 关于构造方法
所有通用的Collection实现类(通常通过它的一个子接口间接实现Collection)应该提供两个"标准"构造方法：一个是使用void声明的构造方法，用于创建空Collection;另一个是带有Collection类型单参数的构造方法，用于创建一个具有与其参数相同元素的新的Collection。实际上，后者允许用户复制任何Collection,以生产所需实现类型的一个等效Collection。尽管无法强制执行此约定（因为接口不能包含构造方法），但是Java平台库中所有通用的Collection实现都遵从它。
为了验证是否如上所说的，我打开了ArrayList的源码来研究一下：
首先可以看到一个使用void声明的无参构造方法：
然后我们还看到了一个参数类型为Collection的构造方法:
由此可以看出上面那段话对于构造方法的描述是正确的。至于构造方法内部具体是如何实现的，等以后我再慢慢开博客来介绍。
- 关于破坏性方法
Collection接口中包含某些破坏性方法。破坏性方法，是指可以修改其所操作的Collection的那些方法。比如说某个破坏性方法的参数类型为Collection，即可以往里面传一个Collection实例，如果此方法可以修改这个Collection实例，那么它就是破坏性方法。如果这个被传入的collection不支持该操作，则指定这些方法抛出UnSupportedOperationException。如果是这样，那么在调用对该collection无效的时候，这些方法可能但不一定抛出UnSupportedOperationException。例如，如果要添加的collection为空并且不可修改，则在对该collection调用addAll(Collection)方法时，可能但不一定会抛出异常。
- 关于一些限制
一些collection实现对它们可能包含的元素有所限制。例如，某些实现禁止Null元素，而某些实现则对元素的类型有所限制。试图添加不合法的元素将抛出一个未经检查的异常，一般来说是NullPointerException或者是ClassCastException。试图查询是否存在不合格的元素也可能抛出一个异常，或者只是简单地返回false;某些不适合的实现将表现出前一种行为，即抛出一个异常，而某些实现则表现出后一种行为。较为常见的是，试图对某个不合法的元素执行操作且该操作的完成不会导致将不合法的元素插入collection中，将可能抛出一个异常，也可能操作成功。这取决于实现本身。这样的异常再次接口的规范中标记为"可选"
- 关于同步策略
这主要是由每个collection来确定自身的同步策略。在没有事先的强烈保证的情况之下，调用由另一进程正在更改的collection的方法可能会出现不确定行为;这包括直接调用，将collection传递给可能执行调用的方法，以及使用现有迭代器检查collection。
- 其它
Collections Frameword接口中的很多方法是根据equals方法定义的。例如，contain(Object o )方法的闺房声明：“当且仅当此collection包含至少一个满足(o == null ? e == null : o.equals(e))的元素e时，返回true。”不应将此规范理解为它暗指调用具有非空参数o的Collection.contains方法会导致任意的e元素调用o.equals(e)方法。可随意对各种实现执行优化，只要避免调用equals即可。例如，通过首先比较两个元素的哈希码（Object.hashCode()规范保证哈希码不相等的两个对象不会相等）。较为常见的是，各种Collections FrameWord接口的实现课随意利用底层Object方法的指定
Collection接口方法摘要：
偷个懒，直接把JDK文档里面的搬过来
方法详细信息：
size
int size()
返回此collection中的元素的数量。如果此collection包含的元素数量大于 Integer.MAX_VALUE,则返回Integer.MAX_VALUE。
返回：此collection中元素的数量
isEmpty
boolean isEmpty()
如果此collection不包含元素，则返回true。
返回：如果此collection不包含元素，则返回true
contains
boolean contains(Object o)
如果此collection包含指定的元素，则返回true。更确切地说，当且仅当此collection至少包含一个满足(o == null ? e == null :o. equals(e))的元素e时，返回true。
参数： o - 测试在此collection中是否存在的元素。
返回： 如果此collection包含指定的元素，则返回true。
抛出：
ClassCastException:如果指定元素的类型与此collection不兼容（可选）
NullPointerException:如果指定的元素为null,并且此collection不允许null元素（可选）
iterator
Iterator<E> iterator()
返回在此collection的元素上进行迭代的迭代器。关于元素返回的顺序没有任何保证，除非此collection是某个能提供保证顺序的类的实例。
制定者：接口Iterator<E>中的iterator
返回：在此collection的元素上进行迭代的Iterator
toArray
Object[] toArray()
返回包含此collection中所有元素的数组。如果collection对其迭代器返回的元素顺序做出了某些保证，那么此方法必须以相同的顺序返回这些元素。
返回的数组将是“安全地”，因此此collection并不维护对返回数组的任何引用。换句话说，即使collection受到数组的支持，此方法也必须分配一个新的数组，因此，调用者可以随意修改返回的数组。
此方法充当了基于数组的API与基于collection的API之间的桥梁。
返回：包含此collection中所有元素的数组
toArray
<T> T[] toArray(T[] a)
返回包含此 collection 中所有元素的数组；返回数组的运行时类型与指定数组的运行时类型相同。如果指定的数组能容纳该 collection，则返回包含此 collection 元素的数组。否则，将分配一个具有指定数组的运行时类型和此 collection 大小的新数组。
如果指定的数组能容纳 collection，并有剩余空间（即数组的元素比 collection 的元素多），那么会将数组中紧接 collection 尾部的元素设置为 null。（只有 在调用者知道此 collection 没有包含任何 null
元素时才能用此方法确定 collection 的长度。）
如果此 collection 对其迭代器返回的元素顺序做出了某些保证，那么此方法必须以相同的顺序返回这些元素。
像 toArray() 方法一样，此方法充当基于数组的 API 与基于 collection 的 API 之间的桥梁。更进一步说，此方法允许对输出数组的运行时类型进行精确控制，并且在某些情况下，可以用来节省分配开销。
假定 x是只包含字符串的一个已知 collection。以下代码用来将 collection 转储到一个新分配的 String数组：
String[] y = x.toArray(new String[0]);
注意，toArray(new Object[0])
和 toArray()
在功能上是相同的。
参数：
a
- 存储此 collection 元素的数组（如果其足够大）；否则，将为此分配一个具有相同运行时类型的新数组。
返回：
包含此 collection 中所有元素的数组
抛出：
ArrayStoreException- - 如果指定数组的运行时类型不是此 collection 每个元素运行时类型的超类型
NullPointerException - 如果指定的数组为 null
add
boolean add(E e)
确保此 collection 包含指定的元素（可选操作）。如果此 collection 由于调用而发生更改，则返回 true
。（如果此 collection 不允许有重复元素，并且已经包含了指定的元素，则返回 false
。）支持此操作的 collection 可以限制哪些元素能添加到此 collection 中来。需要特别指出的是，一些 collection 拒绝添加 null
元素，其他一些 collection 将对可以添加的元素类型强加限制。Collection 类应该在其文档中清楚地指定能添加哪些元素方面的所有限制。
如果 collection 由于某些原因（已经包含该元素的原因除外）拒绝添加特定的元素，那么它必须 抛出一个异常（而不是返回 false
）。这确保了在此调用返回后，collection 总是包含指定的元素。
参数：
e
- 确定此 collection 中是否存在的元素。
返回：
如果此 collection 由于调用而发生更改，则返回true
抛出：
UnsupportedOperationException
- 如果此 collection 不支持 add
操作
ClassCastException - 如果指定元素的类不允许它添加到此 collection 中
NullPointerException - 如果指定的元素为 null，并且此 collection 不允许 null 元素
IllegalArgumentException - 如果元素的某属性不允许它添加到此 collection 中
IllegalStateException - 如果由于插入限制，元素不能在此时间添加
remove
boolean remove(Object o )
从此 collection 中移除指定元素的单个实例，如果存在的话（可选操作）。更确切地讲，如果此 collection 包含一个或多个满足 (o==null ? e==null : o.equals(e))
的元素 e
，则移除这样的元素。如果此 collection 包含指定的元素（或者此 collection 由于调用而发生更改），则返回 true
。
参数：
o
- 要从此 collection 中移除的元素（如果存在）。
返回：
如果此调用将移除一个元素，则返回 true
抛出：
ClassCastException
- 如果指定元素的类型与此 collection 不兼容（可选）
NullPointerException - 如果指定的元素为 null，并且此 collection 不允许 null 元素（可选）。
UnsupportedOperationException - 如果此 collection 不支持 remove
操作
containsAll
boolean containsAll(Collection<?> c)
如果此 collection 包含指定 collection 中的所有元素，则返回 true
。
参数：
c
- 将检查是否包含在此 collection 中的 collection
返回：
如果此 collection 包含指定 collection 中的所有元素，则返回 true
抛出：
ClassCastException
- 如果指定 collection 中有一个或多个元素的类型与此 collection 不兼容（可选）
NullPointerException - 如果指定 collection 包含一个或多个 null 元素，并且此 collection 不允许 null 元素（可选），或者指定的 collection 为 null
addAll
boolean addAll(Collection<? extends E> c)
将指定 collection 中的所有元素都添加到此 collection 中（可选操作）。如果在进行此操作的同时修改指定的 collection，那么此操作行为是不确定的。（这意味着如果指定的 collection 是此 collection，并且此 collection 为非空，那么此调用的行为是不确定的。）
参数：
c
- 包含要添加到此 collection 的元素的 collection
返回：
如果此 collection 由于调用而发生更改，则返回true
抛出：
UnsupportedOperationException
- 如果此 collection 不支持 addAll
方法
ClassCastException - 如果指定 collection 中某个元素的类不允许它添加到此 collection 中
NullPointerException - 如果指定 collection 包含 null 元素，并且此 collection 不支持 null 元素，或者指定的 collection 为 null
IllegalArgumentException
- 如果指定 collection 的元素的某属性不允许它添加到此 collection 中
IllegalStateException - 如果由于插入限制，不是所有的元素都能在此时间添加
removeAll
boolean removeAll(Collection<?> c)
移除此 collection 中那些也包含在指定 collection 中的所有元素（可选操作）。此调用返回后，collection 中将不包含任何与指定 collection 相同的元素。
参数：
c
- 办好要从此 collection 移除的元素的 collection
返回：
如果此 collection 由于调用而发生更改，则返回true
抛出：
UnsupportedOperationException
- 如果此 collection 不支持 removeAll
方法
ClassCastException - 如果此 collection 中一个或多个元素的类型与指定 collection 不兼容（可选）
NullPointerException - 如果此 collection 包含一个或多个 null 元素，并且指定的 collection 不支持 null 元素（可选），或者指定的 collection 为 null
retainAll
boolean retainAll(Collection<?> c)
仅保留此 collection 中那些也包含在指定 collection 的元素（可选操作）。换句话说，移除此 collection 中未包含在指定 collection 中的所有元素。
参数：
c
- 包含保留在此 collection 中的元素的 collection
返回：
如果此 collection 由于调用而发生更改，则返回true
抛出：
UnsupportedOperationException
- 如果此 collection 不支持 retainAll
操作
ClassCastException - 如果此 collection 中一个或多个元素的类型与指定 collection 不兼容（可选）
NullPointerException - 如果此 collection 包含一个或多个 null 元素，并且指定的 collection 不允许 null 元素（可选），或者指定的 collection 为null
clear
void clear()
移除此 collection 中的所有元素（可选操作）。此方法返回后，除非抛出一个异常。
抛出：
UnsupportedOperationException
- 如果此 collection 不支持 clear
操作
equals
boolean equals(Object o )
比较此 collection 与指定对象是否相等。当 Collection
接口没有对 Object.equals
的常规协定添加任何约定时，“直接”实现该 Collection
接口（换句话说，创建一个 Collection
，但它不是 Set
或 List
的类）的程序员选择重写 Object.equals
方法时必须小心。没必要这样做，最简单的方案是依靠 Object
的实现，然而实现者可能希望实现“值比较”，而不是默认的“引用比较”。（List
和 Set
接口要求进行这样的值比较。）
Object.equals
方法的常规协定声称相等必须是对称的（换句话说，当且仅当存在 b.equals(a)
时，才存在a.equals(b)
）。List.equals
和 Set.equals
的协定声称列表只能与列表相等，set 只能与 set 相等。因此，对于一个既不实现 List
又不实现 Set
接口的 collection 类，当将此 collection 与任何列表或 set 进行比较时，常规的equals
方法必须返回 false
。（按照相同的逻辑，不可能编写一个同时正确实现 Set
和 List
接口的类。）
覆盖：
类 Object
中的 equals
参数：
o
- 要与此 collection 进行相等性比较的对象。
返回：
如果指定对象与此 collection 相等，则返回 true
hashCode
int hashCode()
返回此 collection 的哈希码值。当 Collection
接口没有为 Object.hashCode
方法的常规协定添加任何约束时，为了满足 Object.hashCode
方法的常规协定，程序员应该注意任何重写 Object.equals
方法的类必须重写 Object.hashCode
方法。需要特别指出的是，c1.equals(c2)
暗示着c1.hashCode()==c2.hashCode()
。
覆盖：
类 Object
中的 hashCode
返回：
此 collection 的哈希码值
以上是Collection接口的概述，以后再慢慢用代码对其中的方法进行验证。
