【Java核心基础知识】01 - Java集合

集合类型分为3种：Collection、Iterator、Map，均存放于Java.util包中。

1.Collection：集合，List、Set、Queue的最基本的接口
2.Iterator：迭代器，ListIterator、
3.Map：映射，SortedMap、ConcurrentMap、AbstractMap的最基本的接口。

集合框架

1 Collection

1.1 List

1.1.1 ArrayList

1.排列有序，可重复。
2.底层使用数组。
3.适合随机查找和遍历，增删慢。
4.线程不安全，多线程下不建议使用ArrayList。
5.当容量不够事，ArrayList默认容量增加0.5倍。

1.1.2 Vector

1.排列有序，可重复。
2.底层使用数组。
3.适合随机查找和遍历，增删慢。
4.线程安全，效率比ArrayList低。
5.当容量不够时，Vector默认容量增加1倍。

1.1.3 LinkedList

1.排列有序，可重复。
2.底层使用双向循环链表。
3.查找速度慢，增删快，适合动态插入和删除。
4.线程不安全。

1.2 Set

1.2.1 HashSet

1.排列无序，不可重复。
2.存储结构基于哈希表。
3.存取速度快。
4.非线程安全。

1.2.2 TreeSet

1.排列有序，不可重复。
2.存储结构基于红黑树。
3.排序存储，按照元素的自然顺序或者自定义顺序排序。
4.非线程安全。

1.2.3 LinkedHashSet

1.排列有序，不可重复。
2.采用Hash表存储，并使用双向链表记录插入顺序。
3.内部是LinkedHashMap。
4.线程安全。

1.3 Queue

Queue（队列）是一种特殊的线性表
只允许在表的前端（front）进行删除操作
在表的后端（rear）进行插入操作
它遵循FIFO（First-In-First-Out，先进先出）的原则

Java提供了多种Queue的实现，包括以下几种：

• LinkedList：实现了Deque接口，可以作为队列使用。它是一个双向链表，所以插入和删除操作具有很高的效率。
• PriorityQueue：这是一个基于优先堆的无界优先队列。它的头部是按指定排序方式确定的最小元素。如果多个元素都是最小值，则任何一个都可能被找到。
• ArrayDeque：这是一个基于数组的双端队列，其操作具有很高的效率。
• ConcurrentLinkedQueue：这是一个适用于高并发场景的线程安全的队列。
• LinkedBlockingQueue：这是一个基于链表的、线程安全的阻塞队列。此队列按 FIFO（先进先出）排序元素。
• PriorityBlockingQueue：这是一个适用于高并发场景的线程安全的阻塞队列。此队列按元素的优先级进行排序。
• SynchronousQueue：这是一个没有存储空间的阻塞队列。它仅仅在每个插入操作和每个移除操作之间提供互斥。此队列仅支持线程之间的协作。

2.Map

2.1 HashMap

1.允许键值为空。
2.线程不安全。
3.底层：哈希表+数组+链表+红黑树（JAVA8后，链表元素大于8个时）。
4.使用Iterator来遍历。
5.多线程环境下，可以使用ConcurrentHashMap或者Collections.synchronizedMap进行替换。
6.在插入、删除和查找元素时，时间复杂度都为O(1)。

2.2 ConcurrentHashMap

1.允许键值为空。
2.线程安全（concurrencyLevel默认值16，理论上最多可以同时支持 16 个线程并发写）。
3.底层：基于Segment数组的分段锁机制+链表+红黑树（JAVA8后，链表元素大于8个时）。
4.使用Iterator来遍历。
5.在插入、删除和查找元素时，时间复杂度都为O(1)。

2.3 HashTable

1.不允许键值为空。
2.线程安全（继承Dictionary类，只能一个线程，并发性不如ConcurrentHashMap）。
3.底层哈希表+数组+链表。
4.使用Iterator来遍历。
5.在插入、删除和查找元素时，时间复杂度都为O(1)。

2.4 TreeMap

1.允许键值为空（键值必须实现Comparable接口或在构造TreeMap传入自定义Comparator）。
2.线程安全性介于HashMap和HashTable之间。
3.底层二叉树。
4.在插入、删除和查找元素时，时间复杂度都为O(1)。