Hash：将一个值映射成另一个的值，建立数据元素的存放位置与关键字 (key-indexed) 之间的关系
直接寻址表
Direct Addressing Table
使用关键字作为索引，将值 存储在相应的位置 (slot) 上，即
当关键字的全域 比较小时，它是一种简单有效的技术。
如果 很大，则在存储大小为 的一张表 不太实际
每一个操作都只需
哈希函数
除留余数法
The division method
将数据值 除以某一个常数 后，取余数来当索引（哈希值），从而实现将 映射到 个槽中的某一个上，即哈希函数为：
- 即为哈希表的最终长度、
应避免选择 的某些值。
- 例如， 为 2 的幂（即 ），通常使用位运算而不是除法来计算哈希值 的结果
此时 的二进制表示只有最高位是 1，其余位都是 0（），对 取模时，相当于只有 的最高位与 的最高位相乘，而其余所有位都被忽略。即一些键值的哈希值会被聚集在少数的桶中，导致哈希表的空间利用率降低。
- 一个不太接近 2 的整数幂的素数，常常是 的一个较好的选择。
乘法
The multiplication method
第一步， 用关键字 乘上常数，并提取 的小数部分（ ）。
第二步， 用 乘以这个值，再向下取整。
即哈希函数为：
全域散列法
Universal hashing
通过在一组可能的哈希函数中随机选择一个函数，从而使得对于任意给定的输入键值，哈希函数生成冲突的概率尽可能地小。
例：
- 其中 a 和 b 是随机选择的整数，p 是一个足够大的质数，k 是输入的键值，m 是桶的数量。
a 和 b 都是随机的，那么反推的时候，要怎么还原原先的输入键值？
🤖：如果使用随机的 a 和 b 进行哈希，那么反推输入键值是非常困难的，因为这是一个单向函数，即从输入得到哈希值容易，但从哈希值得到输入很难。
这也是哈希函数的一个重要特性，因为它可以提供一定的安全性保障，比如密码学中常用的哈希函数就要求满足这个特性，从而保护用户密码不被泄露。
在一些应用场景中，我们需要支持反向查找，即给定哈希值 h，找到对应的键值 k。这时可以使用加盐哈希技术，在哈希表中保存键值和对应的哈希值以及盐值 s，从而在查找时将哈希值和盐值作为输入，反推出对应的键值。但需要注意的是，为了保护哈希表的安全性，盐值 s 需要保密，不应该公开。
哈希冲突解决
两个关键字可能映射到同一个槽中，则产生冲突 (collision)。
链接法
Chaining：将所有哈希地址相同的记录都链接在同一链表中
- 给定一个能存放 个元素的、具有 个槽位的散列表 ，定义 的装载因子(load factor) ，即一个链的平均存储元素数。
- 对于用链接法解决冲突的散列表，一次（不）成功查找的平均时间为
- 散列方法的平均性能依赖于所选取的散列函数 ，将所有的关键字集合分布在 个槽位上的均匀程度。
- 用链接法散列的最坏情况性能很差：所有的 个关键字都散列到同一个槽中，这时， 最坏情况下查找的时间为 ， 再加上计算散列函数的时间，就和用一个链表来链接所有的元素差不多了。
元素的查找
- 查找操作的最坏情况
- 如果散列表中槽数与表中的元素数成正比，则有 ， 从而
元素的增删
最坏情况均仍为
开放寻址法
Open Addressing
线性探查
Linear Probing
其中 为辅助哈希函数 (Auxiliary hash function)
例 1
假如 为余数法，它的 和 使用的 相同，遇到冲突时相当于直接不断加 1 寻找下一个合适的位置。
现在表是空的，按顺序将下列关键字 27, 18, 17 插入
产生冲突，
例 2
1->2, 2->4, 3->1, 7->5, 8->3, 9->6
线性探查存在一次群集 (Primary clustering) 问题，即随着连续被占用的槽不断增加，平均查找时间也随之不断增加。
- 一个空槽前有 个满的槽时，该空槽为下一个将被占用的概率是 ，连续被占用的槽就会变得越来越长，平均查找时间也会越来越大。
二次探查
Quadratic probing
双重散列
Double hashing
用于开放寻址法的最好方法之一，它产生的排列具有随机选择排列的许多特性
- 为了能查找整个散列表，值 必须要与表的大小 互素
- 当 为素数 或者 2 的幂时，双重散列法中用到了 种探查序列， 而线性探查或二次探查中用了 种，故前者是后两种方法的一种改进。
算法应用
赎金信
输入两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。magazine 中的每个字符只能在 ransomNote 中使用一次。如果可以，返回 true ；否则返回 false 。