Algorithms study cheatsheets
Coding interview 的 Hash table cheatsheet
Hash table 学习指南，包含练习题、技巧、时间复杂度与推荐资源
Introduction
Hash table（也叫 hash map）是一种实现 associative array 的数据结构，用来把 key 映射到 value。Hash table 会对 key 做 hash，得到一个 index（hash code），用于定位 bucket/slot，从而找到对应 value。查找时对 key 做 hash，就能直接定位到存储位置。
Hashing 是经典的 space-time tradeoff。与每次 O(n) 线性查找相比，我们可以先遍历一次，把元素哈希进 hash table。之后查找元素是否存在，只需 hash 一下并查表，平均 O(1)。
Hash 冲突时有多种处理方式。面试一般不会考太细：
- Separate chaining - 每个 bucket 里用 linked list 存储冲突项
- Open addressing - 所有 entry 都放在 bucket array 内，通过 probing 找空位
Learning resources
- Readings
- Taking Hash Tables Off The Shelf, basecs
- Hashing Out Hash Functions, basecs
- Videos
- Core: Hash Tables, University of California San Diego
- A Brief Guide to Hash Tables (slides), Samuel Albanie, University of Cambridge
Implementations
| Language | API |
|---|---|
| C++ | std::unordered_map |
| Java | java.util.Map. Use java.util.HashMap |
| Python | dict |
| JavaScript | Object or Map |
Time complexity
| Operation | Big-O | Note |
|---|---|---|
| Access | N/A | 无法直接 access，因为 hash code 不可预测 |
| Search | O(1)* | |
| Insert | O(1)* | |
| Remove | O(1)* |
* 这里是平均情况，面试里通常只关心 hash table 的平均复杂度。
Sample questions
- 描述一个 least-used cache 的实现，以及其 big-O
- 关于 API 集成 hash map，bucket 由 linked list 组成的问题
Essential questions
该 topic 必练题。
Recommended practice questions
在掌握基础后推荐练习。
- Group Anagrams
- Insert Delete GetRandom O(1)
- First Missing Positive
- LRU Cache
- All O one Data Structure