Java数据结构高频面试题及详细答案（真实面试版）

Java数据结构高频面试题及详细答案（真实面试版）一、数据结构基础概念1.说说你对数据结构的理解？常用的数据结构有哪些？数据结构说白了就是数据在内存里的存储和组织方式，不同结构适配不同场景，核心就是取舍查询、增删、占用空间的性能。Java中最常用的就这几类：线性结构：数组、链表、栈、队列哈希结构：哈希表（HashMap、HashTable）树形结构：二叉树、二叉搜索树、平衡树、红黑树图形结构：有向图、无向图（面试考得少，了解即可）堆结构：大顶堆、小顶堆（优先队列底层）2.线性结构和非线性结构的区别？线性结构：元素一对一前后关联，有唯一前驱和唯一后继，遍历是有序的。比如数组、链表、栈、队列。非线性结构：元素一对多或多对多关联，没有严格的前后顺序。比如树、图、哈希表。3.时间复杂度和空间复杂度怎么理解？常见复杂度排序？时间复杂度就是估算代码执行的运算次数，不看常数，只看最高阶，衡量算法快慢；空间复杂度是代码运行过程中额外占用的内存大小。常见复杂度从优到差：O(1)<O(logn)<O(n)<O(nlogn)<O(n²)O(1)：常数级，比如数组随机取值O(logn)：对数级，比如二分查找O(n)：线性级，比如普通遍历数组O(nlogn)：归并排序、快速排序平均情况O(n²)：冒泡、选择排序二、数组与链表（面试重中之重）1.数组和链表的核心区别？各自优缺点？数组：内存连续、固定长度（静态数组），底层是一块连续内存空间。优点：支持随机访问，根据下标查询速度极快O(1)；内存紧凑，无额外开销。缺点：增删元素需要移动大量元素，效率低O(n)；长度固定，扩容需要新建数组拷贝数据，浪费内存。链表：内存不连续，每个节点存数据+下一个节点指针，动态扩容。优点：增删只需要修改指针指向，不需要移动元素，头尾增删效率高O(1)；没有固定长度限制，内存利用率高。缺点：不支持随机访问，查找元素必须从头遍历O(n)；每个节点有指针开销，占用内存更多。2.ArrayList和LinkedList底层区别、使用场景？ArrayList：底层是动态数组，默认初始容量10，扩容1.5倍。LinkedList：底层是双向链表，JDK1.6之前是循环链表，之后改为普通双向链表。使用场景：查询多、增删少，优先用ArrayList（绝大多数业务场景）频繁头尾增删、极少查询，优先用LinkedList注意：LinkedList的中间增删效率依然低，因为需要先遍历找到节点。3.ArrayList扩容机制详细说一下？1.JDK1.8空参创建ArrayList时，初始是空数组，第一次添加元素才初始化容量为10，懒加载机制，节省内存。2.当元素个数超过当前容量，触发扩容：新容量=原容量+原容量/2，也就是1.5倍扩容。3.如果1.5倍扩容后依然不够（比如一次性add大量元素），直接使用所需最小容量。4.扩容本质：新建一个更大的数组，通过数组拷贝把旧数据复制到新数组，废弃旧数组。4.为什么说ArrayList线程不安全？怎么解决？多线程同时添加元素时，会出现两个问题：并发覆盖：多个线程同时给同一个下标赋值，数据被覆盖丢失数组越界：多个线程同时判断容量，都认为不需要扩容，同时添加导致下标越界异常解决方式：使用Vector（效率低，全局锁，不推荐）使用Collections.synchronizedList包装并发场景优先使用CopyOnWriteArrayList（读写分离，写时复制）三、栈与队列1.栈和队列的特点？Java中对应的实现类？栈（Stack）：后进先出LIFO，最后进来的第一个出去。Java实现：Stack类（遗留类，不推荐）、LinkedList（可以模拟栈）、ArrayDeque（推荐）。队列（Queue）：先进先出FIFO，先进来的先出去。Java实现：ArrayDeque、LinkedList、PriorityQueue（优先队列）。2.ArrayDeque为什么比Stack、LinkedList效率高？1.Stack是线程安全的，方法加了synchronized，单线程下有锁竞争开销，效率极低。2.LinkedList是链表结构，有指针开销，每次增删都要创建节点、修改引用。3.ArrayDeque底层是可变数组，无锁、内存连续，头尾操作都是O(1)，性能最优，日常栈队列场景优先用它。3.什么是优先队列？PriorityQueue底层原理？优先队列不遵循先进先出，而是按照自定义优先级排序，优先级高的先出队。PriorityQueue底层是最小堆，基于数组实现的完全二叉树，默认自然排序，也可以自定义比较器实现大顶堆。核心特点：堆顶永远是最值，入队出队时间复杂度O(logn)。四、哈希表与HashMap（核心高频）1.哈希表的底层原理？哈希冲突怎么解决？哈希表核心：通过哈希函数把key转换成数组下标，直接定位存储位置，理想情况下查询、增删都是O(1)。不同key算出相同下标就是哈希冲突，主流解决方式两种：链地址法：数组+链表，冲突元素挂在对应下标链表上（HashMap采用）开放寻址法：冲突后向后寻找空位置（ThreadLocalMap采用）2.JDK1.8HashMap底层结构？为什么要改成数组+链表+红黑树？JDK1.7：数组+单向链表。JDK1.8及以后：数组+单向链表+红黑树。改造原因：当哈希冲突严重，单个链表过长时，链表查询效率会退化成O(n)。红黑树是平衡二叉树，查询效率O(logn)，能大幅优化长链表查询性能。树化阈值：链表长度>=8且数组容量>=64，链表转红黑树。退链阈值：红黑树节点数<=6，树转回链表（避免频繁树化、退树消耗性能）。3.HashMap初始容量、负载因子、扩容机制？初始容量：默认16，必须是2的幂次，方便哈希取模运算。负载因子：默认0.75，代表数组填充比例，权衡空间和查询效率。扩容阈值：容量*负载因子，默认12，元素数量超过阈值触发扩容。扩容规则：容量翻倍（2倍扩容），重新计算所有元素的下标位置，重新映射存储。4.HashMap为什么线程不安全？并发场景用什么？JDK1.7会出现循环链表、数据丢失、死循环问题；JDK1.8解决了死循环，但依然会数据覆盖、丢失数据，无法保证原子性。并发替代方案：Hashtable：全局锁，效率极低，不推荐ConcurrentHashMap：分段锁（JDK1.7）/CAS+synchronized（JDK1.8），高并发首选5.HashMap和HashTable、ConcurrentHashMap区别？对比项HashMapHashTableConcurrentHashMap线程安全不安全安全（全局锁）安全（细粒度锁）效率单线程极高极低并发高效null键值允许1个null键，多个null值不允许null键值不允许null键值底层结构数组+链表+红黑树数组+链表同HashMap，加并发控制五、树形结构（二叉树、红黑树）1.普通二叉树、二叉搜索树、平衡二叉树区别？普通二叉树：每个节点最多两个子节点，无大小规则。二叉搜索树BST：左子树所有节点值<根节点，右子树所有节点值>根节点，中序遍历有序。缺点：极端情况会退化成链表。平衡二叉树AVL：在BST基础上，保证左右子树高度差不超过1，完全平衡，查询稳定，但插入删除需要频繁旋转，开销大。2.红黑树的特性？为什么HashMap用红黑树不用AVL树？红黑树五大特性：节点只有红、黑两种颜色根节点一定是黑色所有叶子节点（空节点）都是黑色红色节点的子节点一定是黑色（不能连续红）任意节点到其叶子节点的所有路径，黑色节点数量相同选择原因：AVL树高度严格平衡，查询更快，但增删需要大量旋转操作，开销极大。红黑树是弱平衡，平衡要求宽松，旋转次数少，增删效率更高。HashMap频繁增删元素，优先牺牲一点查询性能，换取更高的写入性能，所以用红黑树。3.二叉树的遍历方式？核心四种，前三种属于深度优先，层序是广度优先：前序遍历：根→左→右中序遍历：左→根→右（二叉搜索树中序遍历结果有序）后序遍历：左→右→根层序遍历：从上到下、从左到右（借助队列实现）六、堆结构1.大顶堆、小顶堆的特点？底层结构？堆是完全二叉树，基于数组实现，无额外指针开销。小顶堆：任意父节点值≤子节点值，堆顶是全局最小值。大顶堆：任意父节点值≥子节点值，堆顶是全局最大值。适用场景：TopK问题、排序、任务优先级调度。2.堆排序的时间复杂度？稳定性如何？堆排序整体时间复杂度稳定O(nlogn)，最好最坏情况一致。不稳定排序：相同数值的元素，排序后相对顺序可能改变。七、常见算法与排序面试题1.常用排序算法的时间复杂度、稳定性总结排序算法最好复杂度最坏复杂度稳定性冒泡排序O(n)O(n²)稳定选择排序O(n²)O(n²)不稳定插入排序O(n)O(n²)稳定快速排序O(nlogn)O(n²)不稳定归并排序O(nlogn)O(nlogn)稳定堆排序O(nlogn)O(nlogn)不稳定2.为什么快速排序是工程中最快的排序？1.平均时间复杂度O(nlogn)，常数开销极小，遍历、交换操作简单。2.局部性好，贴合CPU缓存，读写效率高。3.归并排序需要额外O(n)空间，堆排序常数开销大，快排原地排序、空间开销小。JavaArrays.sort()对基础类型用优化快排，对象类型用归并排序（保证稳定）。3.二分查找的前提和时间复杂度？前提：有序数组、随机访问结构，链表不能用二分查找。时间复杂度O(logn)，每次查找排除一半数据，效率极高。八、高频综合面试题1.怎么用队列实现栈？怎么用栈实现队列？栈实现队列：两个栈，一个入栈、一个出栈。出栈为空时，把入栈所有数据导入出栈，反转顺序实现先进先出。队列实现栈：两个队列，每次入队放主队列，出队时把主队列除最后一个元素外全部转移到备用队列，弹出最后一个元素，实现后进先出。2.什么是迭代器模式？ArrayList为什么会出现并发修改异常？迭代器遍历集合时，会校验集合的修改次数。ArrayList内部有modCount变量，每次增删都会自增。迭代器遍历过程中，如果发现modCount不等于预期值，直接抛出Concu