 查找的实现与刷题路线)
tech-interview-handbook 哈希表面试备战指南从时空权衡到 O(1) 查找的实现与刷题路线【免费下载链接】tech-interview-handbookCurated coding interview preparation materials for busy software engineers项目地址: https://gitcode.com/GitHub_Trending/te/tech-interview-handbook哈希表Hash table / Hash map是 tech-interview-handbook 算法学习清单中标注为Mid优先级、但作者认为可能是算法题里最常用的数据结构的核心主题。本篇基于仓库中的 哈希表学习指南完整覆盖其定义、碰撞处理策略、各语言 API、时间复杂度并结合仓库内的面试技巧文档、学习计划与示例代码做纵深扩充——读完后你将掌握如何在面试中用哈希表做时空权衡、如何用标准库 API 落地、遇到瓶颈时如何系统性地想到哈希表优化以及一条从必修题到进阶题的完整练习路线。哈希表的核心原理哈希表通常也称 hash map是实现关联数组抽象数据类型的一种数据结构负责把 key 映射到 value。其工作方式对元素施加一个哈希函数hash function计算出一个索引即哈希码hash code该索引指向一个由**桶buckets或槽slots**组成的数组目标值就存放在其中查找lookup时对 key 做哈希得到的哈希值直接指示对应 value 的存储位置。哈希是最典型的时空权衡原文档把哈希定位为**最常见的时间—空间权衡space-time tradeoff**示例不用哈希每次判断元素是否存在都要对数组做线性搜索时间 O(n)用哈希先遍历数组一次把所有元素哈希进哈希表花费 O(n) 空间此后判断元素存在只需对元素做哈希并查表平均 O(1)。换句话说用一次预处理和额外的空间换取后续每次查询从 O(n) 到 O(1) 的质变。在面试中讨论方案时这正是应该主动说出的 tradeoff。哈希碰撞与两种解决策略不同 key 可能哈希到同一个桶即哈希冲突collision。仓库文档明确提示面试中不太会被追问冲突处理的细节但概念上应知道两大流派拉链法Separate chaining每个桶挂一条链表所有碰撞的元素都存储在该链表中开放寻址法Open addressing所有条目直接存放在桶数组本身中。插入新条目时从哈希命中的槽位开始按某种**探测序列probe sequence**逐一检查直到找到一个空槽。仓库中的实战题描述也印证了这两条路线其中一道面试题就是某 API 与 hash map 的集成其 hash map 的 buckets 由链表构成即拉链法的真实落地形态。在整体学习计划中的定位在 算法学习清单 中Hash Table 的优先级为Mid与 Recursion、Linked List、Queue、Stack、Heap、Trie、Interval 同级低于 Array、String、Sorting/Searching 等 High 优先级主题。编码学习计划 将哈希表安排在第 1 周学习预估投入3 小时。学习清单页面还给出了两条与哈希表直接相关的高价值建议数据结构的组合增强把 hash map 和双向链表doubly-linked list组合使用可以让 LRU cache 的get和put都达到 O(1)——这是哈希表组合武器的典型代表卡题时的兜底策略哈希表是算法题中出现频率最高的数据结构。卡住时最后的手段是枚举手头常见的几种数据结构逐一考虑是否适用——这个技巧对作者本人有效过。各语言的标准库实现面试中你不需要手写哈希表但必须熟悉所用语言的 API。原文档给出的实现对照表如下语言APICstd::unordered_mapJavajava.util.Map接口实际使用java.util.HashMapPythondictJavaScriptObject或Map使用时的注意点Java 中声明时多用接口类型Map、构造时用HashMap这是 Java 惯用法JavaScript 中Object的 key 会被强制转为字符串且存在原型链问题Map支持任意类型 key 且有size、迭代器等更干净的语义处理计数、集合类问题时Map通常更合适Python 的dict本身即哈希表若语言提供内置 Counter 类如 Python字符串主题 特别建议在统计字符频率时先向面试官确认能否使用以节省时间。时间复杂度速查原文档给出的复杂度表如下应作为面试前必背内容操作Big-O说明AccessN/A哈希码未知无法直接按位置访问SearchO(1)*InsertO(1)*RemoveO(1)** 这是平均情况的复杂度。原文档明确说明在面试语境下哈希表只需要考虑平均情况即可不要求推导最坏情况 O(n) 的成因。Access N/A 这一行值得强调哈希表不支持按物理下标取值只能通过 key 定位。这是它与数组在面试讨论中最本质的差别也决定了它适合按键查找/计数/去重类问题而不适合按下标访问类问题。经典面试场景哈希表如何解题仓库的多份文档给出了哈希表在不同题型中的落地方式下面按场景归纳。1. 查找互补元素Two Sum 的时空权衡编码面试作弊表 以 Two Sum 为例展示了面试中如何用两句话讲清哈希表方案的 tradeoff双层嵌套 for 循环时间 O(n²)空间 O(1)单遍遍历把值哈希进哈希表value → index对后续每个值查表看是否存在能与它加和为 target 的既有值时间与空间均为 O(n)。面试中的标准动作是把两个方案都讲出来说明各自的 time/space 复杂度讨论 tradeoff 后选定时间复杂度更低的方案。注意文中写法hash a value to its index into a hash table——存什么当 key、存什么当 value值是索引还是值本身是哈希表方案的第一个设计决策。2. 哈希 分组Group Anagrams编码面试技巧 用 Group Anagrams 演示了把大问题拆成哈希相关的子问题的思路——先哈希字符串再按哈希分组。仓库给出的骨架代码def hash(string): # TODO: 哈希字符串例如排序字符或统计字符频率作为 key def group_strings(strings_hashes): # TODO: 按哈希值分组 strings_hashes [(string, hash(string)) for string in strings] return group_strings(strings_hashes)这个先算哈希、再按哈希聚合的两段式结构是哈希表类题目的通用拆解模式也对应原文档推荐练习题中的 Group Anagrams。3. 把数组本身当作哈希表O(1) 空间技巧当面试官要求O(1) 空间时可以反过来把输入数组本身当作哈希表。数组主题 的 Index as a hash key 一节与 技巧文档 都指向同一道题 First Missing Positive若数组值域恰好是 1..NN 为数组长度可以用把对应下标的值取负来标记该数字出现过——要标记4 出现过就取负nums[4]。仓库同时给出了使用边界值得在面试前记住这属于利用原数组存储中间状态的取巧手段技巧文档明确警告这种 mutate 原数组的做法只适合面试场景实际工程中不要使用使用前要先确认值域满足索引即 key的前提值在 1..N 之间否则下标标记法不成立。4. 哈希表 双向链表LRU / LFU 类缓存哈希表在缓存类题目中承担O(1) 定位节点的角色链表承担O(1) 维护访问顺序的角色。原文档的 Sample questions 第一题——描述一个least-used cacheLFU的实现及其大 O 复杂度——正是这个组合的进阶版把最近使用换成最少使用需要额外的频次计数结构而这通常又是一层 hash map。推荐练习题中的 LRU Cache 与 All O(1) Data Structure 属于同一族。必修与推荐练习题原文档将练习划分为两级完整继承如下题目以 LeetCode 同名题为准。Essential questions学习该主题时必练Two SumRansom NoteRecommended practice questions掌握必修题后再做Group AnagramsInsert Delete GetRandom O(1)First Missing PositiveLRU CacheAll O(1) Data Structure从这份清单可以读出作者的取舍前两题建立哈希表 查找加速的基本盘进阶题则刻意覆盖了哈希表的三个变体形态——哈希表 数组双写Insert Delete GetRandom O(1)、数组伪装哈希表First Missing Positive、哈希表 链表组合LRU / All O(1) Data Structure。哈希函数的实战一面Rabin-Karp 滚动哈希哈希表的主题离不开哈希函数本身怎么写。仓库的 Rabin-Karp 滚动哈希示例 展示了一个面试中可能用到的哈希技术——滚动哈希在需要对连续子串逐一计算哈希时不必每次 O(m) 重算而是 O(1) 增量更新。核心公式def rk_hash_update(curr_hash, size, add_n, rem_n): Updates the hash by removing an integer from the left and appending a new one on the right. return (curr_hash - (rem_n * BASE ** (size - 1))) * BASE add_n其数学直觉旧哈希去掉最左字符的贡献rem_n * BASE^(size-1)整体左移一位乘 BASE再加上新右端字符add_n。仓库示例还验证了哈希的路径无关性从abc滚动到bcd与从zbc滚动到bcd两次得到相同哈希值。这一技术正是 字符串主题 中 Rabin Karp用 rolling hash 高效搜索子串 技巧的底层实现。学习资源与推荐课程原文档列出的学习资料保留原条目供延伸阅读ReadingsTaking Hash Tables Off The ShelfbasecsHashing Out Hash FunctionsbasecsVideosCore: Hash Tables——University of California San Diego 的数据结构课程CourseraA Brief Guide to Hash Tables——Samuel AlbanieUniversity of Cambridge附配套 slides仓库中所有算法主题页面共用的 推荐课程 模块还列出三门覆盖哈希表等模式化题型的付费课程AlgoMonsterGoogle 工程师出品一次付费终身有效、Design Gurus 的Grokking the Coding Interview按题型模式练习支持 Java/Python/C/JavaScript 并带分步可视化、以及 Udemy 的Master the Coding Interview: Data Structures Algorithms约 19 小时、全栈面试内容的打包课程。小结哈希表主题的面试自检清单能否一句话说清哈希表是用空间换时间的经典案例平均 O(1) 查找/插入/删除、无法按下标访问能否说出拉链法与开放寻址法两种冲突解决策略并知道面试中通常只考概念能否流畅写出所用语言的标准库哈希表 APIunordered_map/HashMap/dict/Map面对 Two Sum 类问题能否同时给出 O(n²)/O(1) 与 O(n)/O(n) 两个方案并讨论 tradeoff遇到查找瓶颈时能否把换哈希表作为第一个尝试的优化手段能否区分需要 O(1) 空间时用数组当哈希表First Missing Positive需要 O(1) 定位 顺序维护时用哈希表 链表LRU/LFU以上六点覆盖了原文档的全部知识点并对应 算法学习清单、学习计划 与 编码面试技巧 中与哈希表相关的所有交叉引用可作为该主题 3 小时学习投入的验收标准。【免费下载链接】tech-interview-handbookCurated coding interview preparation materials for busy software engineers项目地址: https://gitcode.com/GitHub_Trending/te/tech-interview-handbook创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 tech-interview-handbook 哈希表面试备战指南：从时空权衡到 O(1) 查找的实现与刷题路线
tech-interview-handbook 哈希表面试备战指南从时空权衡到 O(1) 查找的实现与刷题路线【免费下载链接】tech-interview-handbookCurated coding interview preparation materials for busy software engineers项目地址: https://gitcode.com/GitHub_Trending/te/tech-interview-handbook哈希表Hash table / Hash map是 tech-interview-handbook 算法学习清单中标注为Mid优先级、但作者认为可能是算法题里最常用的数据结构的核心主题。本篇基于仓库中的 哈希表学习指南完整覆盖其定义、碰撞处理策略、各语言 API、时间复杂度并结合仓库内的面试技巧文档、学习计划与示例代码做纵深扩充——读完后你将掌握如何在面试中用哈希表做时空权衡、如何用标准库 API 落地、遇到瓶颈时如何系统性地想到哈希表优化以及一条从必修题到进阶题的完整练习路线。哈希表的核心原理哈希表通常也称 hash map是实现关联数组抽象数据类型的一种数据结构负责把 key 映射到 value。其工作方式对元素施加一个哈希函数hash function计算出一个索引即哈希码hash code该索引指向一个由**桶buckets或槽slots**组成的数组目标值就存放在其中查找lookup时对 key 做哈希得到的哈希值直接指示对应 value 的存储位置。哈希是最典型的时空权衡原文档把哈希定位为**最常见的时间—空间权衡space-time tradeoff**示例不用哈希每次判断元素是否存在都要对数组做线性搜索时间 O(n)用哈希先遍历数组一次把所有元素哈希进哈希表花费 O(n) 空间此后判断元素存在只需对元素做哈希并查表平均 O(1)。换句话说用一次预处理和额外的空间换取后续每次查询从 O(n) 到 O(1) 的质变。在面试中讨论方案时这正是应该主动说出的 tradeoff。哈希碰撞与两种解决策略不同 key 可能哈希到同一个桶即哈希冲突collision。仓库文档明确提示面试中不太会被追问冲突处理的细节但概念上应知道两大流派拉链法Separate chaining每个桶挂一条链表所有碰撞的元素都存储在该链表中开放寻址法Open addressing所有条目直接存放在桶数组本身中。插入新条目时从哈希命中的槽位开始按某种**探测序列probe sequence**逐一检查直到找到一个空槽。仓库中的实战题描述也印证了这两条路线其中一道面试题就是某 API 与 hash map 的集成其 hash map 的 buckets 由链表构成即拉链法的真实落地形态。在整体学习计划中的定位在 算法学习清单 中Hash Table 的优先级为Mid与 Recursion、Linked List、Queue、Stack、Heap、Trie、Interval 同级低于 Array、String、Sorting/Searching 等 High 优先级主题。编码学习计划 将哈希表安排在第 1 周学习预估投入3 小时。学习清单页面还给出了两条与哈希表直接相关的高价值建议数据结构的组合增强把 hash map 和双向链表doubly-linked list组合使用可以让 LRU cache 的get和put都达到 O(1)——这是哈希表组合武器的典型代表卡题时的兜底策略哈希表是算法题中出现频率最高的数据结构。卡住时最后的手段是枚举手头常见的几种数据结构逐一考虑是否适用——这个技巧对作者本人有效过。各语言的标准库实现面试中你不需要手写哈希表但必须熟悉所用语言的 API。原文档给出的实现对照表如下语言APICstd::unordered_mapJavajava.util.Map接口实际使用java.util.HashMapPythondictJavaScriptObject或Map使用时的注意点Java 中声明时多用接口类型Map、构造时用HashMap这是 Java 惯用法JavaScript 中Object的 key 会被强制转为字符串且存在原型链问题Map支持任意类型 key 且有size、迭代器等更干净的语义处理计数、集合类问题时Map通常更合适Python 的dict本身即哈希表若语言提供内置 Counter 类如 Python字符串主题 特别建议在统计字符频率时先向面试官确认能否使用以节省时间。时间复杂度速查原文档给出的复杂度表如下应作为面试前必背内容操作Big-O说明AccessN/A哈希码未知无法直接按位置访问SearchO(1)*InsertO(1)*RemoveO(1)** 这是平均情况的复杂度。原文档明确说明在面试语境下哈希表只需要考虑平均情况即可不要求推导最坏情况 O(n) 的成因。Access N/A 这一行值得强调哈希表不支持按物理下标取值只能通过 key 定位。这是它与数组在面试讨论中最本质的差别也决定了它适合按键查找/计数/去重类问题而不适合按下标访问类问题。经典面试场景哈希表如何解题仓库的多份文档给出了哈希表在不同题型中的落地方式下面按场景归纳。1. 查找互补元素Two Sum 的时空权衡编码面试作弊表 以 Two Sum 为例展示了面试中如何用两句话讲清哈希表方案的 tradeoff双层嵌套 for 循环时间 O(n²)空间 O(1)单遍遍历把值哈希进哈希表value → index对后续每个值查表看是否存在能与它加和为 target 的既有值时间与空间均为 O(n)。面试中的标准动作是把两个方案都讲出来说明各自的 time/space 复杂度讨论 tradeoff 后选定时间复杂度更低的方案。注意文中写法hash a value to its index into a hash table——存什么当 key、存什么当 value值是索引还是值本身是哈希表方案的第一个设计决策。2. 哈希 分组Group Anagrams编码面试技巧 用 Group Anagrams 演示了把大问题拆成哈希相关的子问题的思路——先哈希字符串再按哈希分组。仓库给出的骨架代码def hash(string): # TODO: 哈希字符串例如排序字符或统计字符频率作为 key def group_strings(strings_hashes): # TODO: 按哈希值分组 strings_hashes [(string, hash(string)) for string in strings] return group_strings(strings_hashes)这个先算哈希、再按哈希聚合的两段式结构是哈希表类题目的通用拆解模式也对应原文档推荐练习题中的 Group Anagrams。3. 把数组本身当作哈希表O(1) 空间技巧当面试官要求O(1) 空间时可以反过来把输入数组本身当作哈希表。数组主题 的 Index as a hash key 一节与 技巧文档 都指向同一道题 First Missing Positive若数组值域恰好是 1..NN 为数组长度可以用把对应下标的值取负来标记该数字出现过——要标记4 出现过就取负nums[4]。仓库同时给出了使用边界值得在面试前记住这属于利用原数组存储中间状态的取巧手段技巧文档明确警告这种 mutate 原数组的做法只适合面试场景实际工程中不要使用使用前要先确认值域满足索引即 key的前提值在 1..N 之间否则下标标记法不成立。4. 哈希表 双向链表LRU / LFU 类缓存哈希表在缓存类题目中承担O(1) 定位节点的角色链表承担O(1) 维护访问顺序的角色。原文档的 Sample questions 第一题——描述一个least-used cacheLFU的实现及其大 O 复杂度——正是这个组合的进阶版把最近使用换成最少使用需要额外的频次计数结构而这通常又是一层 hash map。推荐练习题中的 LRU Cache 与 All O(1) Data Structure 属于同一族。必修与推荐练习题原文档将练习划分为两级完整继承如下题目以 LeetCode 同名题为准。Essential questions学习该主题时必练Two SumRansom NoteRecommended practice questions掌握必修题后再做Group AnagramsInsert Delete GetRandom O(1)First Missing PositiveLRU CacheAll O(1) Data Structure从这份清单可以读出作者的取舍前两题建立哈希表 查找加速的基本盘进阶题则刻意覆盖了哈希表的三个变体形态——哈希表 数组双写Insert Delete GetRandom O(1)、数组伪装哈希表First Missing Positive、哈希表 链表组合LRU / All O(1) Data Structure。哈希函数的实战一面Rabin-Karp 滚动哈希哈希表的主题离不开哈希函数本身怎么写。仓库的 Rabin-Karp 滚动哈希示例 展示了一个面试中可能用到的哈希技术——滚动哈希在需要对连续子串逐一计算哈希时不必每次 O(m) 重算而是 O(1) 增量更新。核心公式def rk_hash_update(curr_hash, size, add_n, rem_n): Updates the hash by removing an integer from the left and appending a new one on the right. return (curr_hash - (rem_n * BASE ** (size - 1))) * BASE add_n其数学直觉旧哈希去掉最左字符的贡献rem_n * BASE^(size-1)整体左移一位乘 BASE再加上新右端字符add_n。仓库示例还验证了哈希的路径无关性从abc滚动到bcd与从zbc滚动到bcd两次得到相同哈希值。这一技术正是 字符串主题 中 Rabin Karp用 rolling hash 高效搜索子串 技巧的底层实现。学习资源与推荐课程原文档列出的学习资料保留原条目供延伸阅读ReadingsTaking Hash Tables Off The ShelfbasecsHashing Out Hash FunctionsbasecsVideosCore: Hash Tables——University of California San Diego 的数据结构课程CourseraA Brief Guide to Hash Tables——Samuel AlbanieUniversity of Cambridge附配套 slides仓库中所有算法主题页面共用的 推荐课程 模块还列出三门覆盖哈希表等模式化题型的付费课程AlgoMonsterGoogle 工程师出品一次付费终身有效、Design Gurus 的Grokking the Coding Interview按题型模式练习支持 Java/Python/C/JavaScript 并带分步可视化、以及 Udemy 的Master the Coding Interview: Data Structures Algorithms约 19 小时、全栈面试内容的打包课程。小结哈希表主题的面试自检清单能否一句话说清哈希表是用空间换时间的经典案例平均 O(1) 查找/插入/删除、无法按下标访问能否说出拉链法与开放寻址法两种冲突解决策略并知道面试中通常只考概念能否流畅写出所用语言的标准库哈希表 APIunordered_map/HashMap/dict/Map面对 Two Sum 类问题能否同时给出 O(n²)/O(1) 与 O(n)/O(n) 两个方案并讨论 tradeoff遇到查找瓶颈时能否把换哈希表作为第一个尝试的优化手段能否区分需要 O(1) 空间时用数组当哈希表First Missing Positive需要 O(1) 定位 顺序维护时用哈希表 链表LRU/LFU以上六点覆盖了原文档的全部知识点并对应 算法学习清单、学习计划 与 编码面试技巧 中与哈希表相关的所有交叉引用可作为该主题 3 小时学习投入的验收标准。【免费下载链接】tech-interview-handbookCurated coding interview preparation materials for busy software engineers项目地址: https://gitcode.com/GitHub_Trending/te/tech-interview-handbook创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考