哈希表
概念
哈希表（hash table）又称字典（dictionary）、词典或散列表，哈希（hashing）又称散列或杂凑。
当我们需要存储和组织的数据项可能来自于一个相当大的空间（不妨将其数量记为 R），而在任何一个常规的时刻，我们所真正需要存储和组织的数据只是其中非常非常小的一个子集时（不妨将其数量记为 N），为了提升空间效率，就需要使用哈希表。
哈希表中的每一个单元被称为桶（bucket），其可以 直接存放 或 间接指向 一个词条（entry）。因此，哈希表又可称为桶数组（bucket array）。
定址（或哈希）是指根据词条的 key（未必可比较）直接确定哈希表入口。要实现这种定址就需要哈希函数/散列函数。
为方便讨论，我们将哈希表的长度（即容量）记为 M。
已用空间的容量与哈希表总容量之比，即 N/M，称为装填因子（load factor），通常也简记为 \(\lambda\)。
哈希冲突/散列冲突（hash collision），即存在 key1 != key2，但 hash(key1) = hash(key2)。适当的将哈希表的长度增长，可以减少冲突出现的概率。
从理论上讲，哈希可以看作是由一个大空间到小空间的映射，因此绝不可能是单射，即冲突不可避免，但是，近似的单射往往可行，因此，我们需要：
- 精心设计哈希表及哈希函数，以尽可能降低冲突的概率；
- 更需要制定可行的预案，以便在发生冲突时，能够尽快予以排解。
下面两节将分别介绍。
哈希函数
一个好的哈希函数有以下特性：
- 确定（determinism）：同一关键码总是被映射至同一地址
- 快速（efficiency）：\(expected-O(1)\)
- 满射（surjection）：尽可能充分地覆盖整个哈希空间
- 均匀（uniformity）：关键码映射到哈希表各位置的概率尽量接近，可有效避免聚集（clustering）现象。
以下是一些常用的哈希函数：
除余法
\(hash(key) = key \bmod M\)，M 为素数时，数据对哈希表的覆盖最充分，分布最均匀。
除余法的缺陷：
- 不动点：无论表长 M 取值如何，总有 hash(0) = 0
- 零阶均匀：[0, k) 的关键码，平均分配至 M 个桶；但相邻关键码的哈希地址也必相邻
MAD 法
MAD 即 multiply-add-divide（乘-加-除），取 M 为素数，\(a > 0\)，\(b > 0\)，\(a \bmod M \neq 0\)，\(hash(key) = (a \times key + b) \bmod M\)。
MAD 法可以解决上述除余法的两个缺陷：
- b 可以看作是偏移量（offset），可解决不动点问题
- a 可以看作是步长（step），可以实现一阶均匀，即邻近的关键码，哈希地址不再邻近
当然，特定场合下，未必需要高阶的均匀性。
数字分析法（selecting digits）
抽取 key 中的某几位，构成地址。
比如，取十进制表示的奇数位：\(hash(123456789) = 13579\)
此方法的缺陷在于没有被选用的那一组数位，对最终的哈希地址没有任何影响和贡献，没有足够的体现均匀性的要求。
平方取中法（mid-square）
取 \(key^2\) 的中间若干位，构成地址。
比如：
\(hash(123)=512\)，保留 \(key^2=123^2=15129\) 的中间 3 位
\(hash(1234567)=556\)，保留 \(1234567^2=1524155677489\) 的中间 3 位
平方取中法可以有效的解决上述方法的缺陷，取中间的数位可以使得构成原关键码的各数位能够对最终的哈希地址有尽可能接近的影响。
折叠法（folding）
将 key 分割成等宽的若干段，取其总和作为地址。
位异或法 XOR
将 key 分割成等宽的二进制段，经异或运算得到地址。
总之，哈希函数越是随机，越是没有规律，越好。
排解冲突
哈希表中的冲突无法避免，通过以下方法可以排解冲突：
多槽位
多槽位（multiple slots）：桶单元细分成若干槽位（slot），存放（与同一单元）冲突的词条。
只要槽位数目不多，依然可以保证 \(O(1)\) 的时间效率。
但是，需要为每个桶配备多少个槽，方能保证 \(O(1)\)？若预留过多，则空间浪费；无论预留多少，极端情况下仍有可能不够。
独立链
为了解决以上问题，可以采用独立链法。
独立链（linked-list chaining/separate chaining）：每个桶存放一个指针，冲突的词条，组织成链表。
它存在如下优点与缺点：
优点：
- 无需为每个桶预备多个槽位
- 任意多次的冲突都可解决
- 删除操作实现简单、统一
缺点：
- 指针需要额外空间
- 节点需要动态申请
- 空间未必连续分布，系统缓存几乎失效