数据结构与算法之——常见面试题及解答2

发表于 2025-06-26 分类于面试相关，数据结构与算法阅读时长 ≈ 1 分钟

一概述

为什么 HashMap 线程不安全？如何解决？
ConcurrentHashMap 具体实现（JDK1.8）
LRU 缓存原理（必问经典设计题）
HashMap 的扩容机制？
二叉树遍历方式（递归 + 非递归）
红黑树 vs AVL树？
数组与链表的区别？
Java 的 Stack 和 Deque 区别？

二面试题解答(仅供参考)

2.1 为什么 HashMap 线程不安全？如何解决？

1、问题背景：
HashMap 在多线程下可能出现：
-死循环（JDK1.7 resize 过程中链表形成环）
-数据覆盖、丢失（多个线程 put 到同一个桶位）

2、解决方式：
-使用 ConcurrentHashMap（推荐）
-或使用 Collections.synchronizedMap(new HashMap<>())（效率低）

2.2 ConcurrentHashMap 具体实现（JDK1.8）

1、简要原理：
-使用 CAS + synchronized 代替分段锁
-数组 + 链表 / 红黑树 的结构
-支持高并发读写操作，读无锁，写只锁当前桶位
-resize 时使用 线程协作机制（transfer）

2、常问点：
-为什么不直接用 HashTable？（全表锁性能差）
-为什么要红黑树？（链表太长时查找慢，O(n) → O(log n)）

2.3 LRU 缓存原理（必问经典设计题）

面试官：请你实现一个 O(1) 时间复杂度的 LRU 缓存？

1、答案结构：
-使用 HashMap + 双向链表
-HashMap 用于快速访问节点
-双向链表维护访问顺序（最近使用的放头部）

2、操作：
-get(key)：找到后提到头部
-put(key, value)：已存在更新并提到头部，不存在时新增到头部，满了则删除尾部节点

2.4 HashMap 的扩容机制？

1、触发时机： 
size >= capacity * loadFactor，即超过 75% 时

2、过程简述：
-扩容为原来 2 倍大小
-重新计算哈希位置
-迁移链表/树节点，注意再哈希后元素不一定在原位置

注意： 扩容是非常耗性能的操作，尽量设置合适初始容量

2.5 二叉树遍历方式（递归 + 非递归）

遍历	顺序	用途
前序遍历	根→左→右	构建树
中序遍历	左→根→右	排序输出（BST）
后序遍历	左→右→根	删除节点、释放内存
层序遍历	一层一层（BFS）	最短路径等题目

2.6 红黑树 vs AVL树？

特性	红黑树	AVL 树
平衡性	相对平衡	严格平衡
插入/删除复杂度	O(log n)，少量旋转	O(log n)，旋转次数多
使用场景	Java TreeMap / TreeSet	数据库索引（读多写少）

2.7 数组与链表的区别？

特性	数组	链表
内存连续性	是	否
插入/删除	慢（O(n)）	快（O(1)）
查找	快（O(1)）	慢（O(n)）
随机访问	支持	不支持
应用场景	顺序读写	频繁增删元素

2.8 Java 的 Stack 和 Deque 区别？

1 2	-Stack 是同步的，底层是 Vector，已不推荐使用 -推荐使用 Deque 实现栈：ArrayDeque 更快、更灵活

0%