介绍JAVA中的Collection FrameWork(包括如何写自己的数据结构)?JAVA中集合框架中，我总是弄混

Collection FrameWork如下： 核心接口有：
Collection Set Sorted SetListMap Sorted Map
Set接口：不允许重复的元素。它对add、equals、hashCode方法增加了限制SortedSet接口：扩展了Set接口，此接口的元素按升序排序。List接口：一些集合具有顺序，即在一个项目后添加另一个项目。列表可以有重复元素。提供了ListIterator，允许向前或向后移动元素。Map接口：将键映射到值得对象。Map不能包含重复键，但可以包含重复值。每个键最多都只能映射到一个值。核心设计类：


Map 设计Set 设计List 设计HashMapHashSetArrayListHashtableLinkedHashSetVectorTreeMapTreeSetLinkedLiskLinkedHasMap
散列表是最快的数据存储结构，它是一个数组。数据存储在数组中散列函数指定的特定下标。散列函数是一组输入数据和一组整数之间的映射。集合类和接口层次Collections是一个类，带有用于处理集合的静态实用方法Collection是一个接口，带有多数集合常用的方法声明，包括add、remove、contains、size、iteratorCollection是最基本的集合接口，一个Collection代表一组Object，即Collection的元素（Elements） Map提供key到value的映射 集合框架的优点：提供一组可用的集合接口，可以方便地扩展或改写集合；接口和算法的可重用性提高了软件的可重用性；提供了有效的数据结构和算法，减少了编程工作。

Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│　└Stack
└Set
Map
├Hashtable
├HashMap
└WeakHashMap
Collection是最基本的集合接口.
一个Collection代表一组Object.
即Collection的元素（Elements）
Map提供key到value的映射

COLLECTION：选集，又称合集。　　Collection 层次结构 中的根接口。Collection 表示一组对象，这些对象也称为 collection 的元素。一些 collection 允许有重复的元素，而另一些则不允许。一些 collection 是有序的，而另一些则是无序的。JDK 不提供此接口的任何直接 实现：它提供更具体的子接口（如 Set 和 List）实现。此接口通常用来传递 collection，并在需要最大普遍性的地方操作这些 collection。
　　包 (bag) 或多集合 (multiset)（可能包含重复元素的无序 collection）应该直接实现此接口。
　　所有通用的 Collection 实现类（通常通过它的一个子接口间接实现 Collection）应该提供两个“标准”构造方法：一个是 void（无参数）构造方法，用于创建空 collection；另一个是带有 Collection 类型单参数的构造方法，用于创建一个具有与其参数相同元素新的 collection。实际上，后者允许用户复制任何 collection，以生成所需实现类型的一个等效 collection。尽管无法强制执行此约定（因为接口不能包含构造方法），但是 Java 平台库中所有通用的 Collection 实现都遵从它。
　　此接口中包含的“破坏性”方法，是指可修改其所操作的 collection 的那些方法，如果此 collection 不支持该操作，则指定这些方法抛出 UnsupportedOperationException。如果是这样，那么在调用对该 collection 无效时，这些方法可能，但并不一定抛出 UnsupportedOperationException。例如，如果要添加的 collection 为空且不可修改，则对该 collection 调用 addAll(Collection) 方法时，可能但并不一定抛出异常。
　　一些 collection 实现对它们可能包含的元素有所限制。例如，某些实现禁止 null 元素，而某些实现则对元素的类型有限制。试图添加不合格的元素将抛出一个未经检查的异常，通常是 NullPointerException 或 ClassCastException。试图查询是否存在不合格的元素可能抛出一个异常，或者只是简单地返回 false；某些实现将表现出前一种行为，而某些实现则表现后一种。较为常见的是，试图对某个不合格的元素执行操作且该操作的完成不会导致将不合格的元素插入 collection 中，将可能抛出一个异常，也可能操作成功，这取决于实现本身。这样的异常在此接口的规范中标记为“可选”。
　　由每个 collection 来确定其自身的同步策略。在没有实现的强烈保证的情况下，调用由另一进程正在更改的 collection 的方法可能会出现不确定行为；这包括直接调用，将 collection 传递给可能执行调用的方法，以及使用现有迭代器检查 collection。
　　Collections Framework 接口中的很多方法是根据 equals 方法定义的。例如，contains(Object o) 方法的规范声明：“当且仅当此 collection 包含至少一个满足 (o==null ? e==null :o.equals(e)) 的元素 e 时，返回 true。”不 应将此规范理解为它暗指调用具有非空参数 o 的 Collection.contains 方法会导致为任意的 e 元素调用 o.equals(e) 方法。可随意对各种实现执行优化，只要避免调用 equals 即可，例如，通过首先比较两个元素的哈希码。（Object.hashCode() 规范保证哈希码不相等的两个对象不会相等）。较为常见的是，各种 Collections Framework 接口的实现可随意利用底层 Object 方法的指定行为，而不管实现程序认为它是否合适。
　　集合的常用操作
　　boolean add(E e)
　　确保此 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 中所有元素的数组；返回数组的运行时类型与指定数组的运行时类型相同。
[编辑本段]
Collection接口的各子类的深入剖析
　　线性表，链表，哈希表是常用的数据结构，在进行Java开发时，JDK已经为我们提供了一系列相应的类来实现基本的数据结构。这些类均在java.util包中。本段落试图通过简单的描述，向读者阐述各个类的作用以及如何正确使用这些类。
　　Collection
　　├List
　　│├LinkedList
　　│├ArrayList
　　│└Vector
　　│　└Stack
　　└Set
　　Map
　　├Hashtable
　　├HashMap
　　└WeakHashMap
　　Collection接口
　　Collection是最基本的集合接口，一个Collection代表一组Object，即 Collection的元素（Elements）。一些Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类，Java SDK提供的类都是继承自Collection的“子接口”如List和Set。
　　所有实现Collection接口的类都必须提供两个标准的构造函数：无参数的构造函数用于创建一个空的Collection，有一个Collection参数的构造函数用于创建一个新的Collection，这个新的Collection与传入的Collection有相同的元素。后一个构造函数允许用户复制一个Collection。
　　如何遍历Collection中的每一个元素？不论Collection的实际类型如何，它都支持一个iterator()的方法，该方法返回一个迭代子，使用该迭代子即可逐一访问Collection中每一个元素。典型的用法如下：
　　Iterator it = collection.iterator(); // 获得一个迭代子
　　while(it.hasNext()) {
　　Object obj = it.next(); // 得到下一个元素
　　}
　　由Collection接口派生的两个接口是List和Set。
　　List接口
　　List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。
　　和下面要提到的Set不同，List允许有相同的元素。
　　除了具有Collection接口必备的iterator()方法外，List还提供一个 listIterator()方法，返回一个ListIterator接口，和标准的Iterator接口相比，ListIterator多了一些 add()之类的方法，允许添加，删除，设定元素，还能向前或向后遍历。
　　实现List接口的常用类有LinkedList，ArrayList，Vector和Stack。
　　LinkedList类
　　LinkedList实现了List接口，允许null元素。此外LinkedList提供额外的get，remove，insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。
　　注意LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：
　　List list = Collections.synchronizedList(new LinkedList(...));
　　ArrayList类
　　ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步。
　　size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。
　　　和LinkedList一样，ArrayList也是非同步的（unsynchronized）。
　　Vector类
　　Vector非常类似ArrayList，但是Vector是同步的。由Vector创建的 Iterator，虽然和ArrayList创建的Iterator是同一接口，但是，因为Vector是同步的，当一个Iterator被创建而且正在被使用，另一个线程改变了Vector的状态（例如，添加或删除了一些元素），这时调用Iterator的方法时将抛出 ConcurrentModificationException，因此必须捕获该异常。
　　Stack 类
　　Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得 Vector得以被当作堆栈使用。基本的push和pop方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。
　　Set接口
　　Set是一种不包含重复的元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2)=false，Set最多有一个null元素。