当前位置：首页 > article >正文

Java集合框架中常用类及其底层数据结构的详细分类

article 2025/2/22 16:05:38

1. 数组（Array）

特点：内存连续，支持随机访问，增删效率低（需扩容或移动元素）。

ArrayList
基于动态数组，扩容时创建新数组并拷贝数据（默认扩容 1.5 倍）。
Vector
线程安全的动态数组，扩容策略与 ArrayList 类似（默认扩容 2 倍）。
ArrayDeque
基于循环数组实现的双端队列，支持高效的头尾插入和删除。
HashMap 的桶数组
存储链表头或红黑树根节点，通过哈希函数定位桶位置。
PriorityQueue
基于数组实现二叉堆（逻辑上是完全二叉树，物理存储是数组）。

2. 链表（Linked List）

特点：内存不连续，增删效率高，随机访问效率低。

LinkedList
双向链表实现，每个节点存储前后节点引用。
LinkedHashMap
继承 HashMap，通过双向链表维护键的插入顺序或访问顺序。
LinkedHashSet
基于 LinkedHashMap 实现，通过链表维护元素插入顺序。
HashMap 的冲突链表（JDK 8 前）
哈希冲突时，桶内元素以链表形式存储（JDK 8 后链表可能转为红黑树）。

3. 树（Tree）

特点：有序存储，支持高效查找、插入和删除（时间复杂度 O(log n)）。

TreeMap
基于红黑树（自平衡二叉搜索树），键按自然顺序或 Comparator 排序。
TreeSet
基于 TreeMap 实现，元素按自然顺序或 Comparator 排序。
HashMap 的红黑树（JDK 8+）
当单个桶的链表长度超过 8 且哈希表容量 ≥64 时，链表转为红黑树。

4. 栈（Stack）

特点：后进先出（LIFO），通过限制操作实现栈语义。

Stack
继承自 Vector，基于数组实现（已过时，不推荐使用）。
Deque 接口的实现类
如 ArrayDeque 或 LinkedList，通过 push() 和 pop() 模拟栈操作。

5. 堆（Heap）

特点：优先队列，按优先级出队（通常是小顶堆或大顶堆）。

PriorityQueue
基于数组实现二叉堆，通过 Comparator 或自然顺序维护优先级。

6. 队列（Queue）

特点：先进先出（FIFO）或按优先级出队。

LinkedList
双向链表实现普通队列。
ArrayDeque
循环数组实现双端队列。
PriorityQueue
二叉堆实现优先队列。
BlockingQueue 实现类（如 ArrayBlockingQueue、LinkedBlockingQueue）
基于数组或链表的线程安全队列。

7. 图（Graph）

特点：表示节点与边的关系，Java 标准库未直接提供图实现。

第三方库（如 JGraphT）
提供邻接表、邻接矩阵等图的实现。
自定义实现
可通过 Map<Node, List<Edge>>（邻接表）或二维数组（邻接矩阵）表示图。

数据结构与集合类对照表

数据结构	集合类	应用场景
数组	ArrayList, Vector, ArrayDeque, HashMap 的桶数组, PriorityQueue	频繁随机访问、队列操作、哈希存储
链表	LinkedList, LinkedHashMap, LinkedHashSet, HashMap 的冲突链表（JDK8前）	频繁增删、维护插入顺序
树	TreeMap, TreeSet, HashMap 的红黑树（JDK8+）	有序存储、范围查询、高频哈希冲突优化
栈	Stack（过时）, Deque 的实现类（如 ArrayDeque）	函数调用栈、括号匹配、表达式求值
堆	PriorityQueue	任务调度、求 Top K 问题、哈夫曼编码
队列	LinkedList, ArrayDeque, PriorityQueue, BlockingQueue 实现类	消息队列、线程池任务队列、广度优先搜索
图	需第三方库或自定义实现（如 JGraphT）	社交网络、路径规划、依赖关系分析

示例代码说明

// 数组结构示例（ArrayList）
List<Integer> list = new ArrayList<>();
list.add(1); // 触发扩容时拷贝数组

// 链表结构示例（LinkedList）
Deque<Integer> deque = new LinkedList<>();
deque.addFirst(10); // 修改链表头节点

// 树结构示例（TreeMap）
TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("b", 2); // 红黑树插入平衡操作

// 堆结构示例（PriorityQueue）
PriorityQueue<Integer> heap = new PriorityQueue<>();
heap.offer(5); // 上浮调整堆结构

// 队列示例（ArrayBlockingQueue）
BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(10);
queue.put(1); // 数组循环写入