一、为什么要有集合？

Student[] arr = new Student[10];
// 问题1：长度不可变
arr[11] = new Student();  // 数组越界异常
// 问题2：不便于删除、添加
// arr.remove();  // 数组没有这些方法
// arr.add();

二、集合的体系结构

Collection接口：单列集合的顶级接口
    |-- List接口：有序、可重复、有索引
        |-- ArrayList类：底层是动态数组，查询快、增删慢
        |-- Vector类：线程安全的ArrayList（已过时，不推荐使用）
        |-- LinkedList类：底层是双向链表，增删快、查询慢
        |-- Stack类：栈结构，继承自Vector
    |-- Set接口：不可重复
        |-- HashSet类：基于HashMap实现，无序
            |-- LinkedHashSet：基于LinkedHashMap实现，有序
        |-- TreeSet类：基于红黑树实现，可排序
        |-- EnumSet类：枚举专用Set
        |-- CopyOnWriteArraySet：线程安全的Set

Map接口：key-value键值对集合
    |-- HashMap类：基于哈希表，无序
        |-- LinkedHashMap：有序的HashMap
    |-- TreeMap类：基于红黑树，可排序
    |-- Hashtable：线程安全的HashMap，不允许null键值
        |-- Properties：属性文件操作专用
    |-- ConcurrentHashMap：高并发场景下的线程安全Map
    |-- WeakHashMap：弱引用Map
    |-- IdentityHashMap：使用==代替equals比较
    |-- EnumMap：枚举专用Map

三、Collection接口

是什么？

• 单列集合的顶级接口

• 定义了单列集合的通用方法

常用方法：

• boolean add(E e)：添加元素

• boolean remove(Object o)：删除指定元素

• int size()：返回元素个数

• boolean isEmpty()：判断是否为空

• boolean contains(Object obj)：判断是否包含元素

• Iterator<E> iterator()：返回迭代器

• void clear()：清空集合

• boolean containsAll(Collection<?> c)：是否包含指定集合所有元素

• boolean addAll(Collection<? extends E> c)：添加指定集合所有元素

• boolean removeAll(Collection<?> c)：删除指定集合所有元素

• boolean retainAll(Collection<?> c)：保留指定集合中的元素

• Object[] toArray()：转换为数组

• <T> T[] toArray(T[] a)：转换为指定类型数组

• default Stream<E> stream()：返回流（JDK8+）

• default Stream<E> parallelStream()：返回并行流（JDK8+）

四、List接口

是什么？

• Collection的子接口

• 有序、可重复、有索引

特有方法：

• void add(int index, E element)：指定位置插入元素

• E get(int index)：获取指定位置元素

• E set(int index, E element)：修改指定位置元素

• E remove(int index)：删除指定位置元素

• int indexOf(Object o)：返回首次出现的索引

• int lastIndexOf(Object o)：返回最后出现的索引

• ListIterator<E> listIterator()：列表迭代器

• List<E> subList(int fromIndex, int toIndex)：截取子列表

实现类详解：

1. ArrayList

• 数据结构：动态数组

• 初始容量：10

• 扩容机制：1.5倍扩容

• 优点：

  • 随机访问快（O(1)）

  • 尾部添加效率高

• 缺点：

  • 增删元素需要移动元素，效率低

  • 内存空间连续，需要大块连续内存

• 线程安全：不安全

• 使用场景：查询多、增删少的场景

// ArrayList源码关键点
transient Object[] elementData;  // 实际存储数组
private int size;  // 元素个数
private static final int DEFAULT_CAPACITY = 10;  // 默认初始容量

2. LinkedList

• 数据结构：双向链表

• 优点：

  • 增删元素快（O(1)）

  • 内存空间不连续

• 缺点：

  • 随机访问慢（O(n)）

• 线程安全：不安全

• 特有方法：

  • addFirst(E e)/ addLast(E e)

  • getFirst()/ getLast()

  • removeFirst()/ removeLast()

• 使用场景：增删多、查询少的场景

// LinkedList源码关键点
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}
transient Node<E> first;  // 头节点
transient Node<E> last;   // 尾节点

3. Vector

• 数据结构：动态数组

• 初始容量：10

• 扩容机制：2倍扩容

• 优点：线程安全（方法都加了synchronized）

• 缺点：性能差

• 替代方案：使用Collections.synchronizedList()或CopyOnWriteArrayList

• 子类：Stack（栈结构）

4. CopyOnWriteArrayList（重要）

• 特点：写时复制，线程安全

• 原理：写操作时复制新数组，读操作无锁

• 优点：读性能高，适合读多写少场景

• 缺点：内存占用大，数据一致性弱

• 使用场景：高并发读，低并发写

五、Set接口

是什么？

• Collection的子接口

• 不可重复，最多一个null元素

• 无索引

实现类详解：

1. HashSet

• 数据结构：数组+链表+红黑树（JDK8+）

• 底层实现：基于HashMap

• 特点：无序、不重复

• 允许null：允许一个null元素

• 线程安全：不安全

• 重要参数：

  • 默认初始容量：16

  • 负载因子：0.75f

  • 树化阈值：8

  • 退化阈值：6

  • 最小树化容量：64

2. LinkedHashSet

• 数据结构：数组+双向链表

• 底层实现：基于LinkedHashMap

• 特点：有序（插入顺序）、不重复

• 优点：既保证了Set的特性，又保持了插入顺序

• 使用场景：需要保持插入顺序的Set

3. TreeSet

• 数据结构：红黑树

• 特点：可排序、不重复

• 排序方式：

  • 自然排序：元素实现Comparable接口

  • 定制排序：创建时传入Comparator

• 线程安全：不安全

• 使用场景：需要排序的Set

六、Map接口

是什么？

• 双列集合，key-value键值对

• key不可重复，value可重复

• 一个key对应一个value

常用方法：

• V put(K key, V value)：添加/修改

• V remove(Object key)：删除

• V get(Object key)：获取

• boolean containsKey(Object key)：是否包含key

• boolean containsValue(Object value)：是否包含value

• int size()：元素个数

• Set<K> keySet()：获取所有key

• Collection<V> values()：获取所有value

• Set<Map.Entry<K, V>> entrySet()：获取所有键值对

• default V getOrDefault(Object key, V defaultValue)：获取或默认值

• default void forEach(BiConsumer<? super K,? super V> action)：遍历

实现类详解：

1. HashMap

• 数据结构：数组+链表+红黑树（JDK8+）

• 特点：无序、允许null键值

• 线程安全：不安全

• 重要参数：

  • 默认初始容量：16

  • 默认负载因子：0.75

  • 扩容阈值：容量*负载因子

  • 树化阈值：8

  • 退化阈值：6

  • 最小树化容量：64

// HashMap底层原理详解
/**
 * 存储过程：
 * 1. 计算key的hash值：hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
 * 2. 计算索引：index = (n - 1) & hash
 * 3. 如果该位置为空，直接放入
 * 4. 如果该位置不为空：
 *    a. 比较hash值和equals，相同则替换
 *    b. 如果是树节点，放入红黑树
 *    c. 如果是链表，遍历到尾插入
 * 5. 判断链表长度是否>=8，是则转为红黑树
 */

/**
 * 扩容机制：
 * 1. 当size > threshold时扩容
 * 2. 新容量 = 旧容量 * 2
 * 3. 重新计算所有元素的位置
 * 4. 如果是树节点，判断是否需要拆分为链表
 */

2. LinkedHashMap

• 数据结构：数组+双向链表

• 特点：有序（插入顺序或访问顺序）

• accessOrder参数：

  • false：插入顺序（默认）

  • true：访问顺序（适合实现LRU缓存）

• 继承关系：继承HashMap

• 使用场景：需要保持顺序的Map

3. TreeMap

• 数据结构：红黑树

• 特点：可排序

• 排序方式：

  • 自然排序：key实现Comparable

  • 定制排序：传入Comparator

• 线程安全：不安全

• 使用场景：需要排序的Map

4. Hashtable

• 特点：线程安全、不允许null键值

• 与HashMap区别：

  • 线程安全（方法加synchronized）

  • 不允许null键值

  • 初始容量11，扩容2n+1

  • 继承Dictionary（已过时）

• 替代方案：使用ConcurrentHashMap

七、工具类

1. Collections

• 排序：sort(), reverse(), shuffle()

• 查找：binarySearch(), max(), min()

• 同步包装：synchronizedList(), synchronizedSet(), synchronizedMap()

• 不可变集合：unmodifiableList(), unmodifiableSet(), unmodifiableMap()

• 单元素集合：singletonList(), singletonSet(), singletonMap()

• 空集合：emptyList(), emptySet(), emptyMap()

2. Arrays

• 数组转集合：asList()

• 排序：sort()

• 二分查找：binarySearch()

• 填充：fill()

• 比较：equals()

• 字符串：toString()

八、迭代器

1. Iterator

// 基本使用
Iterator<String> it = list.iterator();
while(it.hasNext()) {
    String s = it.next();
    it.remove();  // 安全删除
}

2. ListIterator

// 双向遍历
ListIterator<String> lit = list.listIterator();
while(lit.hasNext()) {
    String s = lit.next();
}
while(lit.hasPrevious()) {
    String s = lit.previous();
}

3. fail-fast机制

• 快速失败机制

• 遍历时修改集合会抛出ConcurrentModificationException

• 原理：比较modCount和expectedModCount

九、性能对比

集合类	数据结构	查询	增删	线程安全	有序	允许null
ArrayList	数组	O(1)	O(n)	否	插入序	是
LinkedList	链表	O(n)	O(1)	否	插入序	是
HashSet	哈希表	O(1)	O(1)	否	无序	是
LinkedHashSet	哈希表+链表	O(1)	O(1)	否	插入序	是
TreeSet	红黑树	O(log n)	O(log n)	否	排序序	否
HashMap	哈希表	O(1)	O(1)	否	无序	是
LinkedHashMap	哈希表+链表	O(1)	O(1)	否	插入序	是
TreeMap	红黑树	O(log n)	O(log n)	否	排序序	否
ConcurrentHashMap	分段锁/红黑树	O(1)	O(1)	是	无序	否

十、使用建议

1. 单列集合选择：

   • 需要唯一性：Set

   • 需要顺序、可重复：List

   • 需要排序：TreeSet/TreeMap

   • 需要保持插入顺序：LinkedHashSet/LinkedHashMap

2. 多线程环境：

   • 高并发读：CopyOnWriteArrayList/CopyOnWriteArraySet

   • 高并发读写：ConcurrentHashMap

   • 低并发：Collections.synchronizedXXX()

3. 内存考虑：

   • 内存敏感：EnumSet/EnumMap

   • 大容量：ArrayList（连续内存）

4. 性能优化：

   • 预估容量，避免频繁扩容

   • 选择合适的负载因子

   • 合理实现hashCode()和equals()

十一、常见面试题

1. ArrayList和LinkedList区别？

2. HashMap的put过程？

3. ConcurrentHashMap原理？

4. HashMap和Hashtable区别？

5. fail-fast和fail-safe机制？

6. HashSet如何保证元素唯一？

7. TreeMap排序原理？

8. HashMap的负载因子为什么是0.75？

9. ConcurrentHashMap1.7和1.8区别？

10. 如何解决哈希冲突？

这个完整的集合框架总结涵盖了Java集合的所有重要实现类，包括它们的特性、使用场景和底层原理，适合发布到CSDN等技术博客平台。