学习随笔 ：集合
Collection接口下有List,Set，Queue队列接口。
Map下有HashMap,HashTable,TreeMap。
List的实现类有ArrayList,LinkedList，Vector（线程安全）。
Set的实现类有HashSet，TreeSet，HashLinkedSet。
Map的实现类有HashTable,HashMap,TreeMap…
注意:
Queue接口与List、Set同一级别，都是继承了Collection接口。
看图你会发现,LinkedList既可以实现Queue接口,也可以实现List接口.只不过呢, LinkedList实现了Queue接口。Queue接口窄化了对LinkedList的方法的访问权限（即在方法中的参数类型如果是Queue时，就完全只能访问Queue接口所定义的方法 了，而不能直接访问 LinkedList的非Queue的方法），以使得只有恰当的方法才可以使用。
SortedSet是个接口，它里面的（只有TreeSet这一个实现可用）中的元素一定是有序的。
List：
ArrayList底层是数组。用下标定位数据。所以查询速度快，但是增加删除效率很慢。增删的原理是对底层的数组进行扩容copy。默认size=10。之后增加的数组长度是10/2+10=15。在频繁查找以及尾部的插入与删除场景下使用ArrayList。
例：在一个长度为10的数组中在下标是4的位置添加一个元素。
把当前index=4之后的数据拿出来copy到index=5之后，index=4的位置就空出来了，然后再进行插入。效率很低。
删除同理，把要删除的下标之后的数据copy到要删除的下标的位置。
LinkedList是一个链表结构。查询效率低，增删效率高。
频繁在任意位置进行元素插入与删除使用LinkedList。
Vector当产生对象时就初始化内部数组(默认大小为10),当增量为0时，扩容为原先数组2倍,当增量大于0是扩充为原来的大小+增量采用synchronized同步方法，线程安全，性能很低(读读互斥)。
List总结：
1，有序。
2，可重复。
（底层数据结构）
主要方法：
boolean add(E o) 向列表的尾部追加指定的元素
void add(int index,E element) 在列表的指定位置插入指定元素。
boolean addAll(Collection<? extends E> c) 追加指定 collection中的所有元素到此列表的结尾，顺序是指定collection的迭代器返回这些元素的顺序。
boolean addAll(int index,Collection<? extends E> c) 将指定collection中的所有元素都插入到列表中的指定位置。
void clear() 从列表中移除所有元素。
boolean contains(Object o) 如果列表包含指定的元素，则返回true。
boolean containsAll(Collection<?> c) 如果列表包含指定collection的所有元素，则返回true。
boolean equals(Object c) 比较指定的对象与列表是否相等。
E get(int index) 返回列表中指定位置的元素。
int hashCode() 返回列表的哈希码值。
int indexOf(Object o) 返回列表中首次出现指定元素的索引，如果列表不包含此元素，则返回-1。
boolean isEmpty() 判断集合是否为空 如果为空 则返回true,否则返回false
Iterator iterator() 返回以正确顺序在列表的元素上进行迭代的迭代器。
int lastIndexOf(Object o) 返回列表中最后出现指定元素的索引，如果列表不包含此元素，则返回-1。
ListIterator listIterator() 返回列表中元素的列表迭代器（以正确的顺序）。
ListIterator listIterator(int index)返回列表中元素的列表迭代器（以正确的顺序），从列表的指定位置开始。
E remove(int index) 移除列表中指定位置的元素。
boolean remove(Object o) 移除列表中出现的首个指定元素。
boolean removeAll(Collection<?> c) 从列表中移除指定collection中包含的所有元素。
boolean retainAll(Collection<?> c)仅在列表中保留指定collection中所包含的元素。
E set(int index,E element) 用指定元素替换列表中指定位置的元素。
int size() 返回列表中的元素数。
List subList(int forIndex,int toIndex) 返回列表中指定的formIndex(包括) 和toIndex(不包括)之间的部分视图。
Object toArray() 返回以正确顺序包含列表中的所有元素的数组。
Set：
特点：无序，不可重复。
1)HashSet:
原理:底层是Hash表。h(key) 用key来确定某个元素的位置。index=h(key)
保证元素唯一性的方法：hashcode() equals()
不能进行排序。
2)LinkedHashSet
底层数据结构是链表和哈希表。(FIFO插入有序,唯一)
1.由链表保证元素有序
2.由哈希表保证元素唯一
3)TreeSet
底层数据结构是红黑树。(唯一，有序)
如何保证元素排序的呢?
自然排序
比较器排序
如何保证元素唯一性的呢?
根据比较的返回值是否是0来决定。
Map接口有三个比较重要的实现类，分别是HashMap、TreeMap和HashTable。
TreeMap是有序的，HashMap和HashTable是无序的。
Hashtable的方法是同步的，HashMap的方法不是同步的。这是两者最主要的区别。
Hashtable是线程安全的，HashMap不是线程安全的。
HashMap效率较高，Hashtable效率较低。
如果对同步性或与遗留代码的兼容性没有任何要求，建议使用HashMap。 查看Hashtable的源代码就可以发现，除构造函数外，Hashtable的所有 public 方法声明中都有 synchronized关键字，而HashMap的源码中则没有。
Hashtable不允许null值，HashMap允许null值（key和value都允许）
父类不同：Hashtable的父类是Dictionary，HashMap的父类是AbstractMap