02.2.2 字符串与哈希表
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.2 数组、字符串与哈希
这个知识域解决什么问题
本知识域覆盖两类高频对象:哈希表的内部机制与设计题,以及字符串的变换、匹配与回文。主线为:哈希表如何平均 O(1) 工作与冲突退化 → 字符串基础变换 → KMP/RK 匹配与回文结构 → 去重、布隆过滤器与 Top-K 堆。
知识地图
哈希表设计与冲突处理(1)
→ 字符串基础与子串变换(2)
→ 字符串匹配 KMP/RK 与回文(3)
→ 去重、布隆过滤器与 Top-K 堆(4)
子主题
| 编号 | 子主题 | 核心内容 | 题数 |
|---|---|---|---|
| 02.2.2.1 | 哈希表设计与冲突处理 | 哈希函数、链地址/开放寻址、HashMap 结构与树化、负载因子、扩容 rehash、设计哈希集/映射、最坏复杂度与选型 | 20 |
| 02.2.2.2 | 字符串基础与子串变换 | 不可变性、编码、反转、压缩、异位词分组、大数加减乘、Z 字形、单词翻转、子串与子序列区别 | 20 |
| 02.2.2.3 | 字符串匹配 KMP/RK 与回文 | 朴素匹配、前缀函数与 next、KMP 流程与复杂度、滚动哈希、中心扩展、回文计数与区间 DP 概念 | 20 |
| 02.2.2.4 | 去重、布隆过滤器与 Top-K 堆 | 哈希去重、交集、布隆过滤器原理/误判/删除/参数、Top-K 堆、快速选择、桶排序与选型 | 20 |
合计 80 题。 每题按「一句话结论 → 概念解释 → 原理流程 → 代码/图示 → 常见误区 → 追问(带答案)」组织;哈希与概率结构标注平均/最坏口径。
学习路径
先 1 理解哈希表内部机制与冲突处理,再 2 掌握字符串基础变换与编码边界,3 学会 KMP/RK 匹配与回文判断,最后 4 处理去重、近似存在性与 Top-K 选优。
自检
- [ ] 能说清链地址法与开放寻址法的区别及退化表现
- [ ] 能手写哈希集合/映射的桶结构与增删查
- [ ] 能写出前缀函数并讲清 KMP 主串不回退的原因
- [ ] 能用中心扩展求最长回文与回文计数
- [ ] 能解释布隆过滤器的假阳性、不可删除与参数估算
- [ ] 能用小顶堆求最大 K 个并报出复杂度
- [ ] 能区分子串与子序列、存在性与计数查重