【Java集合夜话】第2篇：Collection家族，一场优雅的探索之约

在上一章中，我们对Java集合框架有了整体认识。🌹
现在，让我们深入探索Collection家族中的每位"明星成员"，不仅要了解它们的特性，更要掌握一些实用的记忆技巧，帮助你对这些集合类型烂熟于心。🌹
如有描述不准确之处，欢迎大家指出交流。🌹

Java Collection接口家族详解

在Java集合框架中，Collection接口家族就像一个精心设计的工具箱，每个工具都有其独特的用途。本文将深入介绍这些"明星"集合类，带你掌握它们的特点和最佳实践。

Collection框架概览

下面用一张图来表示Collection家族之间的关系，以及里面的一些常见集合的优缺点。

Collection接口家族主要成员

• List: 有序可重复集合
  • ArrayList：最常用的List实现,
  • LinkedList：适合频繁增删的场景
  • Vector：早期的线程安全实现
• Set: 不重复集合
  • HashSet：无序唯一集合
  • LinkedHashSet：有序唯一集合
  • TreeSet：排序唯一集合
• Queue: 队列集合
  • PriorityQueue：优先队列
  • Deque：双端队列
  • Stack：后进先出栈
  • ArrayDeque：数组双端队列
  • ConcurrentLinkedQueue：并发队列

List详解

由浅：

常见实现类对比

ArrayList

• 基于动态数组实现
• 查询速度快，插入和删除慢
• 需要考虑扩容机制
• 最常用的List实现

最常用的List实现,是基于动态数组实现（之所以叫动态是因为数组容量可以动态变化）、查询速度快、插入和删除慢。这点很容易理解，数组一般需要一开始就定义好容量，如果空间不够用了， 需要扩容，重新定义一个大的空间（怎么定义大空间又涉及到扩容机制，这里浅的时候咱不细谈）。然后将元素全部在放到这个空间中去，这里的操作会有时间成本问题。但是因为是数组实现，可以通过寻址立马查到某一个元素，所以效率高。

LinkedList

• 基于双向链表实现
• 插入删除快，查询慢
• 不存在扩容问题
• 适合频繁增删场景

适合频繁增删的场景,LinkedList可以和ArrayList做一个鲜明的对比：LinkedList采用双向链表实现,由一个个Node节点通过前后指针相连。由于链表结构的特性,它不需要像数组那样预分配连续空间,只要堆内存充足就可以不断添加节点。在插入操作时,只需修改插入位置前后节点的指针指向即可,不需要像ArrayList那样移动大量元素;删除操作也只需要修改待删除节点前后节点的指针指向,操作复杂度都是O(1)。但需要注意的是,虽然增删效率高,但查找元素时需要遍历链表,性能不如ArrayList。

Vector

• 线程安全版ArrayList
• 性能较差（synchronized实现）
• 已被CopyOnWriteArrayList替代

早期的线程安全实现, Vector又可以和ArrayList做一个鲜明的对比：两个都是基于动态数组实现，但是Vector是线程安全的，所以他的方法都加了synchronized关键字，但正是由于这个原因，所以它的效率低。
这里大家要知道synchronized是一个重量级的锁，在并发量大的情况下，性能会下降。所以我们基本上很少使用Vector。而是使用CopyOnWriteArrayList。

源码深入分析

入深：

1. ArrayList源码解析

// 底层数组实现
transient Object[] elementData;

// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;

// 核心扩容方法
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容为原来的1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

ArrayList的核心原理主要体现在以下几个方面：

1. 扩容机制

• 当容量不足时，会触发grow方法进行扩容
• 默认扩容为原容量的1.5倍(oldCapacity + oldCapacity >> 1)
• 扩容过程中会创建新数组并复制元素，性能开销较大
• 因此在已知元素数量的情况下，建议使用带初始容量的构造方法

2. 线程安全性

• ArrayList是非线程安全的
• 多线程并发修改时可能导致数据不一致
• 如需线程安全可以：
  1. 使用Collections.synchronizedList()包装
  2. 使用CopyOnWriteArrayList
  3. 自行加锁控制并发访问

3. 删除元素原理

• 删除指定位置元素时，会将该位置后的所有元素向前移动一位
• 元素移动通过System.arraycopy实现
• 删除操作的时间复杂度为O(n)
• 频繁删除场景建议使用LinkedList

4. 遍历性能

• 支持随机访问，通过索引访问元素的时间复杂度为O(1)
• for循环遍历性能优于迭代器遍历
• 不要在遍历过程中对List进行结构性修改，会导致ConcurrentModificationException

这些特性决定了ArrayList适合读多写少的场景，不适合频繁增删和并发访问的场景。在使用时需要根据实际情况权衡选择合适的List实现类。

2. LinkedList源码解析

// 节点定义
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

// 头尾指针
transient Node<E> first;
transient Node<E> last;

// 添加元素实现
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

LinkedList的核心特性和实现原理：

1. 基本结构

• 采用双向链表实现，每个节点包含前驱和后继指针
• 维护first和last指针指向链表头尾
• 不需要预分配容量，按需分配内存

2. 增删元素原理

• 增加元素时只需修改相邻节点的指针，时间复杂度O(1)
• 删除元素时也只需修改相邻节点的指针，时间复杂度O(1)
• 不需要像ArrayList那样移动大量元素
• 但需要遍历找到插入/删除位置，这部分时间复杂度为O(n)

3. 访问性能

• 不支持随机访问，需要从头/尾遍历找到目标位置
• 访问任意位置元素的时间复杂度为O(n)
• 顺序访问性能较好，可以利用双向特性选择更短的遍历路径

4. 内存占用

• 每个节点需要额外的指针空间
• 空间利用率相对ArrayList较低
• 但不会因为动态扩容产生空间浪费

5. 并发控制

• 非线程安全
• 可以用Collections.synchronizedList()包装实现同步
• 并发修改会导致ConcurrentModificationException

这些特性决定了LinkedList适合频繁增删元素的场景，不适合随机访问和查找的场景。在选择List实现类时需要根据具体使用场景权衡。

3. CopyOnWriteArrayList源码解析

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

CopyOnWriteArrayList的核心原理分析:

1. 写时复制机制

• 每次写操作都会复制一个新数组
• 修改在新数组上进行,不影响原数组
• 最后用新数组替换老数组
• 保证读操作不受写操作影响

2. 线程安全实现

• 写操作使用ReentrantLock加锁
• 读操作不加锁,因为读取的是不变的数组
• 读写分离,实现了最大程度的并发
• 适合读多写少的场景

3. 数据一致性

• 写操作对读操作不可见,属于弱一致性
• 读操作可能读到旧数据
• 但保证最终一致性
• 牺牲实时性换取性能

4. 性能特点

• 读操作性能很好,无锁且不会被阻塞
• 写操作性能较差,需要复制数组
• 内存占用较大,每次修改都创建新数组
• 不适合频繁写入的场景

5. 迭代器特性

• iterator返回的是某个时刻的快照
• 不会抛出ConcurrentModificationException
• 但可能看不到最新修改的数据
• 适合遍历时对一致性要求不高的场景

性能对比与最佳实践

Set详解

常见实现类对比

HashSet

• 基于HashMap实现
• 无序不重复集合
• 查找性能好O(1)
• 最常用的Set实现

最常用的Set实现,基于HashMap实现。利用HashMap的key不可重复特性,实现了元素的唯一性。查找性能好,但不保证元素顺序。

LinkedHashSet

• 继承自HashSet
• 维护元素插入顺序
• 性能略低于HashSet
• 适合需要记录插入顺序的场景

基于LinkedHashMap实现,在HashSet的基础上通过双向链表维护了元素的插入顺序。虽然性能略低于HashSet,但是可以按照插入顺序遍历元素。

TreeSet

• 基于红黑树实现
• 元素自动排序
• 查找性能O(log n)
• 适合需要排序的场景

基于TreeMap实现的有序Set集合,可以自动对元素进行排序。查找性能不如HashSet,但是提供了有序性保证。

源码深入分析

1. HashSet源码解析

// HashMap中的Node节点结构
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;  // 哈希值
    final K key;     // 键
    V value;         // 值
    Node<K,V> next;  // 链表中的下一个节点
}

// HashMap的put方法核心实现
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
              boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 1. 如果表为空则创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2. 计算索引并插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 3. 处理哈希冲突
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 4. 链表处理
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
    }
    return null;
}

从上面的源码中，我们可以总结出HashSet的几个关键原理：

1. 存储结构

• HashSet内部使用HashMap实现，将元素存储为HashMap的key
• HashMap的value统一为一个PRESENT常量对象
• 利用HashMap的key不可重复特性实现Set的唯一性

2. 哈希冲突处理

• 当不同元素hash值相同时，使用链表法解决冲突
• 链表长度超过阈值(8)时转为红黑树
• 红黑树节点数小于阈值(6)时退化为链表
• 这种结构保证了即使发生大量哈希冲突，查询性能也不会严重下降

3. 负载因子机制

• 默认负载因子为0.75
• 当元素数量超过容量*负载因子时触发扩容
• 扩容会重新计算所有元素的位置
• 合理的负载因子在空间和时间上达到平衡

4. 线程安全性

• HashSet是非线程安全的
• 并发修改可能导致数据不一致
• 需要线程安全时可以使用Collections.synchronizedSet()包装
• 或使用ConcurrentHashMap实现线程安全的Set

5. 性能特点

• 利用哈希算法，大多数操作的时间复杂度为O(1)
• 但哈希冲突过多时性能会下降
• 扩容操作比较耗时，应预估元素数量
• 不保证元素顺序，迭代顺序可能发生变化

理解这些原理有助于我们更好地使用HashSet，在适当的场景选择合适的集合类型。

2. LinkedHashSet特点：

• 继承自HashSet，使用LinkedHashMap存储
• 通过双向链表维护插入顺序
• 迭代性能优于HashSet
• 额外内存开销用于维护链表
  核心源码分析：

public class LinkedHashSet<E> extends HashSet<E> {
// 序列化ID
private static final long serialVersionUID = -2851667679971038690L;
// 默认构造函数，初始容量16，负载因子0.75
public LinkedHashSet() {
super(16, .75f, true);
}
// 指定初始容量的构造函数
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
// 指定初始容量和负载因子的构造函数
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
}
// HashSet中的关键实现（LinkedHashSet依赖此实现）
public class HashSet<E> {
// 实际存储数据的Map实例
private transient HashMap<E,Object> map;
// 所有value共用的虚拟对象
private static final Object PRESENT = new Object();
// 构造函数中的dummy参数用于区分不同的构造方法
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
// 关键点：这里使用LinkedHashMap而不是HashMap
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
// 添加元素实际上是将元素作为key存入map
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
}
// LinkedHashMap中维护顺序的关键结构
public class LinkedHashMap<K,V> extends HashMap<K,V> {
// 双向链表的节点结构
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after; // 双向链表的前后引用
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
// 双向链表的头尾节点
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;
// 是否按访问顺序排序（LinkedHashSet中为false，维护插入顺序）
final boolean accessOrder;
}

LinkedHashSet的核心原理分析：

1. 继承关系与底层实现

• 继承自HashSet，但底层使用LinkedHashMap存储
• 通过特殊的构造函数dummy参数区分实现
• 复用了HashSet的大部分功能
• 在HashSet基础上增加了顺序维护

2. 有序性实现机制

• LinkedHashMap通过双向链表维护插入顺序
• Entry节点额外维护before和after引用
• 新增元素时同时维护哈希表和双向链表
• 保证了遍历顺序与插入顺序一致

3. 性能特点

• 查找性能接近O(1)，继承自HashSet的特性
• 插入/删除需要维护链表，性能略低于HashSet
• 相比TreeSet不需要维护平衡树，性能更好
• 额外的链表结构会占用更多内存

4. 线程安全性

• 非线程安全的实现
• 可以通过Collections.synchronizedSet()包装
• 并发修改会导致ConcurrentModificationException

5. 最佳实践

• 需要记录插入顺序时优先使用
• 不要在遍历时修改集合
• 预估容量可以指定初始大小
• 注意equals和hashCode的正确实现

这些特性使LinkedHashSet成为在需要保持插入顺序的场景下的最佳选择，它在HashSet的高性能基础上，很好地解决了元素顺序的问题。

3. TreeSet实现：

• 基于红黑树(TreeMap)实现
• 自平衡二叉查找树保证有序性
• 操作复杂度O(log n)
• 要求元素可比较

// TreeSet的核心实现
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E> {
    // 实际存储结构是TreeMap
    private transient NavigableMap<E,Object> m;
    
    // 所有value共用的虚拟对象
    private static final Object PRESENT = new Object();
    
    // 构造函数使用TreeMap初始化
    public TreeSet() {
        this.m = new TreeMap<E,Object>();
    }
    
    // 添加元素实际调用TreeMap的put方法
    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
}

// TreeMap中的红黑树节点定义
static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;    // 左子节点
    Entry<K,V> right;   // 右子节点 
    Entry<K,V> parent;  // 父节点
    boolean color;      // 节点颜色
}

// 插入后的平衡调整
private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;  // 新节点默认为红色
    
    // 循环向上调整直到满足红黑树性质
    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                // Case 1: 叔叔节点为红色
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                // Case 2&3: 叔叔节点为黑色
                if (x == rightOf(parentOf(x))) {
                    // Case 2: 当前节点是右子节点
                    x = parentOf(x);
                    rotateLeft(x);
                }
                // Case 3: 当前节点是左子节点
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            // 对称处理右子树的情况
            // ...
        }
    }
    root.color = BLACK; // 根节点始终为黑色
}

TreeMap的核心原理分析:

1. 红黑树特性

• 每个节点要么是红色要么是黑色
• 根节点必须是黑色
• 叶子节点(NIL)是黑色
• 红色节点的子节点必须是黑色
• 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点

2. 平衡调整机制

• 插入节点默认为红色
• 通过变色和旋转操作维持红黑树性质
• 主要分为以下情况处理:
  • Case 1: 叔叔节点为红色,只需要变色
  • Case 2&3: 叔叔节点为黑色,需要旋转调整

3. 查找性能

• 平衡树结构保证了O(log n)的查找效率
• 不会像普通二叉树那样退化成链表
• 但比哈希表的O(1)查找效率要低

4. 有序性保证

• 中序遍历可以得到有序序列
• 支持范围查询等操作
• 适合需要排序的场景

5. 使用场景

• 需要有序性保证的Map实现
• 范围查询频繁的场景
• 对插入删除查找速度都有要求的场景
• 内存要求相对不苛刻的场景

性能对比：

• HashSet: O(1)平均查找/插入/删除
• LinkedHashSet: 接近O(1)，额外链表维护
• TreeSet: O(log n)操作但保证顺序

使用建议：

• 无序且追求性能用HashSet
• 需要记录插入顺序用LinkedHashSet
• 需要排序用TreeSet

Queue详解

常见实现类对比

PriorityQueue

• 基于堆实现的优先队列
• 可以自定义优先级规则
• 适合需要动态排序的场景
• 非线程安全

优先队列的典型实现,内部通过小顶堆(或大顶堆)维护元素顺序。每次取出的都是优先级最高的元素,常用于任务调度等场景。

ArrayDeque

• 基于循环数组实现
• 双端队列,支持两端操作
• 性能优于LinkedList
• 适合用作栈或队列

基于循环数组实现的双端队列,可以高效地在两端进行插入和删除操作。相比LinkedList具有更好的性能,是实现栈和队列的理想选择。

ConcurrentLinkedQueue

• 基于链表实现
• 线程安全的队列
• 无锁算法,性能好
• 适合高并发场景

采用CAS等无锁算法实现的线程安全队列,相比传统的同步队列具有更好的并发性能。适合在多线程环境下使用。

源码深入分析

1. PriorityQueue源码解析

// 基于小顶堆实现，父节点小于等于子节点
private transient Object[] queue; // 存储元素的数组
private int size;                 // 元素个数
private final Comparator<? super E> comparator; // 比较器

2. ArrayDeque源码特点：

• 循环数组实现，高效的双端队列
• head和tail标记队列两端
• 容量必须是2的幂，利于位运算优化
• 关键代码：

  public void addFirst(E e) {
      if (e == null)
          throw new NullPointerException();
      elements[head = (head - 1) & (elements.length - 1)] = e;
      if (head == tail)
          doubleCapacity();
  }
  

3. ConcurrentLinkedQueue并发实现：

• 基于CAS操作保证线程安全
• 无锁算法，比传统加锁性能好
• 核心Node节点:

  private static class Node<E> {
      volatile E item;
      volatile Node<E> next;
  }
  

• 入队操作通过CAS保证原子性：

  do {
      p = tail;
      next = p.next;
  } while (!p.casNext(next, node));
  

4. LinkedBlockingQueue阻塞队列实现：

• 基于链表的有界阻塞队列
• 使用两个ReentrantLock控制并发
• 关键属性：

  /** 队列容量 */
  private final int capacity;
  /** 当前元素数量 */
  private final AtomicInteger count = new AtomicInteger();
  /** 入队锁 */
  private final ReentrantLock putLock = new ReentrantLock();
  /** 出队锁 */
  private final ReentrantLock takeLock = new ReentrantLock();
  

• 阻塞等待条件：

  private final Condition notEmpty = takeLock.newCondition();
  private final Condition notFull = putLock.newCondition();
  

5. DelayQueue延时队列：

• 基于PriorityQueue实现
• 元素必须实现Delayed接口
• 只有延迟期满才能被消费
• take()方法核心实现：

  public E take() throws InterruptedException {
      final ReentrantLock lock = this.lock;
      lock.lockInterruptibly();
      try {
          for (;;) {
              E first = q.peek();
              if (first == null)
                  available.await();
              else {
                  long delay = first.getDelay(NANOSECONDS);
                  if (delay <= 0)
                      return q.poll();
                  first = null;
                  available.awaitNanos(delay);
              }
          }
      } finally {
          lock.unlock();
      }
  }
  

博主本人的一个记忆方法，模拟实战拷打

一、学习方法总览

在学习Java集合框架时，我们可以采用"由浅入深"的两步学习方法：

1. 知其然

   • 从接口出发，首先要能回答"这个接口有哪些主要的实现类？"
   • 能够清晰地说出各个实现类的基本特点和区别

2. 知其所以然

   • 深入到具体的实现类，要能够回答以下三个问题：
     • 这个类的底层是如何实现的？
     • 这个类有什么特点和优势？
     • 这个类适用于什么场景？

二、以List接口为例

1. 知其然

List接口的主要实现类包括：

• ArrayList

  • 基于数组实现
  • 随机访问快

• LinkedList

  • 基于链表实现
  • 插入删除快

• Vector

  • 线程安全的数组实现
  • 性能较低

2. 知其所以然

深入分析各实现类：

• ArrayList

  • 核心：扩容机制
  • 重点：扩容时机、扩容策略等原理

• LinkedList

  • 核心：双向链表的数据结构
  • 重点：插入删除操作的具体实现

• Vector

  • 核心：线程安全实现原理
  • 重点：Synchronized带来的性能开销
  • 延伸：Java锁机制（轻量级锁、重量级锁等）

三、方法论推广

这种学习方法可以应用于任何知识领域：

1. 从表层入手

   • 提出基础性问题
   • 给出全面但不深入的第一版答案
   • 确保覆盖问题的各个方面

2. 逐层深入

   • 在理解表层内容基础上提出更深层次问题
   • 不断探索和思考
   • 直到触及自己的知识边界

总结：这种由浅入深，自问自打的学习方式，既能确保知识框架的完整性，又能帮助我们真正掌握知识的本质。