java中集合类主要有两大分支：
（1）Collection （2）Map 
Collection接口
一个Collection代表一组Object，即Collection的元素（Elements）。Java SDK不提供直接继承自Collection的类，java SDK提供的类都是继承自Collection的“子接口”如List和Set。
实现：所有实现Collection接口的类都必须提供两个标准的构造函数：无参数的构造函数用于创建一个空的Collection，有一个 Collection参数的构造函数用于创建一个新的Collection，这个新的Collection与传入的Collection有相同的元素。后一个构造函数允许用户复制一个Collection。
访问：
Iterator it = collection.iterator(); // 获得一个迭代子
while(it.hasNext()) {
Object obj = it.next(); // 得到下一个元素
}
—Set接口
继承关系
Collection
|–Set：元素唯一，不保证存取顺序，只可以用迭代器获取元素。
|–HashSet：哈希表结构，非线程安全，查询速度较快。元素唯一性取决于hashCode和equals方法。
|–LinkedHashSet：带有双向链表的哈希表结构，非线程安全，保持存取顺序，保持了查询速度较快特点。
|—SortedSet
|–TreeSet：平衡排序二叉树（红黑树）结构，非线程安全，按自然排序或比较器存入元素以保证元素有序。元素唯一性取决于ComparaTo方法或Comparator比较器。
Collection子接口；Set中不存在两个相同的元素，使得equal相等；
* Set集合中的元素是唯一的，不可重复（取决于hashCode和equals方法），也就是说具有唯一性。
* Set集合中元素不保证存取顺序，并不存在索引。
Set判断两个对象相同不是使用==运算符，而是根据equals方法。也就是说，只要两个对象用equals方法比较返回true，Set就不 会接受这两个对象。
set底层实现：RB树（红黑树）
set集合容器使用一种称为红黑树(Red-Black Tree) 的平衡二叉检索树的数据结构，来组织泛化的元素数据。每个节点包含一个取值红色或黑色的颜色域，以利于进行树的平衡处理。作为节点键值的元素的插入，必须确保每个子树根节点的键值大于左子树所有节点的键值，而小于右子树所有节点的键值。不会将重复的键值插入容器，也不需要指定具体的插入位置，而按元素在树中的关联关系，进行位置检索和插入，元素的删除亦然。
元素数据的检索，使用的是二叉检索树的中序遍历算法，检索的效率高于vector、 deque和list等容器。由于采用中序遍历算法可将二叉检索树的键值，由小到大排列遍历出来，因此 set 集合容器蕴含了元素间的有序性。
元素的插入：set 并没有固定的所谓尾部插入 push_back函数，元素的插入一般使用 insert进行动态检索插入。
元素的删除：与插入一样，set 容器也具有高效的红黑树元素的删除处理，并自动重新调整内部的红黑树平衡。
元素的搜索：set容器提供了一个应用红黑树进行搜索的函数 find ，返回的迭代器值位搜索到的元素位置，如果元素不存在，则返回一个 end结束元素的位置。
为什么不用hash作为数据结构？
红黑树与hash table最大的不同是，红黑树是有序结构，而hash table不是。但不是说set就不能用hash，如果只是判断set中的元素是否存在，那么hash显然更合适，因为set 的访问操作时间复杂度是log(N)的，而使用hash底层实现的hash_set是近似O(1)的。然而，set应该更加被强调理解为“集合”，而集合所涉及的操作并、交、差等，即STL提供的如交集set_intersection()、并集set_union()、差集set_difference()和对称差集set_symmetric_difference()，都需要进行大量的比较工作，那么使用底层是有序结构的红黑树就十分恰当了，这也是其相对hash结构的优势所在。
hashset：底层hashmap:数组+链表
1>不保证元素的存入顺序
2>非同步
3>允许有null
4>不允许重复
当向HashSet结合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据 hashCode值来决定该对象在HashSet中存储位置。
简单的说，HashSet集合判断两个元素相等的标准是两个对象通过equals方法比较相等，并且两个对象的hashCode()方法返回值相 等
注意，如果要把一个对象放入HashSet中，重写该对象对应类的equals方法，也应该重写其hashCode()方法。其规则是如果两个对 象通过equals方法比较返回true时，其hashCode也应该相同。另外，对象中用作equals比较标准的属性，都应该用来计算 hashCode的值。
LinkedHashSet：底层使用LinkedHashMap来保存所有元素；
与hashset的实现一致，同时维护一个双向链表，保证了顺序；
LinkedHashSet在迭代访问Set中的全部元素时，性能比HashSet好，但是插入时性能稍微逊色于HashSet。
treeSet：底层红黑树实现 treemap
1>元素具有唯一性，不能有重复
2>不保证存储的顺序，但是保证想要的顺序；
3>非同步
TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式，自然排序 和定制排序，其中自然排序为默认的排序方式。向TreeSet中加入的应该是同一个类的对象。
TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比较没有返回0；
自然排序
自然排序使用要排序元素的CompareTo（Object obj）方法来比较元素之间大小关系，然后将元素按照升序排列。
定制排序
自然排序是根据集合元素的大小，以升序排列，如果要定制排序，应该使用Comparator接口，实现 int compare(T o1,T o2)方法
总结：
如果要插入一个有序的集合建议使用treeSet，因为TreeSet是使用红黑树算法来进行维护，相对性能会比hashSet会慢，而hashSet下面的一个子类linkedhashset对于，删除，插入来说，他的性能会低于hashset,因为，他要保证插入的顺序，而又因为他的底层使用链表来存储的，所以它相对查找来说就更快了。
—list接口（类似于数组）
1>允许重复
2>允许null
3>有序
ArrayList：object类型的数组，动态数组，允许包括null在内的所有元素；
不同步、固定大小的数组，不够用时，扩容，每次数组容量增长大约是其容量的1.5倍，新开辟一个都移过去，代价很高；
LinkedList ：非同步，双向链表，允许包括null在内的所有元素；
Vector：线程同步；一种老的动态数组，是线程同步的，效率很低，一般不赞成使用。
map：存储 key，value
HashMap：数组+链表的结合体—哈希表
底层数据结构是哈希表。线程不安全，效率高
LinkedHashMap
底层数据结构由链表和哈希表组成。
由链表保证元素有序。
由哈希表保证元素唯一。
Hashtable：
底层数据结构是哈希表。线程安全，效率低
TreeMap：底层数据结构是红黑树
1>唯一性（同上）
2>有序性（同上）