简介
1.所有的集合类都位于java.util包下，Java的结合主要由两个接口类派生出来，分别是Collection和Map
2.Collection接口是一组允许重复的对象集合
3.Set接口继承自Collection接口，是一组不允许重复的集合
4.List接口也继承自Collection接口，允许重复，并维护元素的插入顺序
- Map是键值对形式存储数据，可以根据key访问对应得value
6.Set，List，Map可以看做集合的三大类
首先我们需要清楚有序无序不是指集合中的排序，而是指是否按照元素的添加顺序来存储数据：
List：是按照元素添加顺序来存储数据的，因此是有序的，他的实现类ArrayList、LinkedList、Vector都是有序的。
Set：是无序的，并且Set中元素的顺序不允许重复，Set的底层实现原理其实是使用Map,他是计算key的哈希值来确定元素在数组中的存放位置，所以是无序的，因为Map中的key不允许重复，所以Set也不允许重复，Set的实现类有hashSet、TreeSet
特例：LinkedHashSet是有序的，LinkedHashSet底层数据结构由哈希表和链表组成。
- 哈希表保证元素的唯一性。
- 链表保证元素有素。(存储和取出是一致)
Map：是无序的，他的存储结构式哈希表<key,value>键值对形式，map中插入元素是根据key计算出的哈希值来存储元素的，因此他不是按照元素的添加顺序存储数据的，所以Map是无序的，他的实现类有HashMap、TableMap、TreeMap，只有LinkedHashSet是有序的，即保证元素的插入顺序。
特例：LinkedHashMap是有序的，底层除了哈希表还添加了一个链表用来保证元素顺序。 - 哈希表保证元素的唯一性。
- 链表保证元素有素。(存储和取出是一致)
HashMap和HashSet的区别
什么是 HashMap??
HashMap实现了Map接口，Map接口对键值对进行映射，Map中不允许重复的键，Map接口有两个基本的实现，HashMap和TreeMap.其中TreeMap保存了对象的排列次序，而HashMap则不能,HashMap允许键和值为null,HashMap是非syncronized的，但是collection提供方法能保证HashMap 同步，这样多个线程访问HashMap时候可以保证只有一个线程更改Map.
可以用put方法添加元素
什么是HashSet??
HashSet实现了Set接口，不允许集合中有重复的值，当提到HashSet时，第一件事就是将对象存储在HashSet之前，要先确保对象重写equals()和HashCode()方法，这样才能比较对象的值是否相等，用来确保Set中没有存储相等的对象，如果没重写这两个方法，将会使用这个方法的默认实现。
可以用add()添加元素
1.Collection是一个接口，是高度抽象出来的集合，它包含了集合的基本操作和属性，Collection包含了List和Set两大分支。
1).List是一个有序的集合，每一个元素都有他的索引，索引值0开始，List的实现类主要有LinkedList、ArrayList、Vector、Stack
2).Set是一个不允许重复的集合，Set的实现类有HashSet和TreeSet,
HashSet依赖于HashMap,实际上是通过HashMap实现的，TreeSet依赖于TreeMap，实际上是通过TreeMap实现的。
2.Map是一个映射接口，即key-value键值对，AbstractMap是一个抽象类，他实现了Map接口中的大部分API，而HashMap,TreeMap,WeakHashMap都继承自AbstractMap.HashTable虽然继承自Dictionary但是他实现了Map接口。
3.Iterator是遍历集合的工具，即我们通常所说的Iterator迭代器遍历集合。Collection依赖于Iterator,是因为Collection的实现类都要实现iterator()函数，返回一个Iterator对象，ListIterator是专门遍历List而存在的。
4.Enumeration也是遍历集合用的，只是比Iteratorde功能少，在上面的图解中所示，Enumeration只作用于HashTable、Vector、Stack
5.Arrays和Collections是操作数组集合的两个工具类
详细介绍
Collection接口
Collection接口是处理集合对象的根接口，其中定义了很多对元素的操作方法，Collection有两个主要的接口，Set、List，注意Map不是Collection的子接口
如上图所示，方法add()添加一个元素到集合中，addAll()将集合中的所有元素添加到集合中，contains()检测集合中是否包含指定元素，toArray()方法返回一个表示集合的数组，Collection中有一个iterator()函数，它的作用是返回一个Iterator接口，通常，我们通过Iterator迭代器来遍历集合。Collection有两个常用的子接口List和Set，下面详细介绍。
List接口
List集合代表一个有序集合，集合中的每个元素都有其对应顺序的索引，List集合允许有重复的元素，可以通过索引来访问指定位置的元素。
List接口继承自Collection接口，List代表的是有序的Collection，他用特定的插入顺序来维护元素顺序，用户可以对列表中的每个元素进行精确控制，同时可以根据元素的索引访问元素，实现List的集合主要有ArrayList、LinkedList、Vector、Stack
Vector：线程安全，但速度慢，已被ArrayList替代。
ArrayList：线程不安全，查询速度快，增删速度慢。
LinkedList：线程不安全，链表结构，增删速度快，查询速度慢。
ArrayList
ArrayList是一个动态数组，也是我们最常用的集合，他允许任何符合规则的元素插入甚至null,每一个ArrayList的初始容量是10，该容量代表了数组的大小，容器的大小会随着容器中的元素不断增加，每次向容器中添加元素都会进行容量检测，当快要溢出时，就会进行扩容。
ArrayList与Vector对比：
ArrayList，此实现不是同步的。性能比较好，优先使用；-------方法中没有synchronized
Vector的底层也是静态数组，但是Vector中的大量方法，都是synchronized，需要线程等待，性能比较差
一点通
HashSet：实现 Set 接口，不允许重复的元素，底层数据结构 hash table
LinkedHashSet：实现 Set 接口，不允许重复的元素，底层数据结构 hash table 与双链表
TreeSet：实现 NavigableSet 接口，不允许重复的元素，底层数据结构红黑树
ArrayList：实现 List 接口，允许重复元素，底层数据结构可变数组
LinkedList：实现 List 接口，允许重复元素，底层数据结构双链表
Vector：实现 List 接口，允许重复元素，底层数据结构可变数组
HashMap：实现 Map 接口，不允许重复的 key，底层数据结构 hash table
LinkedHashMap：实现 Map 接口，不允许重复的 key，底层数据结构 hash table 与双链表
HashTable：实现 Map 接口，不允许重复的 key，底层数据结构 hash table
TreeMap：实现 SortedMap 接口，不允许重复的 key，底层数据结构红黑树
LinkedList
LinkedList是一个双向链表，所以LinkedList不能随机访问，他的所有操作都要按照双重链表的操作执行，在列表中索引的操作将从头或者尾遍历，好处是用比较小的代价插入和删除元素。LinkedList也是非同步的，多线程下需要自己实现同步访问，一种解决方法是创建List的同时构造一个同步的List
List list = Collections.stnchronizedList(new LinkedList(.........));
Vector
Vector是线程同步的，也就是线程安全的，底层也是动态数组，但是效率低下，一般来说不考虑线程安全的情况下都用ArrayList.
Stack
Stack继承自Vector,实现了一个后进先出的堆栈，Stack提供了5个额外的方法使得Vector可以被当作堆栈使用，基本的push，pop方法，peek()得到栈顶的元素，empty（）测试是否为空，search（）检测一个元素在堆栈中的位置，Stack刚创建后是空栈。
Set接口
Set继承自Collection，他不包括重复元素，与List一样，他允许存放null但是只允许一个，Set接口有三个重要的实现类，HashSet、LinkedHashSet、TreeSet.
Set的元素是无序且不重复的，任意两个元素之间都满足a.equals(b)==false,注意：虽然Set中的元素没有顺序，但是元素在Set中的位置是由HashCode决定的，具体位置是固定的。即使A，B是两个对象，但是如果他们重写HashCode和equals方法相同的话，也不能同时放进Set中
HashSet
HashSet实现了Set接口，是没有重复元素的集合，由HashMap实现，不保证元素的插入和输出顺序，允许使用null元素，线程非同步的，HashSet按照Hash算法存储集合的元素，因此具有很好的查找和存取功能。HashSet的实现方式大致如下,通过一个HashMap存储元素，元素存放在HashMap的key中，而value同意使用一个Object对象。
LinkedHashSet
LinkedHashSet继承自HashSet并且实现了Set接口，其底层是基于LinkedHashMap实现的，有序，线程非同步，LinkedHashSet同样是根据HashCode值来决定元素的存储位置，但是他同时使用了一个链表维护元素的次序,也就是遍历的时候会根据元素的 添加顺序访问元素。
TreeSet
TreeMap是一个有序集合，底层基于TreeMap实现的，非线程安全，TreeSet支持两种排序方式，自然排序和定制排序，如果构造TreeSet时候，使用不带参数的构造函数，则使用自然比较器，若用户想要定制比较器，需要使用带比较器的参数。
注意：TreeSet集合不是通过hashCode和equals（）来比较元素的，他是通过compare或者comparaeTo函数判断元素是否相等，compare判断两个对象的id，相同的id算作重复元素，不会加入到集合中。
Map接口
Map与List和Set接口不同，它是由键值对组成的集合，提供了Key-value的映射，同时他不继承Collection，保证key-value的一一对应，他不存在相同的key值，但是value值可以相同。
HashMap
以hash表数据结构实现，查找对象时通过哈希函数计算其位置，他是为了快速查询而设计的，内部定义了一个hash表数组Entry[] table,元素会通过哈希转换函数将元素的哈希地址转换成数组中存放的索引，如果有冲突，则使用散列链表的形式将所有相同哈希地址的元素串起来，可以通过查看HashMap.Entry的源码知道他是一个单链表结构。
LinkedHashMap
继承自HashMap实现了Map接口，它保留元素的插入顺序，底层是Hash表和链表实现的，允许使用null值和null键，不保证映射的顺序，特别是不保证映射顺序永远不变。LinkedHashMap因为需要维护插入顺序，所以性能略低于HashMap,但是在迭代访问Map里全部元素的时候会有很好的性能，因为他一链表来维护元素的内部顺序。
TreeMap
TreeMap是一个有序的key-value集合，线程非同步，底层是基于红黑树实现的，每一个key-value节点作为红黑树的一个节点，TreeMap存储时会进行排序，会根据key对key-value键值对进行排序，其中的排序方式分为两种，自然排序和定制排序，具体排序取决于构造方法：
自然排序：TreeMap中所有的key必须事先Comparable接口，并且所有的key都应该是同一个类的对象，否则汇报ClassCastException异常。
定制排序：定义TreeMap时，创建一个comparator对象，该对象对所有treeMap中所有的key值进行排序，采用定制排序的时候不需要TreeMap中的所有key实现Comparable接口。
TreeMap判断两个元素相等的标准：两个key通过CompareTo()返回0，则认为两个key相等
如果使用自定义的类作为TreeMap中的key值，且想让TreeMap能够良好的工作，则必须重写自定义类中的equals（）方法，此时TreeMap中判断相等的标准是，equal()返回true，并且compareTo()方法返回0
比较总结
1.ArrayList和LinkedList
①ArrayList是一个动态数组结构，LinkedList是链表结构
②对于随机访问get和set，ArrayList对于优于LinkedList，因为linkedList要移动指针
③对于新增和删除，LinkedList占据绝对优势,因为ArrayList要移动元素位置
但是要看实际情况，如果是单条数据的插入和删除ArrayList速度更快，但是批量随机插入和删除的话LinkedList才是最好的选择。
2.HashTable和HashMap
①都实现了Map、Cloneable、Serializable接口
②都是存储键值对的散列表，并且都是使用拉链法实现的
③历史原因：HashTable是基于陈旧的Dictionary类的，HashMap是Map接口的一个实现
④同步性：HashTable是线程安全的，HashMap是线程不安全的
⑤对null值得处理： HashTable的key-value都不能为null,HashMap都可以
⑥基类不同：HashMap继承自AbstractMap，HashTable继承自Dictionary
⑦Dictionary是一个抽象类，她直接继承自Object类，没有实现任何接口，Api比Map少，一般通过Enumeration遍历，Map则是使用Iterator迭代器遍历，由于HashTable也实现了Map接口，所以他也支持Iterator遍历。
⑧AbstractMap是一个抽象类，他实现了Map接口的绝大多数api，为Map的具体实现类提供了极大的便利。
3.HashMap、HashTable、LikedHashMap、TreeMap的比较
①HashMap是一个最常用的Map，他根据键的HashCode值存储数据，根据key可以直接获取到value，具有很快的访问速度，遍历时，取得的数据顺序是完全随机的，线程不安全，可以通过用Collections的synchronizedMap方法使HashMap具有同步的能力
②HashTable和HashMap类似，不同点是：他不允许key-value的任意一个为null，他是线程安全的，即任一时刻只有一个线程能写HashTable，因此也导致写入时会较慢。
③LinkedHashMap保存了元素的插入顺序，再用Iterator遍历时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照应用次数排序，在遍历时会比HashMap慢，特例：在HashMap容量较大，实际数据较少的时候，遍历起来会比LinkedHashMap慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和容量有关如果需要输出顺序和输入顺序一样，可以选择LinkedHashMap,它继承自HashMap底层使用Hash表和双重链表保存元素，其基本操作和HashMap类似，他通过重写父类的方法来实现自己链接列表的特性。
④TreeMap实现了NavigableMap实现了SortedMap,内部实现是红黑树，能够把他保存的记录根据键排序，默认是按照键值的升序排列，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的，TreeMap不允许Key值为null，线程不安全。
4.HashSet、LinkedHashSet、TreeSet比较
①HashSet是无序不重复的，线程不安全的，集合元素可以是null但是仅允许一个，当向HashSet中存入一个元素时，HashSet会调用该对象的hashCode()值，根据此值确定存储位置，判断两个元素相等的标准是两个对象equals()==true并且两个对象的hashCode()方法返回值也相等。
②LinkedHashSet同样是根据元素的HashCode值来决定元素的位置，但是他用链表维护元素的插入顺序，遍历的时候，会以元素的添加顺序访问元素。
LinkedHashSet在迭代器访问Set中的全部元素时，性能比HashSet好，但是插入时的性能不如HashSet
③TreeSet是SortedSet的唯一实现类，TreeSet是无序的，即不能保证元素的插入顺序，但是支持自动排序，支持两种排序，自然排序和定制排序。
TreeSet特性：
它存储唯一的元素
它不保留元素的插入顺序
它按升序对元素进行排序
它不是线程安全的
