罗罗编程学习记录
本页内容 展开查看

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 个并报出复杂度
  • [ ] 能区分子串与子序列、存在性与计数查重