Collection接口继承树

1. Collection接口介绍
2. 常用Set原理分析
3. 常用Queue原理分析
4. 常用List原理分析

Collection接口介绍

API	描述
add(Object o)	增加元素
addAll(Collection c)	增加集合中所有元素
clean()	清空集合
contains(Object o)	是否包含元素
containsAll(Collection c)	是否包含c中所有元素
iterator	返回一个Iterator对象
remove(Object o)	删除元素o
removeAll(Collection c)	删除集合c中包含的所有元素
retainAll(Collection c)	相当于求与c的交集
removeIf(lambda)	Lambda表达式去除符合要求的元素
size()	返回元素个数
toArray()	把集合转换为数组

常用Collection区别

类	有序性	线程安全	适用范围	性能	原理
HashSet	无序	不安全	元素唯一	高	hashcode
LinkedHashSet	有序	不安全	元素插入顺序有序且唯一	低	双向链表+ hashcode
TreeSet	有序	不安全	元素按自然（或自定义）排序顺序且唯一	低	二叉树+ hashcode
ArrayList	有序	不安全	随机访问频繁	高	动态数组
LinkedList	有序	不安全	频繁增删、栈实现	低	双向链表
Vector	有序	安全	多线程集合存储	低	动态数组
PriorityQueue	有序	不安全	按队列元素大小排序（也可自定义排序）	低	小顶堆

常用Set原理分析

• HashSet：底层是由HashMap实现的，HashSet可插入null，元素不重复，线程不同步，需要手动同步，例如

Set s = Collections.synchronizedSet(new HashSet(...));

• LinkedHashSet：对于LinkedHashSet而言，它继承与HashSet、又基于LinkedHashMap来实现的，线程同步同HashSet类似，保证了增、删数据的常量复杂度，需要维护链表数据结构的开销，所以效率比HashSet要低。
• TreeSet：支持自然顺序访问和自定义的比较顺序，其底层原理是通过二叉树的结构比较元素的大小从而完成排序，由于需要维护二叉树的结构，效率比HashSet低。

常用Queue原理分析

• PriorityQueue：实现原理是小顶堆，作用是保证每次取出的元素都是队列中权值最小的，元素的大小可以通过元素本人的自然顺序，也可以通过构造比较器。

常用List原理分析

• ArrayList：动态数组，线程不安全。其增容量与Vector有所不同，Vector增容会增加一倍，而ArrayList只增容50%；
• LinkedArrayList：提供双向链表，对数据的增加、删除的效率高，但是随机访问的效率低于ArrayList。
• Vector：线程安全的动态数组，可根据需要自动增容，当数组达到最大限度，会创建新的数组，并拷贝原有数据。