Coding interview 的 Hash table cheatsheet

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 冲突时有多种处理方式。面试一般不会考太细：