数据结构高频题

数据结构面试一般问两层：一是常见容器的底层实现与复杂度，二是选型依据。背完复杂度表后一定要能说出"什么场景选什么"。

Q1: 数组和链表的区别？各自适用场景？ 「🟢 校招/初级」

考察点：最基础的存储结构认知。

参考答案：

维度	数组	链表
内存	连续分配，缓存友好	节点分散，靠指针串联
随机访问	O(1)	O(n)
头部/中间插入删除	O(n)（需搬移）	O(1)（已知节点时）
空间	需预分配，可能浪费	按需分配，但有指针开销

• 选型：读多写少、按下标访问选数组；频繁在头尾增删选链表（或双端队列）。

追问延伸：

• 为什么数组"缓存友好"？（CPU 缓存行的空间局部性）
• Java ArrayList 和 LinkedList 的实际性能差异为什么和理论不一致？

Q2: 栈和队列的区别？有哪些实际应用？ 「🟢 校招/初级」

考察点：线性结构的语义差异及应用意识。

参考答案：

• 栈：后进先出（LIFO）。应用：函数调用栈、括号匹配、表达式求值、浏览器后退、撤销操作。
• 队列：先进先出（FIFO）。应用：任务调度、消息队列、BFS、缓冲区。
• 常见变体：双端队列（Deque）、优先队列（堆实现）、循环队列（避免假溢出）。

追问延伸：

• 用两个栈怎么实现队列？
• 循环队列怎么判断满和空？

Q3: HashMap 的底层实现原理？ 「🟡 中级」

考察点：最高频数据结构题，能决定面试走向。

参考答案（以 Java 8 为例）：

• 结构：数组 + 链表 + 红黑树。hash(key) & (n-1) 定位桶，冲突用拉链法。
• 链表长度超过 8 且数组长度 ≥ 64 时转红黑树（O(n)→O(log n)），长度低于 6 退化回链表。
• 负载因子 0.75，扩容为 2 倍；容量保持 2 的幂是为了让取模变成位运算。
• Java 8 头插法改尾插法，解决了多线程扩容时的死循环问题，但 HashMap 本身仍非线程安全。

追问延伸：

• 为什么容量必须是 2 的幂？
• 为什么不用红黑树而用链表做第一层？（空间与常数开销）
• 线程安全场景选 ConcurrentHashMap 还是 Collections.synchronizedMap？

Q4: 说一下堆的实现和应用 「🟡 中级」

考察点：优先队列的理解。

参考答案：

• 堆是完全二叉树，用数组存储；父节点 i 的左右孩子在 2i+1、2i+2。
• 大顶堆/小顶堆：插入时上浮（sift up），删除堆顶时下沉（sift down），都是 O(log n)；建堆 O(n)。
• 应用：优先队列、TopK 问题（维护大小为 K 的小顶堆）、堆排序、定时器调度（时间轮之外的简单实现）。

追问延伸：

• 从 10 亿个数里找最大的 100 个，怎么做？
• 为什么建堆是 O(n) 而不是 O(n log n)？

Q5: 跳表是什么？为什么 Redis 用跳表不用红黑树？ 「🟡 中级」

考察点：对工程选型（而非纯理论）的理解。

参考答案：

• 跳表在有序链表上建立多层索引，每层以约 1/2 概率晋升，查找/插入/删除平均 O(log n)。
• Redis ZSet 选跳表的原因：实现简单；范围查询（ZRANGE）天然友好；通过调整晋升概率可灵活平衡内存和速度；并发友好（局部修改）。
• 红黑树实现复杂、范围查询需要中序遍历、旋转涉及多个节点，不利于并发修改。

追问延伸：

• 跳表的空间复杂度是多少？
• LevelDB/RocksDB 的 memtable 也用了跳表，为什么？

Q6: 布隆过滤器了解吗？ 「🟡 中级」

考察点：解决缓存穿透等实际问题的数据结构储备。

参考答案：

• 用 m 位比特数组 + k 个哈希函数判断元素"可能存在"：写入时把 k 个位置置 1，查询时任一位置为 0 则一定不存在。
• 特点：有假阳性（说"存在"可能不存在），无假阴性；不支持删除（计数布隆过滤器可以）。
• 应用：缓存穿透防护、爬虫 URL 去重、垃圾邮件过滤、HBase 加速读。

追问延伸：

• 误判率和哪些参数相关？怎么估算？
• 缓存穿透还有什么解法？（空值缓存、互斥锁，见 Redis 篇）