一、String
- String类是Java中字符串操作类，位于java.lang包下
- String类型对象的底层使用字符数组char[]存储字符串，由final修饰且没有提供公共的修改方法，因此String对象是不可变的。
- 常见方法
| 方法名 | 作用 |
|---|---|
| trim() | 去掉字符串首尾空字符 |
| split(分隔符/正则表达式) | 分割字符串 |
| substring(int start,int end) | 提取子串 |
| length() | 字符串长度 |
| charAt(int index) | 寻找指定索引处的字符 |
| indexOf(int index) | 寻找指定字符在字符串中第一次出现的索引 |
| startsWith(String prefix) | 字符串是否以指定前缀开头 |
| endsWith(String prefix) | 字符串是否以指定后缀结尾 |
| isEmpty() | 是否为空串 |
| contains(CharSequence s) | 字符串是否包含指定字符或字符串 |
| toUpperCase()/toLowerCase() | 大小写转换 |
- String、StringBuilder、StringBuffer
- 联系：三者都是对字符串进行操作的类
- 区别
| 类名 | 是否可变 | 线程安全 |
|---|---|---|
| String | 不可变 | √ |
| StringBuilder | 可变 | × |
| StringBuffer | 可变 | √（同步锁） |
- 字符串常量池
- 是为了重复利用字符串字面量在JVM 中开辟的一个内存区域（堆中）
- final 关键字修饰之后的 String 会被编译器当做常量来处理
二、Java集合
（一）集合介绍
1. 框架结构
Java中集合主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。其框架结构如图所示：
2. 集合和数组
| 特性 | 数组 | 集合 (Collection) |
|---|---|---|
| 存储类型 | 可以存储基本数据类型和对象 | 只能存储对象 |
| 大小 | 固定 | 可动态调整 |
| 性能 | 较快，内存连续 | 较慢，底层实现不同类型的数据结构 |
| 访问方式 | 通过索引访问 | 通过迭代器或方法访问 |
| 类型安全 | 可以是泛型，但不强制 | 可以使用泛型，类型安全 |
| 多态性 | 不支持 | 支持 |
| 工具方法 | 无 | 提供丰富的工具方法 (例如 add, remove) |
| 遍历方式 | for 循环 | for-each 循环、迭代器 |
| 实现类 | 无 | List, Set, Queue 等 |
| 初始容量 | 必须指定 | 可以动态调整 |
| 内存分配 | 连续内存块 | 不连续，取决于具体实现 |
| 是否支持多线程 | 不支持 | 一些实现支持 (如 CopyOnWriteArrayList) |
（二）实现Collection接口的集合
1. ArrayList
（1）介绍
- ArrayList是用于顺序存储元素的集合，其存储的值可以重复。
- ArrayList是非线程安全的。
（2）常用方法
| 方法名 | 说明 |
|---|---|
boolean add(E e) | 在列表末尾添加指定的元素 |
void add(int index, E element) | 在指定位置插入指定元素 |
boolean addAll(Collection<? extends E> c) | 添加指定集合中的所有元素到列表末尾 |
E get(int index) | 返回指定位置的元素 |
E set(int index, E element) | 用指定元素替换指定位置的元素 |
E remove(int index) | 移除并返回指定位置的元素 |
boolean remove(Object o) | 移除首次出现的指定元素 |
void clear() | 移除列表中的所有元素 |
int size() | 返回列表中的元素数量 |
boolean isEmpty() | 判断列表是否为空 |
boolean contains(Object o) | 判断列表是否包含指定元素 |
int indexOf(Object o) | 返回首次出现的指定元素的索引 |
int lastIndexOf(Object o) | 返回最后一次出现的指定元素的索引 |
Object[] toArray() | 返回包含列表所有元素的数组 |
<T> T[] toArray(T[] a) | 返回包含列表所有元素的数组，数组的运行时类型与指定数组相同 |
boolean containsAll(Collection<?> c) | 判断列表是否包含指定集合中的所有元素 |
boolean removeAll(Collection<?> c) | 移除列表中与指定集合中相同的所有元素 |
boolean retainAll(Collection<?> c) | 仅保留列表中与指定集合中相同的元素 |
void ensureCapacity(int minCapacity) | 增加列表的容量以确保它至少可以保存指定数量的元素 |
void trimToSize() | 将列表的容量调整为当前元素数量 |
Iterator<E> iterator() | 返回列表元素的迭代器 |
ListIterator<E> listIterator() | 返回列表元素的列表迭代器 |
ListIterator<E> listIterator(int index) | 返回从指定位置开始的列表迭代器 |
List<E> subList(int fromIndex, int toIndex) | 返回列表的指定范围的视图 |
其添加、删除元素的时间复杂度均为O（n），查找元素的时间复杂度为O（1）。
（3）底层数据结构
- ArrayList 底层是一个动态数组，默认初始容量为 10。（Java7之后懒加载）
- 扩容因子：1.5。
- 扩容步骤：
- 初始化时 elementData 为空数组。
- 首次添加元素时，确保最小容量。
- 当添加元素超出当前容量时，计算新的容量（1.5倍）。
- 如果新的容量小于所需的最小容量，则调整为最小容量。
- 如果新的容量超出最大数组大小，则进行特殊处理。
- 使用 Arrays.copyOf 方法将旧数组内容复制到新数组。
- 扩容源码
// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;
// 空数组实例，用于懒加载机制
private static final Object[] EMPTY_ELEMENTDATA = {};
// 实际存储元素的数组
transient Object[] elementData;
// ArrayList 的当前大小
private int size;
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
2. LinkedList
（1）介绍
- LinkedList是用于随机存储元素的集合，其存储的值可以重复。
- LinkedList是非线程安全的.
（2）常用方法
| 方法 | 描述 |
|---|---|
boolean add(E e) | 在链表末尾添加指定元素。 |
void add(int index, E element) | 在链表的指定位置插入指定元素。 |
boolean addAll(Collection<? extends E> c) | 将指定集合中的所有元素按其迭代器返回的顺序添加到链表末尾。 |
boolean addAll(int index, Collection<? extends E> c) | 将指定集合中的所有元素按其迭代器返回的顺序插入到链表的指定位置。 |
void addFirst(E e) | 在链表头部插入指定元素。 |
void addLast(E e) | 在链表尾部添加指定元素。 |
void clear() | 移除链表中的所有元素。 |
Object clone() | 返回此链表的浅表副本。 |
boolean contains(Object o) | 判断链表中是否包含指定元素。 |
E get(int index) | 返回链表中指定位置的元素。 |
E getFirst() | 返回链表的第一个元素。 |
E getLast() | 返回链表的最后一个元素。 |
int indexOf(Object o) | 返回链表中第一次出现指定元素的索引，如果不存在返回-1。 |
int lastIndexOf(Object o) | 返回链表中最后一次出现指定元素的索引，如果不存在返回-1。 |
boolean isEmpty() | 判断链表是否为空。 |
E remove(int index) | 移除并返回链表中指定位置的元素。 |
boolean remove(Object o) | 移除链表中首次出现的指定元素。 |
E removeFirst() | 移除并返回链表的第一个元素。 |
E removeLast() | 移除并返回链表的最后一个元素。 |
int size() | 返回链表中的元素数量。 |
Object[] toArray() | 返回一个包含链表中所有元素的数组。 |
<T> T[] toArray(T[] a) | 返回一个包含链表中所有元素的数组，数组的运行时类型与指定数组相同。 |
void push(E e) | 将元素推入此链表表示的堆栈（等价于 addFirst(E e)）。 |
E pop() | 从此链表表示的堆栈弹出一个元素（等价于 removeFirst()）。 |
E peek() | 检索但不移除此链表表示的堆栈的头部（第一个元素），如果此链表为空，则返回 null。 |
E peekFirst() | 检索但不移除此链表的第一个元素，如果此链表为空，则返回 null。 |
E peekLast() | 检索但不移除此链表的最后一个元素，如果此链表为空，则返回 null。 |
boolean offer(E e) | 将指定元素添加到此链表的末尾（等价于 add(E e)）。 |
boolean offerFirst(E e) | 在链表头部插入指定元素。 |
boolean offerLast(E e) | 在链表末尾插入指定元素。 |
E poll() | 检索并移除此链表的头部（第一个元素），如果此链表为空，则返回 null。 |
E pollFirst() | 检索并移除此链表的第一个元素，如果此链表为空，则返回 null。 |
E pollLast() | 检索并移除此链表的最后一个元素，如果此链表为空，则返回 null。 |
其添加、删除、查找元素的时间复杂度均为O（n）。
（3）底层数据结构
- LinkedList 底层使用的是双向链表（JDK1.6 之前为循环链表，JDK1.7 取消了循环）进行实现。
3. ArrayList、LinkedList、Vector之间的联系与区别
| 特性 | ArrayList | LinkedList | Vector |
|---|---|---|---|
| 底层数据结构 | 数组 | 双向链表 | 数组 |
| 线程安全性 | 非线程安全 | 非线程安全 | 线程安全 |
| 扩容机制 | 当元素数量超过当前容量时，扩展当前容量的1.5倍 | 每次添加元素时，根据需要动态创建新节点 | 当元素数量超过当前容量时，扩展当前容量的2倍 |
| 遍历性能 | 适合随机访问，通过索引访问元素效率高（O(1)） | 遍历性能较差，通过索引访问元素效率较低（O(n)） | 适合随机访问，通过索引访问元素效率高（O(1)） |
| 插入和删除操作 | 在末尾插入元素的性能较好，中间位置插入效率较低 | 在头部和尾部插入、删除元素性能较好，中间位置操作高效 | 在末尾插入元素的性能较好，中间位置插入效率较低 |
4. HashSet、LinkedHashSet 和 TreeSet的联系与区别
| 特性 | HashSet | LinkedHashSet | TreeSet |
|---|---|---|---|
| 底层数据结构 | 哈希表 | 哈希表 + 链表 | 红黑树 |
| 元素顺序 | 无序 | 按插入顺序维护 | 按自然顺序或比较器排序 |
| 元素唯一性 | 基于 hashCode() 和 equals() 方法判断 | 基于 hashCode() 和 equals() 方法判断 | 基于比较器或自然顺序判断唯一性 |
| 插入和检索性能 | 平均时间复杂度 O(1) | 平均时间复杂度 O(1) | 平均时间复杂度 O(log n) |
| 迭代顺序 | 不保证顺序 | 按插入顺序迭代 | 按排序顺序迭代 |
| 内存消耗 | 较低 | 稍高 | 较高 |
| 线程安全性 | 非线程安全 | 非线程安全 | 非线程安全 |
注：使用 Collections.synchronizedSet 方法可以创建一个线程安全的 Set 集合
Set<String> synchronizedSet = Collections.synchronizedSet(new HashSet<>());
5. Deque
（1）介绍
- Deque 是双端队列，在队列的两端均可以插入或删除元素。
- Deque 还提供pop（）和push（）方法用以实现栈（目前栈的实现方式）
（2）常用方法
| 方法 | 描述 |
|---|---|
void addFirst(E e) | 将指定元素插入到双端队列的开头。 |
void addLast(E e) | 将指定元素插入到双端队列的末尾。 |
boolean offerFirst(E e) | 将指定元素插入到双端队列的开头，如果成功返回 true。 |
boolean offerLast(E e) | 将指定元素插入到双端队列的末尾，如果成功返回 true。 |
E removeFirst() | 移除并返回双端队列的第一个元素，如果队列为空则抛出异常。 |
E removeLast() | 移除并返回双端队列的最后一个元素，如果队列为空则抛出异常。 |
E pollFirst() | 移除并返回双端队列的第一个元素，如果队列为空则返回 null。 |
E pollLast() | 移除并返回双端队列的最后一个元素，如果队列为空则返回 null。 |
E getFirst() | 返回双端队列的第一个元素，但不移除。如果队列为空则抛出异常。 |
E getLast() | 返回双端队列的最后一个元素，但不移除。如果队列为空则抛出异常。 |
E peekFirst() | 返回双端队列的第一个元素，但不移除。如果队列为空则返回 null。 |
E peekLast() | 返回双端队列的最后一个元素，但不移除。如果队列为空则返回 null。 |
void push(E e) | 将元素推入双端队列表示的堆栈（等效于 addFirst(E e)）。 |
E pop() | 从双端队列表示的堆栈弹出一个元素（等效于 removeFirst()）。 |
boolean removeFirstOccurrence(Object o) | 移除第一次出现的指定元素（从头部开始），如果移除则返回 true。 |
boolean removeLastOccurrence(Object o) | 移除最后一次出现的指定元素（从尾部开始），如果移除则返回 true。 |
boolean add(E e) | 将指定元素添加到双端队列的末尾（等效于 offerLast(E e)）。 |
boolean offer(E e) | 将指定元素添加到双端队列的末尾，如果成功返回 true（等效于 offerLast(E e)）。 |
E remove() | 移除并返回双端队列的头部元素（等效于 removeFirst()）。 |
E poll() | 移除并返回双端队列的头部元素，如果队列为空则返回 null（等效于 pollFirst()）。 |
E element() | 返回双端队列的头部元素，但不移除（等效于 getFirst()）。 |
E peek() | 返回双端队列的头部元素，但不移除，如果队列为空则返回 null（等效于 peekFirst()）。 |
void clear() | 移除双端队列中的所有元素。 |
boolean isEmpty() | 判断双端队列是否为空。 |
int size() | 返回双端队列中的元素数量。 |
Iterator<E> iterator() | 返回在此双端队列元素上进行迭代的迭代器。 |
Iterator<E> descendingIterator() | 返回在此双端队列的元素上以逆向顺序进行迭代的迭代器。 |
（3）接口实现方式
- ArrayDeque：使用循环数组和双指针作为其底层数据结构。
- LinkedList :基于双向链表实现Deque。
6. PriorityQueue（力扣刷题常用）
（1）介绍
- PriorityQueue是优先级队列，是堆数据结构的主要实现方式，存在大根堆和小根堆（默认）两种。
- 大根堆：父节点的值大于等于其孩子节点的值
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b)->b-a);
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// 实现大根堆的比较规则，返回负数表示 o1 比 o2 大（o1 在 o2 的前面）
return o2.compareTo(o1);
}
});
- 小跟堆：父节点的值小于等于其孩子节点的值
PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
- PriorityQueue是非线程安全的
（2）常用方法
| 方法签名 | 描述 |
|---|---|
boolean add(E e) | 将指定的元素插入到此优先队列中。 |
boolean offer(E e) | 将指定的元素插入到此优先队列中。 |
E remove() | 检索并删除此优先队列的头部，即具有最高优先级的元素。如果队列为空，则抛出异常。 |
E poll() | 检索并删除此优先队列的头部，即具有最高优先级的元素。如果队列为空，则返回 null。 |
E peek() | 检索但不删除此优先队列的头部，即具有最高优先级的元素。如果队列为空，则返回 null。 |
int size() | 返回此优先队列中的元素数量。 |
boolean isEmpty() | 如果此优先队列不包含任何元素，则返回 true。 |
void clear() | 从此优先队列中移除所有元素。 |
Object[] toArray() | 返回一个包含此优先队列所有元素的数组。数组中的元素没有特定的顺序。 |
<T> T[] toArray(T[] a) | 返回一个包含此优先队列所有元素的数组，如果指定数组足够大，则将元素存入指定数组中。否则，将创建一个新数组。 |
（3）底层数据结构
- PriorityQueue 的底层数据结构通常采用的是二叉小顶堆（Binary Min-Heap）的数据结构，底层使用可变长的数组来存储数据。
- 二叉小顶堆：是一种完全二叉树，其中父节点的值小于或等于其任何一个子节点的值。
（三）实现Map接口的集合
1. HashMap
（1）介绍
- HashMap是基于哈希表的 Map 接口的实现，主要用于存储键值对类型数据。
- HashMap是线程不安全的
注：HashMap的键和值都可以为NULL，但是键只能有一个为NULL，值可以多个
（2）常用函数
| 方法 | 描述 |
|---|---|
V put(K key, V value) | 将指定的值与此映射中的指定键关联（如果该映射先前包含一个该键的映射，则替换其值）。 |
V get(Object key) | 返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回 null。 |
V remove(Object key) | 如果存在一个键的映射关系，则将其从此映射中移除。 |
boolean containsKey(Object key) | 如果此映射包含指定键的映射关系，则返回 true。 |
boolean containsValue(Object value) | 如果此映射将一个或多个键映射到指定值，则返回 true。 |
Set<K> keySet() | 返回此映射中包含的键的 Set 视图。 |
Collection<V> values() | 返回此映射中包含的值的 Collection 视图。 |
Set<Map.Entry<K, V>> entrySet() | 返回此映射中包含的映射关系的 Set 视图。 |
int size() | 返回此映射中的键-值映射关系数。 |
boolean isEmpty() | 如果此映射未包含键-值映射关系，则返回 true。 |
void clear() | 从此映射中移除所有的键-值映射关系。 |
V putIfAbsent(K key, V value) | 如果指定键尚未与值关联（或映射到 null），将其与指定值关联并返回 null，否则返回当前值。 |
V replace(K key, V value) | 仅当指定键已经与某个值关联时，替换该键的值。 |
boolean replace(K key, V oldValue, V newValue) | 仅当当前映射到指定值时，替换该键的值。 |
void forEach(BiConsumer<? super K, ? super V> action) | 对此映射中的每个映射执行给定操作，直到所有条目都被处理或该操作引发异常。 |
V compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) | 计算指定键的值及其当前映射（如果有），并将其条目更新到此映射中。 |
V computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction) | 如果指定的键尚未与值关联或映射到 null，则尝试使用给定的映射函数计算其值并将其输入到此映射中。 |
V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) | 如果指定的键存在且非 null，则尝试使用给定的映射函数计算新的映射。 |
V merge(K key, V value, BiFunction<? super V,? super V,? extends V> remappingFunction) | 如果指定的键尚未与值关联或映射到 null，则将其与给定的非 null 值关联。 |
（3）底层数据结构
- HashMap使用的数据结构在Java8之前是：数组+链表，Java8之后是数组+链表+红黑树。
注：当链表长度大于阈值（默认为 8）时，先判断当前数组的长度是否小于 64，小于的话选择先进行数组扩容，大于64时转换为红黑树；当红黑树的节点小于6的时候退化为链表（避免频繁的转换）。 - 初始容量为16，扩容因子0.75，2倍扩容。
- 扩容步骤：
- 创建新数组：新的数组容量是原来数组容量的两倍
- 重新计算哈希值：对于原来数组中的每个元素，根据新的数组容量重新计算其哈希值，从而确定其在新数组中的位置。
- 迁移元素：将原来数组中的所有元素放到新数组中。
注：这里不仅仅是简单地复制元素，而是需要根据新的哈希值重新分配位置。
- 扩容源码
// 在 HashMap 类中的 resize 方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTable = table;
int oldCap = (oldTable == null) ? 0 : oldTable.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTable;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTable = (Node<K,V>[])new Node[newCap];
table = newTable;
if (oldTable != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTable[j]) != null) {
oldTable[j] = null;
if (e.next == null)
newTable[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTable, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTable[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTable[j + oldCap] = hiHead;
}
}
}
}
}
return newTable;
}
（4）HashMap 的长度为什么是 2 的幂次方
向HashMap中添加元素时，需要通过计算元素的**（散列值%数组长度）来找到元素的存储位置，而当除数是2的幂次方（及数组长度为2的幂次方）时，求余的操作可以转换为&操作**，能够提高运算效率。
2. ConcurrentHashMap
（1）介绍
ConcurrentHashMap是通过加锁保证线程安全的HashMap。
注：ConcurrentHashMap 的 key 和 value 不能为 null （避免二义性）
（2）底层数据结构
- Java7之前的ConcurrentHashMap底层采用：分段的数组+链表，分段数组的长度一旦初始化就不能改变。
- Java8之后采用：数组+链表/红黑二叉树。
（3）锁机制
- Java7之前使用的是**分段锁（ReentrantLock锁）**保证线程安全
- Java8之后使用的是synchronized 和 CAS 来保证线程安全，通过CAS修改数组节点的值，然后synchronized 锁定当前链表或红黑二叉树的首节点。
3. HashMap、Hashtable、ConcurrentHashMap
| 特性 | HashMap | Hashtable | ConcurrentHashMap |
|---|---|---|---|
| 线程安全性 | 否 | 是 | 是 |
| 锁机制 | 无 | 整个表锁 | 分段锁（Java 7）或桶级锁（Java 8 及以后） |
| 性能 | 高（单线程环境） | 低（由于使用同步方法，整体锁影响性能） | 高（高并发场景下比 Hashtable 性能更好） |
允许 null 键和值 | 是 | 否 | 否 |
| 初始容量与负载因子 | 默认初始容量 16，负载因子 0.75 | 默认初始容量 11，负载因子 0.75 | 默认初始容量 16，负载因子 0.75 |
| 扩容机制 | 容量加倍 | 容量加倍 | 容量加倍 |
| 底层数据结构 | 数组 + 链表 + 红黑树（Java 8 及以后） | 数组 + 链表 | 数组 + 链表 + 红黑树（Java 8 及以后） |
| 遍历方式 | Iterator | Enumeration | Iterator |
| 引入版本 | JDK 1.2 | JDK 1.0 | JDK 1.5 |
| 主要用途 | 非线程安全环境 | 线程安全，但性能低，已过时 | 高并发环境 |
| 实现接口 | Map, Cloneable, Serializable | Map, Cloneable, Serializable | ConcurrentMap, Serializable |
（四）Collections 工具类常用方法（面试手撕算法）
| 方法签名 | 描述 |
|---|---|
static <T> void sort(List<T> list) | 根据元素的自然顺序对指定列表按升序进行排序。 |
static <T> void sort(List<T> list, Comparator<? super T> c) | 根据指定比较器产生的顺序对指定列表进行排序。 |
static <T> int binarySearch(List<? extends T> list, T key) | 使用二分搜索法搜索指定列表，以获得指定对象。 |
static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) | 使用二分搜索法搜索指定列表，以获得指定对象。 |
static void reverse(List<?> list) | 反转指定列表中元素的顺序。 |
static void shuffle(List<?> list) | 使用默认随机源随机排列指定列表中的元素。 |
static void shuffle(List<?> list, Random rnd) | 使用指定的随机源随机排列指定列表中的元素。 |
static <T> void swap(List<T> list, int i, int j) | 交换指定列表中指定位置的元素。 |
static void rotate(List<?> list, int distance) | 旋转指定列表中的元素。 |
static void fill(List<? super T> list, T obj) | 用指定元素替换指定列表中的所有元素。 |
static <T> void copy(List<? super T> dest, List<? extends T> src) | 将一个列表中的所有元素复制到另一个列表。 |
static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) | 返回根据元素的自然顺序给定集合中的最小元素。 |
static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) | 根据指定的比较器返回给定集合中的最小元素。 |
static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) | 返回根据元素的自然顺序给定集合中的最大元素。 |
static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) | 根据指定的比较器返回给定集合中的最大元素。 |
static int frequency(Collection<?> c, Object o) | 返回指定集合中等于指定对象的元素数。 |
static boolean disjoint(Collection<?> c1, Collection<?> c2) | 如果两个指定集合没有相同的元素，则返回 true。 |
