notes/18_hashtable/readme.md
散列表是数组的一种扩展，利用数组下标的随机访问特性。
本质：利用散列函数将关键字映射到数组下标，而后利用数组随机访问时间复杂度为 $\Theta(1)$ 的特性快速访问。
hash(key)key1 == key2，那么 hash(key1) == hash(key2)key1 != key2，那么 hash(key1) != hash(key2)第 3 个要求，实际上不可能对任意的 key1 和 key2 都成立。因为通常散列函数的输出范围有限而输入范围无限。
key1 != key2 但 hash(key1) == hash(key2)散列冲突会导致不同键值映射到散列表的同一个位置。为此，我们需要解决散列冲突带来的问题。
如果遇到冲突，那就继续寻找下一个空闲的槽位。
插入时，如果遇到冲突，那就依次往下寻找下一个空闲的槽位。（橙色表示已被占用的槽位，黄色表示空闲槽位）
查找时，如果目标槽位上不是目标数据，则依次往下寻找；直至遇见目标数据或空槽位。
删除时，标记为 deleted，而不是直接删除。
插入时，如果遇到冲突，那就往后寻找下一个空闲的槽位，其步长为 $1^2$, $2^2$, $3^2$, $\ldots$。
查找时，如果目标槽位上不是目标数据，则依次往下寻找，其步长为 $1^2$, $2^2$, $3^2$, $\ldots$；直至遇见目标数据或空槽位。
删除时，标记为 deleted，而不是直接删除。
$\text{load factor} = \frac{size()}{capacity()}$
所有散列值相同的 key 以链表的形式存储在同一个槽位中。
插入时，不论是否有冲突，直接插入目标位置的链表。
查找时，遍历目标位置的链表来查询。
删除时，遍历目标位置的链表来删除。