Java 当中内置和开发常用的数据结构主要分为四大类，分别是线性结构树形结构图结构还有哈希相关结构，线性结构包含数组链表队列栈，树形结构包含二叉树平衡二叉树红黑树堆，图结构就是邻接表邻接矩阵实现的图，哈希相关结构核心是哈希表，Java 集合框架里面的 ArrayList LinkedList HashMap TreeSet 这些类本质就是对这些经典数据结构做了工程化封装，日常写业务代码并不是从零手写数据结构，而是直接调用 JDK 提供好的实现类，理解底层原理之后才能选对容器，避免出现扩容频繁线程不安全性能退化这类线上问题，选择数据结构的核心判断依据就是访问方式增删频率排序需求是否需要键值映射是否需要有序，不同数据结构在时间复杂度内存占用上差异很大，选错容器会直接拖慢系统性能。

一 线性数据结构

线性结构特点是元素排成一条直线，每个元素最多只有一个前驱和一个后继，是最基础的数据结构。

1 数组

Java 里面基本类型数组和对象数组，内存是连续分配，支持随机下标访问，查询速度快时间复杂度 O1，但是中间插入删除需要移动大量元素时间复杂度 On，数组创建之后长度固定，这也是它最大局限，ArrayList 底层就是动态数组，内部维护数组，超出容量自动扩容，扩容会复制旧数组元素，代价比较高。

2 链表

链表不需要连续内存，节点保存数据和下一个节点引用，单向链表双向链表循环链表都属于链表，LinkedList 底层是双向链表，头部尾部插入删除很快时间复杂度 O1，但是随机访问需要从头遍历，查询是 On，适合频繁头尾增删，很少随机查询的场景。

3 栈

栈是后进先出 LIFO 结构，只允许在栈顶操作，入栈 push 出栈 pop 取栈顶 peek，JDK 里面 Stack 类已经不推荐使用，一般用 ArrayDeque 实现栈，常用于表达式求值括号匹配方法调用栈撤销回退逻辑。

4 队列

队列是先进先出 FIFO 结构，一端入队另一端出队，普通队列之外还有双端队列 ArrayDeque，还有优先级队列 PriorityQueue 底层是小顶堆，适合任务调度按优先级取出元素。

二 树形数据结构

树是非线性结构，一个根节点向下分叉，每个子节点只有一个父节点，层级存储适合分层数据和快速查找。

1 二叉树

每个节点最多两个子节点，分为左子树右子树，遍历方式有前序中序后序层序遍历，普通二叉树查找没有优化，最坏情况退化成链表。

2 平衡二叉树 AVL 树

严格维持左右子树高度差不超过 1，查找稳定 Ologn，但是每次插入删除之后旋转调整比较频繁，维护成本高。

3 红黑树

红黑树是弱平衡二叉搜索树，JDK 里面 TreeMap TreeSet 底层就是红黑树，节点带有颜色属性红或者黑，通过颜色约束和旋转维持平衡，不需要像 AVL 那样严格高度平衡，插入删除旋转次数更少，综合性能更好，支持按键有序遍历，查询插入删除都是 Ologn。

4 堆

堆是完全二叉树，分为大顶堆小顶堆，父节点和子节点满足大小关系，PriorityQueue 底层小顶堆，适合 topK 问题动态求最值，堆不能按键有序遍历，只能快速拿到堆顶元素。

三 哈希数据结构

哈希表核心思想是哈希函数把 key 映射成数组下标，实现平均 O1 的查找插入删除，哈希冲突是必然存在，Java8 之后 HashMap 底层是数组加链表加红黑树，链表长度超过阈值 8 并且数组长度达到 64 的时候，链表转成红黑树，解决哈希冲突严重之后链表过长查询退化 On 的问题，HashMap 是无序，LinkedHashMap 在 HashMap 基础上增加双向链表，保留插入顺序或者访问顺序，适合 LRU 缓存。

四 图数据结构

图由顶点和边组成，分为有向图无向图，有权图无权图，存储方式两种，邻接矩阵是二维数组，查询边很快但是空间浪费大，顶点多的时候不适合，邻接表是数组加链表，节省内存，适合稀疏图，Java 标准库没有内置图类，业务里面一般自己用 Map List 封装邻接表，常用算法深度优先 DFS 广度优先 BFS 最短路径拓扑排序。

五 JDK 集合框架分类对照表

六 选型核心判断步骤

第一步确认需求，是存单个元素还是键值对，第二步确认是否要求有序，第三步确认操作类型，是查询多还是插入删除多，第四步评估数据量，大数据量要重点关注扩容和时间复杂度，第五步确认线程安全要求，普通这些容器都是非线程安全，多线程场景要换成 ConcurrentHashMap 这类并发容器。

总结下来 Java 数据结构不是孤立的知识点，JDK 集合类全部建立在经典数据结构之上，掌握数组链表树哈希图的原理，理解时间复杂度和底层实现，才能在业务开发正确选择容器，写出高性能稳定的 Java 程序。

【常见问题】

问题 1 Java 数据结构里面 HashMap 底层数据结构为什么在 Java8 改成数组链表加红黑树

回答 1 Java 数据结构里面 HashMap 早期版本只有数组加链表，哈希冲突严重的时候链表会很长，查询时间退化到 On，加入红黑树之后，链表满足阈值就转红黑树，把查询优化成 Ologn，提升哈希冲突极端场景下的性能。

问题 2 Java 数据结构里面 ArrayList 和 LinkedList 底层数据结构有什么本质区别

回答 2 Java 数据结构里面 ArrayList 底层是动态数组，内存连续支持随机下标访问，LinkedList 底层是双向链表，节点分散存储依靠引用串联，随机访问需要遍历，头尾增删效率更高。

问题 3 Java 数据结构里面 TreeMap 底层使用什么数据结构是否有序

回答 3 Java 数据结构里面 TreeMap 底层是红黑树，属于平衡二叉搜索树，存储的时候按照 key 的排序规则保持有序，插入删除查询时间复杂度都是 Ologn。

问题 4 Java 数据结构里面 PriorityQueue 底层是什么数据结构支持随机遍历吗

回答 4 Java 数据结构里面 PriorityQueue 底层是小顶堆，属于完全二叉树，只能快速获取堆顶最小元素，不支持按照大小顺序完整遍历，不能按键有序输出全部元素。

【免责申明】

本文内容基于 JDK 主流版本公开原理整理，仅用于学习理解 Java 数据结构相关知识，不同 JDK 版本底层实现可能存在差异，实际项目开发请结合对应 JDK 源码和业务场景评估，本文不构成任何生产环境技术选型强制建议。