【Java】【集合】集合框架Collection
文章目录
- Java集合框架
- Collection
- List
- Queue
- Set
Java集合框架
Java 集合，也称作容器，主要是由两大接口 (Interface) 派生出来的：Collection 和 Map：
Collection 存放单一元素。Map 存放 key-value 键值对。
Collection
常用API，操作集合CRUD（Create, Read, Update, and Delete）：
boolean add(E e);
boolean addAll(Collection<? extends E> c);
boolean remove(Object o);
boolean removeAll(Collection<?> c);
boolean contains(Object o);
boolean containsAll(Collection<?> c);
boolean isEmpty();
int size();
Object[] toArray(); // 集合转数组
List
- 有序，可重复
- 实现方式有 LinkedList 和 ArrayList 两种
| 功能 | 方法 | ArrayList | LinkedList |
|---|---|---|---|
| 增 | add(E e) | O(1) | O(1) |
| 删 | remove(int index) | O(n) | O(n) |
| 改 | set(int index, E e) | O(1) | O(n) |
| 查 | get(int index) | O(1) | O(n) |
1、ArrayList
- 数组实现，可以随机访问，查找快。
- 物理连续性，增删中间元素需移动后续元素。指定 index 添加数据，就需要拷贝 index 后面的数据后移一位。
- 动态数组，初始化时是一个空数组，在第一次 add 时设置初始容量为 10，每次扩容都增加到原来的 1.5 倍。
2、LinkedList
- 链表实现，查找元素需从头访问
- 增删快
3、Vector
- 数组实现
- 弃用，线程安全，但是太多synchronized，效率低
4、ArrayList和Vector区别
- Vector线程安全
- 扩容机制，ArrayList增量右移一位即/2，新容量是原容量1.5倍。Vector新容量是2倍。
5、Stack
- 弃用，使用ArrayDeque实现
Queue
1、Queue两组API，功能相同，用法区别：
| 功能 | 抛异常 | 返回值 |
|---|---|---|
| 增 | add(E e) | offer(e) |
| 删 | remove() | poll() |
| 查 | element() | peek() |
2、 Deque双端队列，针对两端：
| 功能 | 抛异常 | 返回值 |
|---|---|---|
| 增 | addFirst(e)/ addLast(e) | offerFirst(e)/ offerLast(e) |
| 删 | removeFirst()/ removeLast() | pollFirst()/ pollLast() |
| 查 | getFirst()/ getLast() | peekFirst()/ peekLast() |
3、实现类：LinkedList、ArrayDeque、PriorityQueue
- 普通队列：LinkedList、ArrayDeque
- 优先队列：PriorityQueue
- 栈：ArrayDeque
- LinkedList、ArrayDeque区别
①ArrayDeque 是一个可扩容的数组，LinkedList 是链表结构；
②ArrayDeque 里不可以存 null 值，但是 LinkedList 可以；
③ArrayDeque 在操作头尾端的增删操作时更高效，但是 LinkedList 只有在当要移除中间某个元素且已经找到了这个元素后的移除才是 O(1) 的；
④ArrayDeque 在内存使用方面更高效。
所以，只要不是必须要存 null 值，就选择 ArrayDeque 吧！
Set
- 无序，不重复
- 实现类：HashSet、LinkedHashSet、TreeSet
1、HashSet
采用 Hashmap 的 key 来储存元素，主要特点是无序的，基本操作都是 O(1) 的时间复杂度，很快。
2、LinkedHashSet
HashSet + LinkedList 的结构，特点就是既拥有了 O(1) 的时间复杂度，又能够保留插入的顺序。
3、TreeSet
采用红黑树结构，特点是可以有序，可以用自然排序或者自定义比较器来排序；缺点就是查询速度没有 HashSet 快。
参考
https://mp.weixin.qq.com/s?__biz=MzAwNDA2OTM1Ng==&mid=2453144514&idx=2&sn=3b14fa92bd3d129d5c60a2eea0c5869f&scene=21#