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

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

一概述

HashMap 原理（Java 举例）
ArrayList 与 LinkedList 区别
HashSet 原理
栈和队列原理
ConcurrentHashMap 原理（高并发场景）
TreeMap / TreeSet 原理
PriorityQueue（最小堆 / 最大堆）

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

2.1 HashMap 原理（Java 举例）

1、面试高频！问得最多的是：
-底层数据结构？
-如何解决哈希冲突？
-为什么负载因子是 0.75？
-JDK1.7 和 1.8 有什么不同？

2、简要回答：
-HashMap 底层由数组 + 链表 / 红黑树组成。
-当插入key时，先用hashCode()计算哈希值，再通过 (n - 1) & hash 定位数组下标。
-如果发生哈希冲突（多个 key 落在同一个 index），
JDK1.7用链表解决冲突，JDK1.8当链表长度超过8且数组长度超过 64 时转为红黑树以提高查找性能。

-默认初始容量是 16，负载因子是 0.75，平衡了空间和扩容频率。
-扩容会复制原数组中的元素到新的两倍大小的数组中，再重新计算 hash 分配位置。

2.2 ArrayList 与 LinkedList 区别

对比点	ArrayList	LinkedList
底层结构	动态数组	双向链表
随机访问	快（O(1)）	慢（O(n)）
插入/删除	中间插入慢	任意位置快（已知指针）
内存占用	少	多（每个节点有两个指针）
应用场景	频繁访问	频繁插入/删除

2.3 HashSet 原理

1
2
3

-HashSet 实际上是基于 HashMap 实现的。
-每个加入的元素会作为 HashMap 的 key，而 value 是一个固定的 dummy 值。
-所以 HashSet 也依赖于 hashCode() 和 equals()。

2.4 栈和队列原理

1
2

-栈（Stack）：后进先出（LIFO），常见题：有效括号、最小栈、逆波兰表达式
-队列（Queue）：先进先出（FIFO），常见题：滑动窗口最大值、最近请求次数

2.5 ConcurrentHashMap 原理（高并发场景）

1
2
3

-JDK1.7 使用 分段锁 Segment[] + HashEntry[]
-JDK1.8 使用 CAS + synchronized + 链表/红黑树 + 数组
-支持高并发读写，避免整个 Map 加锁

2.6 TreeMap / TreeSet 原理

1 2	-基于红黑树实现，自动排序（按 key 或 comparator） -插入、删除、查找时间复杂度为 O(log n)

2.7 PriorityQueue（最小堆 / 最大堆）

1 2	-Java 中的 PriorityQueue 是最小堆结构，每次出队都是最小值 -常用于实现 Top K 问题、小根堆排序

0%