散列
联合数组：下标不是数字，不一定能比较大小
Map/Dictionary：关键码禁止/允许相等
词条只需有判等功能。
两个 key 通过 hashing 映射到散列表中的 rank。
冲突 & 完美
当数据集大小固定且已知时，可以设计完美散列。
但一般情况下，可能出现冲突，两个 key 被映射到同一个 rank。
散列函数
- 确定：同一 key 总是被映射到同一 rank
- 快速：期望
- 满射：尽可能充分利用散列表
- 均匀：key 被映射到各个 rank 的概率基本相同
除余法
对于理想随机序列，表长是否为素数无关紧要。
Kolmogorov 复杂度：生成一个序列的算法最短可以用多少行代码实现。
实际应用中，数据并非随机，例如，可能具有周期性。此时，将散列表长取作素数，可将聚集的概率降为最低。
缺陷：
- 不动点：无论 取值如何，总有
- 相关性：相邻关键码的散列地址必然相邻
- 解决？
- MAD 法：取随机数 ，
其他
- 抽取其中若干位
- 平方取中
- 折叠法：切割成等宽的若干段取总和
- 位异或：切割成等宽的若干段作异或
- 随机
伪随机数
MAD 法
HashCode
String to Integer，一般采用多项式法
排解冲突
开放散列
- 多槽位：将桶的单元细分为多个槽位，可以保持 效率
- 难以预测细分程度，若过细，会导致空间浪费，若过粗，可能仍然冲突
- 独立链：每个桶拥有一个链表
- 任意多次冲突均可解决
- 节点的动态分配和回收耗时
- 空间不连续分布，缓存很难生效
封闭散列
插入
遇到冲突，沿试探链逐个试探，直到找到空桶。
线性试探：
数据局部性极好，缓存作用可以发挥到极致。
查找
沿试探链逐个试探，直到找到目标或遇到空桶。
删除
不能直接清空桶，否则会导致多条试探链断裂。
Lazy Removal： 用位图标记删除，再清空桶。 对于被标记删除的位，
- 查找时视作不匹配的空桶
- 插入时视作可插入的空桶
插入
找到第一个空桶或者含 LazyRemove 标记的桶插入，若装填因子大于阈值，则 Rehash
Rehash
将新的 M 设为大于 4*N 的第一个素数（而不是 2*M），极端情况下可能缩容
平方试探
试探链从连续试探改为按平方数试探，步长为 1, 3, 5, 7, ...
Cache 利用率有所下降，但可以接受
- 若表长为合数，可能出现可使用的桶数小于 ，此时，若这些桶均非空，则会死循环
- 若表长为素数，必然恰有 个可用桶，且由试探链的前 项取遍
Proof
若 ，第 和 项冲突，则 但 ，不可能整除
如何利用另一半表？
可以利用双向平方试探：交替地向两侧进行平方试探，若能保证两个子试探链相互独立，则可以利用上所有桶。
但是两个子试探链不一定彼此独立： 由 Two Square Theorem，
Link to originalTheorem
素数 不能表示为一对整数的平方和当且仅当
- 若表长取作 类素数，必然不能表示为两对整数的平方和，而两个子试探链不独立的充要条件是表长能被分解为两个平方数之和（正向和反向的试探链在某处交汇），因此两个子试探链相互独立
- 若表长取作 类素数，则两个子试探链不相互独立
桶排序
用开放散列的独立链实现，可以实现稳定性
MaxGap
给定 n 个点，得到 n-1 个区间，求最大间隔。
- 找到全局最小和最大点
- 将总区间均分为 n-1 段
- 将各点归入各桶，各桶只需记录最小和最大点
- 最大间隔必然大于均值，只会出现在两桶之间，遍历各桶，求出相邻非空桶的距离，最大值即为最大间隔 时间复杂度为 对称的 MinGap 问题不能线性完成
基数排序
若关键码有多个域 ，需要依次按照 排序 自 到 依次进行一次桶排序 正确性源于稳定性
整数排序
限制： 个整数，整数范围为 ， 为常数 将所有整数转换为 位的 进制形式（每个数需常数时间，共 时间），使用基数排序，可以在 时间内完成排序。
计数排序
- 分桶，统计各桶内元素的数量
- 自前向后遍历各桶，得到各桶的秩的区间
- 自后向前扫描每个元素，对应桶的计数减一即为它的秩
- 时间复杂度为 ，空间复杂度为 （不能就地完成）