CC 咖啡猫的工作空间 Coding Space
Dev Guide / Java开发技术guide / java content/dev-guide/a-Java开发技术guide/02-java/2-集合框架.md
  1. 集合框架：Collection接口，子集合框架：List（常用ArrayList、双端队列LinkedList）、Set（常用HashSet、LinkedHashSet、TreeSet）、Queue（常用优先级队列PriorityQueue、双端队列Deque）。Map接口（常用HashMap、子类LinkedHashMap、TreeMap）
  2. List
  • ArrayList：动态数组，线程不安全，可重复，可排序。
  • LinkedList：双向链表（JDK1.6 之前为循环链表，JDK1.7 取消了循环），线程不安全，可重复，可排序。适用场景：必须实现 List + Deque。99% 的情况下，ArrayDeque 都比 LinkedList 更好。LinkedList 基本上已经很少使用了（使用ArrayDeque或ConcurrentLinkedQueue代替）。
  • vector、stack：很少使用。
  1. Set
  • HashSet：基于 HashMap 实现的，底层采用 HashMap 来保存元素。
  • LinkedHashSet：基于 LinkedHashMap 实现的，底层采用 LinkedHashMap 来保存元素。
  • TreeSet：基于 TreeMap 实现的，底层采用 TreeMap 来保存元素。
  1. Queue（数据流转管道（FIFO），核心诉求是“先进先出”）
  • Deque：双端队列父类接口，。
  • ArrayDeque：双端队列，基于循环数组实现，非并发队列（即线程不安全，适用于单线程场景），比 Stack 快，比 LinkedList 省内存。
  • PriorityQueue：优先级队列（无界），基于二叉堆实现，非线程安全。可自定义排序规则，不允许空值和非 Comparable 值。适用于单线程环境下的任务优先级排序。
  • BlockingQueue：阻塞队列（线程安全的阻塞等待机制，阻塞队列在队列满/空时会阻塞线程，直到条件满足），可重复，可排序。
  1. Map
  • HashMap：JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。
  • LinkedHashMap：LinkedHashMap 继承自 HashMap，底层基于拉链式散列结构即由数组和链表或红黑树组成，在此基础上又添加了双向链表，保持底层结构中键值对的插入顺序，同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
  • TreeMap：基于红黑树实现，红黑树是一种自平衡二叉查找树，在插入、删除、查找时，会自动保持平衡，从而保证查询效率。
  • HashTable：数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的。
  1. 一些底层原理：
  • ArrayList/LinkedList的插入和新增元素：头插法/尾插法，头部删除/尾部删除
  • ArrayList的扩容机制：grow()方法，新容量 = 旧容量 + (旧容量 >> 1)（1.5倍扩容）
  • Set集合：comparable和compareTo（实现排序）
  • HashMap和TreeMap的区别：TreeMap实现NavigableMap接口(支持定向搜索、子集操作、逆序视图、边界操作)和SortedMap接口（排序能力），TreeMap的key必须实现Comparable接口或者使用Comparator接口进行排序。HashMap不支持排序，key不能重复。
  • HashMap的底层原理：数组+链表+红黑树，链表长度大于8时转化为红黑树，红黑树节点小于6时转化为链表。
  • HashMap的扩容机制：扩容因子0.75，扩容时容量为原来的2倍，扩容时需要重新计算hash值，重新计算索引位置，重新插入。
  • HashMap多线程操作导致死循环、线程不安全
  • ConcurrentHashMap的底层原理：分段锁，每个段是一个HashEntry数组，每个段是一个锁，多线程操作不同段的数据时，不会发生冲突，提高并发性。
  • “线程不安全”的本质：底层代码在读写共享状态时，没有加锁、没有使用原子操作、也没有保证内存可见性，因此多线程并发操作时会出现数据错乱、丢失或程序崩溃。
  • 集合迭代策略：java.util.* 集合遍历时遇到结构修改，遵守 fast-fail（快速失败） 机制，会抛出ConcurrentModificationException异常（一旦多线程误用，立刻崩溃暴露 Bug，避免隐蔽的数据损坏）。java.util.concurrent.* 集合遍历时遇到结构修改，遵守 fail-safe(安全失败)/ 弱一致性 机制，不会抛出异常（追求吞吐与可用性，放弃强一致性，允许遍历期间看到“旧数据”或“部分新数据”，但绝不中断业务）。
  1. 集合框架源码分析

  • ArrayList：

    • 底层基于动态数组实现，初始容量10
    • 扩容机制：grow()方法，新容量 = 旧容量 + (旧容量 >> 1)（1.5倍扩容）
    • System.arraycopy()进行数组复制，时间复杂度O(n)
    • 非线程安全，多线程环境下需外部同步

  • LinkedList：双端队列。

    • 底层基于双向链表实现（Node内部类）
    • 头尾指针first/last，支持O(1)的头尾插入删除
    • get(index)需要遍历，时间复杂度O(n)
    • 非线程安全

  • HashMap

    • JDK8后采用数组+链表+红黑树结构
    • 初始容量16，负载因子0.75，阈值=容量*负载因子
    • hash扰动函数：(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
    • 链表转红黑树阈值：TREEIFY_THRESHOLD=8，数组长度>=64
    • 红黑树转链表阈值：UNTREEIFY_THRESHOLD=6
    • 扩容时rehash采用高位bit判断，避免重新计算hash

  • ConcurrentHashMap

    • JDK8后采用Node数组+CAS+synchronized实现
    • 分段锁思想演进为CAS+synchronized锁单个桶
    • sizeCtl控制字段：-1表示初始化，-N表示有N-1个线程在扩容
    • 扩容时支持多线程协助扩容（transfer方法）
    • 计数采用CounterCell数组分段计数，减少竞争

  • LinkedHashMap

    • 继承HashMap，额外维护双向链表记录访问顺序
    • accessOrder字段控制是插入顺序还是访问顺序
    • afterNodeAccess()、afterNodeInsertion()、afterNodeRemoval()钩子方法
    • 可用于实现LRU缓存（removeEldestEntry()方法）

  • ArrayBlockingQueue：单锁（1个ReentrantLock+2个Condition）

    • 底层基于定长数组实现循环队列
    • notEmpty和notFull两个Condition分别用于take和put操作的等待通知
    • 入队offer()和出队poll()都是非阻塞操作
    • put()和take()是阻塞操作，会await对应Condition

  • LinkedBlockingQueue：双锁（putLock生产锁+takeLock消费锁），不传参时默认容量为Integer.MAX_VALUE

    • 底层基于单向链表实现
    • 生产者和消费者使用不同的锁，提高并发度
    • count字段用AtomicInteger保证原子性
    • 无界队列可能导致内存溢出，需注意容量限制

  • PriorityQueue优先级队列

    • 底层基于二叉堆（数组实现的小顶堆）
    • offer()调用siftUpComparable()向上调整
    • poll()调用siftDownComparable()向下调整
    • 非线程安全，元素必须实现Comparable接口或提供Comparator

  • DelayQueue延迟队列

    • 内部封装PriorityQueue，按到期时间排序
    • 元素必须实现Delayed接口
    • take()操作会阻塞直到有元素到期
    • 使用leader-follower模式优化线程等待

  • ConcurrentLinkedQueue：基于链表的无界非阻塞队列，基于 CAS 实现的线程安全。

    • 采用Michael & Scott算法实现
    • head和tail指针可能滞后，通过hop域优化
    • offer()使用CAS更新tail，poll()使用CAS更新head
    • 弱一致性：size()方法需要遍历，结果可能不准确
  1. 队列框架汇总
  • 阻塞队列（JVM 进程内内存数据结构）：ArrayBlockingQueue（有界阻塞队列，适用于线程池任务队列，追求内存紧凑）、LinkedBlockingQueue(有界阻塞队列，适用于线程池任务队列，追求高并发吞吐、生产者-消费者模型、异步解耦)、PriorityBlockingQueue（基于优先级的无界阻塞队列）、DelayQueue（延迟触发的无界阻塞队列）、SynchronousQueue（零容量的同步移交队列，应用场景：Executors.newCachedThreadPool() 的任务队列，实现线程复用）
  • 非阻塞队列（CAS实现线程安全，适合高并发场景）：ConcurrentLinkedQueue（基于链表的无界非阻塞队列，无锁非阻塞队列）、ConcurrentLinkedDeque（双端无界非阻塞队列）
  • 非并发队列（线程不安全，仅适用于单线程场景）：LinkedList（实现了Deque接口，线程不安全，多线程下配合synchronized使用）、ArrayDeque（基于数组的双端队列，线程不安全，适用于单线程栈或队列操作）
  • 优先级队列：PriorityQueue（基于二叉堆的优先级队列，无界队列，线程不安全，适用于单线程任务优先级排序）