集合

Collection接口：单列数据，定义了存取一组对象的方法的集合
List接口：元素有序、可重复的集合 —>“动态”数据，替换原有的数组
ArrayList:
LinkedList:双向链表，内部没有声明数组，而是定义了Node类型的first和last，用于记录首末元素。同时，定义内部类Node，作为LinkedList中保存数据的基本结构。Node除了保存数据，还定义了两个变量：
 prev变量记录前一个元素的位置
 next变量记录下一个元素的位置
对于频繁的插入或删除元素的操作，建议使用LinkedList类，效率较高

Vector:Vector 是一个古老的集合，JDK1.0就有了。大多数操作与ArrayList相同，区别之处在于Vector是线程安全的。

面试题：ArrayList(扩容1.5)、LinkedList(扩容2.0)、Vector三者的异同？
同：三个类都实现点了List接口、存储数据的特点相同：存储有序、可重复的数据
ArrayList 查找的时间复杂度为O(1)、 LinkedList为O(n)
Set：元素无序、不可重复的集合
hashCode

Map接口：双列数据，保存具有映射关系“key-value对”的集合

List提供的方法

1、添加  add(Object obj)
 addAll(Collection coll)
2、获取有效元素的个数
 int size()
3、清空集合
 void clear()
4、是否是空集合
 boolean isEmpty()
5、是否包含某个元素
 boolean contains(Object obj)：是通过元素的equals方法来判断是否 是同一个对象  boolean containsAll(Collection c)：也是调用元素的equals方法来比 较的。拿两个集合的元素挨个比较。
6、删除
 boolean remove(Object obj) ：通过元素的equals方法判断是否是 要删除的那个元素。只会删除找到的第一个元素
 boolean removeAll(Collection coll)：取当前集合的差集
7、取两个集合的交集
 boolean retainAll(Collection c)：把交集的结果存在当前集合中，不 影响c
8、集合是否相等
 boolean equals(Object obj)
9、转成对象数组
 Object[] toArray()
10、获取集合对象的哈希值
 hashCode()
11、遍历
 iterator()：返回迭代器对象，用于集合遍历

List除了从Collection集合继承的方法外，List 集合里添加了一些根据索引来操作集合元素的方法。
void add(int index, Object ele):在index位置插入ele元素
boolean addAll(int index, Collection eles):从index位置开始将eles中
的所有元素添加进来
Object get(int index):获取指定index位置的元素
int indexOf(Object obj):返回obj在集合中首次出现的位置
int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置
Object remove(int index):移除指定index位置的元素，并返回此元素
Object set(int index, Object ele):设置指定index位置的元素为ele
List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex
位置的子集合

ArrayList和LinkedList的异同

二者都线程不安全，相对线程安全的Vector，执行效率高。
此外，ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。对于新增和删除操作add(特指插入)和remove，LinkedList比较占优势，因为ArrayList要移动数据。

ArrayList和Vector的区别

Vector和ArrayList几乎是完全相同的,唯一的区别在于Vector是同步类(synchronized)
，属于强同步类。因此开销就比ArrayList要大，访问要慢。正常情况下,大多数的Java程序员使用ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。Vector每次扩容请求其大小的2倍空间，而ArrayList是1.5倍。Vector还有一
个子类Stack。

Iterator对象称为迭代器(设计模式的一种)，主要用于遍历 Collection 集合中的元素。
 GOF给迭代器模式的定义为：提供一种方法访问一个容器(container)对象中各个元 素，而又不需暴露该对象的内部细节。迭代器模式，就是为容器而生。类似于“公 交车上的售票员”、“火车上的乘务员”、“空姐”。
 Collection接口继承了java.lang.Iterable接口，该接口有一个iterator()方法，那么所 有实现了Collection接口的集合类都有一个iterator()方法，用以返回一个实现了 Iterator接口的对象。
 Iterator 仅用于遍历集合，Iterator 本身并不提供承装对象的能力。如果需要创建 Iterator 对象，则必须有一个被迭代的集合。
 集合对象每次调用iterator()方法都得到一个全新的迭代器对象，默认游标都在集合 的第一个元素之前。
**

Set接口

存储无序的（不是随机性）、不可重复的
无序性：存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值
HashSet:作为Set接口主要实现：线程不安全：可存储null值。
LinkedHashSet:作为HashSet的子类：遍历其内部数组时。可以按照添加的顺序遍历。
TreeSet：可以按照添加对象的指定属性，进行排序。

向HashSet中添加元素的过程：

 当向 HashSet 集合中存入一个元素时，HashSet 会调用该对象的 hashCode() 方法来得到该对象的 hashCode 值，然后根据 hashCode 值，通过某种散列函数决定该对象在 HashSet 底层数组中的存储位置。（这个散列函数会与底层数组的长度相计算得到在
数组中的下标，并且这种散列函数计算还尽可能保证能均匀存储元素，越是散列分布，该散列函数设计的越好）

 如果两个元素的hashCode()值相等，会再继续调用equals方法，如果equals方法结果为true，添加失败；如果为false，那么会保存该元素，但是该数组的位置已经有元素了，那么会通过链表的方式继续链接。

如果两个元素的 equals() 方法返回 true，但它们的 hashCode() 返回值不相
等，hashSet 将会把它们存储在不同的位置，但依然可以添加成功。

Set中添加的对象一定要重写equals()和hashCode(Object obj)方法，以实现对象相等规则：相同的对象必须具有相等的散列吗。

LinkedHashSet对于频繁遍历的效率高于HashSet

向TreeSet中添加的数据，要求是相同类的对象，可以按照添加的对象的指定属性，进行排序。
两种排序方式：自然排序 和 定制排序
重写compareTo()返回0不再是equals
默认情况下，TreeSet 采用自然排序。