Java集合框架
# Collection集合中常见的Api
# 增：
- 方法传入的数据类型必须是 Object，所以当写入基本数据类型的时候，会做自动装箱 auto-boxing 和自动拆箱 unboxing。
boolean add(E e);
- 把另一个集合里的元素加到此集合中。
boolean addAll(Collection<? extends E> c);
# 删：
- 删除的指定元素。
boolean remove(Object o);
- 删除集合B中的所有元素
boolean removeAll(Collection<?> c);
# 改：
- 没有改, 可以用删和增来实现
# 查：
- 查集合中是否有某个特定的元素
boolean contains(Object o);
- 查集合 A 是否包含了集合 B：
boolean containsAll(Collection<?> c);
# 对集合整体的操作：
- 判断集合是否为空
boolean isEmpty();
- 集合的大小
int size();
- 集合转成数组
Object[] toArray();
# List
# 与LinkedList的区别
An ordered collection (also known as a sequence).
Unlike sets, lists typically allow duplicate elements.
List 的实现方式有LinkedList 和 ArrayList，一个链表一个数组，没什么好说的。
| 功能 | 方法 | ArrayList | LinkedList |
|---|---|---|---|
| 增 | add(E e) | O(1) | O(1) |
| 增 | add(int index, E e) | O(n) | O(n) |
| 删 | remove(int index) | O(n) | O(n) |
| 删 | remove(E e) | O(1) | O(n) |
| 改 | set(int index, E e) | O(1) | O(n) |
| 查 | get(int index) | O(1) | O(n) |
# 与Vector的区别
Vector 中许多方法加了synchronized关键字，同步了，但效率低。
线程安全区别
扩容区别
ArrayList扩容1.5倍，Vector扩容2倍。
# Queue & Deque
- Queue是单向队列； Deque是双向队列。
# Queue
| 功能 | 抛异常 | 返回值 |
|---|---|---|
| 增 | add(e) | offer(e) |
| 删 | remove() | poll() |
| 瞧 | element() | peek() |
为什么会抛异常呢？
- 比如队列空了，那 remove() 就会抛异常，但是 poll() 就返回 null；element() 就会抛异常，而 peek() 就返回 null 就好了。
那 add(e) 怎么会抛异常呢？
有些 Queue 它会有容量的限制，比如 BlockingQueue，那如果已经达到了它最大的容量且不会扩容的，就会抛异常；但如果 offer(e)，就会 return false.
那怎么选择呢？：
- 首先，要用就用同一组 API，前后要统一；
- 其次，根据需求。如果你需要它抛异常，那就是用抛异常的；不过做算法题时基本不用，所以选那组返回特殊值的就好了。
# Deque
| 功能 | 抛异常 | 返回值 |
|---|---|---|
| 增 | addFirst(e)/ addLast(e) | offerFirst(e)/ offerLast(e) |
| 删 | removeFirst()/ removeLast() | pollFirst()/ pollLast() |
| 瞧 | getFirst()/ getLast() | peekFirst()/ peekLast() |
使用时同理，要用就用同一组。
Queue 和 Deque 的这些 API 都是 O(1) 的时间复杂度，准确来说是均摊时间复杂度。
# 实现类
- 如果想实现「普通队列 - 先进先出」的语义，就使用 LinkedList 或者 ArrayDeque 来实现；
- 如果想实现「优先队列」的语义，就使用 PriorityQueue；
- 如果想实现「栈」的语义，就使用 ArrayDeque。
在实现普通队列时，如何选择用LinkedList还是ArrayDeque呢？
LinkedList还是ArrayDeque区别
- ArrayDeque 是一个可扩容的数组，LinkedList 是链表结构；
- ArrayDeque 里不可以存 null 值，但是 LinkedList 可以；
- ArrayDeque 在操作头尾端的增删操作时更高效，但是 LinkedList 只有在当要移除中间某个元素且已经找到了这个元素后的移除才是 O(1) 的；
- ArrayDeque 在内存使用方面更高效。
非必要存null值时，推荐使用ArrayDeque。
# Stack
虽然Java有这个Stack类，官方文档说不让用了！因为Vector已经弃用，而Stack是继承它的。
用ArrayDeque吧
Deque<Integer> stack = new ArrayDeque<>();
# Set
Set 的常用实现类有三个：
HashSet: 采用 Hashmap 的 key 来储存元素，主要特点是无序的，基本操作都是 O(1) 的时间复杂度，很快。
LinkedHashSet: 这个是一个 HashSet + LinkedList 的结构，特点就是既拥有了 O(1) 的时间复杂度，又能够保留插入的顺序。
TreeSet: 采用红黑树结构，特点是可以有序，可以用自然排序或者自定义比较器来排序；缺点就是查询速度没有 HashSet 快。
那每个 Set 的底层实现其实就是对应的 Map：
数值放在 map 中的 key 上，value 上放了个 PRESENT，是一个静态的 Object，相当于 place holder，每个 key 都指向这个 object。
# 总结
