- Collection接口介绍
- 常用Set原理分析
- 常用Queue原理分析
- 常用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：线程安全的动态数组，可根据需要自动增容，当数组达到最大限度，会创建新的数组，并拷贝原有数据。
- CopyOnWriteArrayList：使用ReentrantLock重入锁保证线程安全，由于写操作时时先拷贝新数组，在新数组中修改，改完再替换，时间负责度O(n)，性能低下。读操作支持随机访问，时间复杂度O(1)。读操作不加锁，写操作加锁，所以适用于读多写少的场合。在一致性方面，保证最终一致性，不保证实时一致性。
