在Java中，所有的集合类都在java.util包中。集合与数组的区别：
1. 数组可以存储基本类型，也可以存储对象；而集合只能存储对象。
2. 数组中只能存储一种类型；而一个集合可以有多种类型。
首先，我们看一下整个集合类的框架，用一幅图表示。
1. Collection
Collection 是所有集合类的父接口，它定义了集合类最基本的操作方法：
增加对象：boolean add(E e) 增加成功则返回true; 若对象已存在，且该集合不允许包含重复元素，则返回false。
删除对象：boolean remove(Object o) 删除集合中与对象o值相等的元素（e.equals（e）==true）
由于List允许允许元素重复，只删除与o相等的第一个元素。
boolean removeAll(Collection<?> c) 删除与c集合中所有对象相等的元素
void clear(); 清除集合中的所有元素，size = 0
判断对象：boolean contains(Object o) 判断集合中所有e.equals（e）==true的元素，并返回true。否则返回false。
boolean containsAll(Collection<?> c) 判断集合c是否是调用集合的子集。
保留交集：boolean retainAll(Collection<?> c) 删除在调用集合在c中不存在的元素，只保留与c的交集
转化为数组：Object[] toArray()
<T> T[] toArray(T[] a)
集合长度：int size() 获取集合的长度
迭代对象：Iterator<E> iterator()
迭代器： 就是一个Iterator接口的子类对象，封装了取出其绑定集合的元素的方式。
步骤： 1、通过调用集合的 Iterator iterator（）方法返回该集合的迭代器，
2、将此迭代器赋值给 一个 Iterator 型对象引用。
3、通过此引用，调用迭代器的方法操作集合：
1）、boolean hasNext（）：如果集合中任有元素可以迭代，则返回true。
2）、Object next（）：返回迭代的下一个元素（列表中还在）。
3）、void remove（）：从迭代器指向的集合中 移除 迭代器返回的最后一个元素。
注意：你不能同时用迭代器和集合同时去操作同一组元素， 有可能会抛出并发异常。
原因：迭代器已经创建， 之后通过集合方法操作的元素过程（比如说增加），迭代器并不知道集合做了什么操作，还是只能按照原来的元素列表操作，就会发生错误。
*** 在迭代的时候要删除元素，只能通过iterator.remove()方法，不可以用集合的remove()。
2. List
列表（List）实现了Collection，并拥有自己的特性：可以有重复元素，且是有序的，以元素添加顺序为序。该类集合中有索引【角标】。
凡是有角标的集合，都有其特有的操作方法，根据index增删改查，也可以根据对象获取角标：
增：void add(int index, E element)
删：E remove(int index)
改：E set(int index, E element)
查：E get(int index)
List<E> subList(int fromIndex, int toIndex)
获取角标：int indexOf(Object o)
int lastIndexOf(Object o)
同时List还有一个特殊的迭代器 ListIterator，由于普通的迭代器提供的功能太少，ListIterator 为List的迭代提供了更完善的功能，它仍然继承于普通的Iterator。ListIterator中新增的方法：
增加：void add(E e)
修改：void set(E e)
向前迭代：boolean hasPrevious()
E previous()
获取角标：int nextIndex()
int previousIndex()
list 集合在涉及到需要判断元素是否相同时，底层调用的都是equals方法。（contains、 remove方法等）
上面从列表角度介绍了一些公用的操作方法，下面来看一下List的4种实现（底层不同）：
ArrayList 底层数据结构是数组存储，查询速度快，但是增删改慢，非线程安全，长度大约0.5倍增长（len += len>>1）
LinkedList 底层数据链结构是表结构，增删改速度快，但查询慢，非线程安全，链表长度即为元素长度。
Vector 底层实现与ArrayList一样，但是线程同步的，相比于ArrayList，查询增删都慢，长度1倍增长。
Stack 继承于 Vector ，实现了一种后进先出（LIFO）的数据结构，栈。
LinkedList 实现了一个双端队列（Deque），具有队列的一些特有方法：
1）、addFirst（）从集合列表开头插入元素
2）、addLast（）从集合列表结尾插入元素（等效于add（））
3）、getFirst（）拿到第一个元素，返回这个元素
4）、getLast（）拿到最后一个元素，返回这个元素
5）、removeFirst（）移除第一个元素，返回这个元素
6）、removeLast（）移除最后一个元素，返回这个元素
（如果列表中没有元素，那么：3到6方法抛 空元素异常）
注： 在1.6版本以后，新添加了获取和移除方法， 在空列表的时候，会返回null，不会发生异常。
1）、peekFirst（）获取 但 不移除 列表第一个元素，列表为空返回null
2）、peekLast（）获取 但 不移除 列表最后一个元素，列表为空返回null
3）、pollFirst（）获取 并 移除 列表第一个元素，列表为空返回null
4）、pollLast（）获取 并 移除 列表第最后一个元素，列表为空返回null
3. Set
集（Set）也实现了 Collection 接口，它与列表的区别在于，不允许与重复元素，且元素是无序的（元素的有序性是指与插入顺序一致）。这类集合中没有索引。
Set有两种实现类，且底层都是用Map实现的：
HashSet：底层用HashMap实现，元素存在map的key中（key, new Object()），元素无序。
TreeSet： 底层用TreeMap实现，元素存在map的key中（key, new Object()），元素无序，但是元素是升序排列的。
HashSet
底层数据： 底层使用哈希表作为数据结构。
元素唯一性： 是通过元素的两个方法： hashCode 和 equals 来完成的。
如果两个元素的HashCode值相同，就会判断equals是否为true。
如果两个元素的HashCode值不同，就不会调用equals方法。
注意：对于判断元素是否存在、删除等操作，都依赖于元素的hashCode、equals等方法。
哈希表：给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，
则称表M为哈希(Hash)表，函数f(key)为哈希(Hash) 函数。
（哈希值与内存地址值之间的关系：默认的哈希值是内存地址值计算的哈希值，但是只是为了给人看的，真正在
内存中还是依靠内存地址值来进行运算的，而不是哈希值）
TreeSet
底层数据结构： 二叉树 （保证元素唯一性的方法是保证compareTo 方法return 0）
比较方式：
方式一、就是让元素自己具有比较性，元素需要实现comparable接口，重写其中得compareTo方法，这个排序叫做自然排序（默认排序）
1、 无序性（按照输入元素类中自定义的compareTo方法来排定存储对象。）2、 单一性（通过判断元素类中自定义的compareTo方法放回值是否为0来判断元素是否相等。）
3、 让需要存入到TreeSet中的元素，实现comparable接口，该接口中定义了一个public int compareTo方法
4、 compareTo 方法：我们需要在类定义中重写该方法， public int compareTo，
使得： 当有e.compareTo(e1)时，
如果e大于e1则返回正数，当e小于e1则返回负数， 等于则返回0.
而且当有e等于e1时， 可以定义附属判断条件来判断 两个对象的大小。
注意：TreeSet 本情况的所有的底层比较原理只是调用了元素的compareTo方法，与 equals等方法都无关。（add、contains、remove等需要用到比较的方法）
所以我们定义所有的比较都返回正数，那么靠遍历迭代器取出的元素顺序和存入顺序一样。
如果定义所有的比较都返回负数，那么靠遍历迭代器去除的元素顺序和存入的顺序相反。
如果定义所有比较都返回0 ，那么就只能存入一个元素，最后也只能取出一个元素。
方式二、当元素自身没有比较性或者具有的比较性不是自身所需要的，那么就要让集合自身具有比较性。
那么就要在集合一初始化时定义比较方式（也就是调用集合的构造方法）
1、 无序性（按照集合实例化的时候的比较器来排布元素的存储顺序。）
2、 单一性（通过集合的比较器的compare方法返回值是否为0 来判断元素是否相等。）
3、 定义一个比价器的类，使其实现comparator接口， 重写覆盖其中的 int compare(T o1, T o2) 方法。
4、 compare 方法：我们需要在比较器类定义中重写该方法，int compare(Object o1, Object o2)，
使得： 我们在该方法中比较两个对象，或者比较其对象的方法，或者直接定义一个数值返回。
当返回值为正时代表o1大于o2，当返回值为负时代表o1小于o2，返回值为0 则代表两个对象相等。
而且当初步判断有o1等于o1时， 可以定义附属判断条件来判断 两个对象的大小。
注意：TreeSet 本情况的所有的底层比较原理只是调用了集合比较器的compare方法，与 元素equals等方法都无关。
（add、contains、remove等需要用到比较的方法）
所以我们定义所有的比较都返回正数，那么靠遍历迭代器取出的元素顺序和存入顺序一样。
如果定义所有的比较都返回负数，那么靠遍历迭代器去除的元素顺序和存入的顺序相反。
如果定义所有比较都返回0 ，那么就只能存入一个元素，最后也只能取出一个元素。
4. Map
映射（Map）没有实现 Collection 接口，它的每一项都是成对存储的，（key, value）。存储的每一个数据都有一个对应的关键字key，key 是唯一的。
key虽然决定了数据在映射中存储的位置，检索数据时，需要提供相应的Key。但是并不是靠key本身来确定的，而是使用了一种散列（hashing）技术来处理，产生一个被称为散列码（hash code）的整数值，它通常作为一个偏置量，该偏置量是相对于数据存储位置与map内存起始位置的偏移，由此来确定（key, value）的存储位置。
理想情况下，散列处理应该产生给定范围内均匀分布的值，而且每个关键字应得到不同的散列码。
Map有多种实现：
HashMap：非线程安全，底层为散列表，允许存储一个 null key，和多个 null value。
HashTable：线程安全，执行效率较低。所有的 key 必须非null。为了能更高效的工作，所有的类必须实现 equal()和 hashcode()方法。
LinkedHashMap：非线程安全，底层实现为散列表，能够保证元素的插入顺序（相对于读取而言的）。
WeakHashMap：非线程安全，底层实现为散列表，当某个键不在被引用时，其对应的键值对可能会对GC回收，从map中清除。
TreeMap：底层为二叉树结构，元素按key值升序排列，不是按插入顺序。