ch10 词典¶
1. 散列¶
【桶】直接存放或间接指向一个词条。根据词条 \(key\)（未必可比较）直接确定散列表入口。
【装填因子】空间利用率 \(\lambda = N / M\)。\(\lambda\) 越大，空间利用率越高，冲突的情况越严重。通过降低 \(\lambda\)，冲突程度将会有所改善，但只要数据集在动态变化，就无法彻底杜绝。
【完美散列】在某些条件下，的确可以实现单射式散列，比如数据集已知且固定。
- 精心设计散列表及散列函数，尽可能降低冲突的概率。
- 制定可行的预案，以便在发生冲突时，能够尽快予以排解。
【散列函数评价标准 / 设计原则】
- 确定：同一关键码总是被映射至同一地址。
- 快速：期望时间复杂度 \(\cal{O}(1)\)。
- 满射：尽可能充分地利用整个散列空间。
- 均匀：关键码映射到散列表各位置的概率尽量接近，有效避免聚集现象。
【常用散列函数】越是随机，越是没有规律，越好。
- 除余法：\(hash(key) = (a\times key + b) \% M\)
- 数字分析：抽取 \(key\) 中的某几位，构成地址，比如，取十进制表示的奇数位
- 平方取中：取 \(key^2\) 的中间若干位，构成地址
- 折叠法：将 \(key\) 分割成等宽的若干段，取其总和作为地址
- 位异或法：将 \(key\) 分割成等宽的二进制段，经异或运算得到地址
【排解冲突】
- 多槽位：桶单元细分成若干槽位，存放冲突的词条，只要槽位数目不太多，依然可以保证 \(\cal{O}(1)\) 的时间效率
- 独立链：每个桶拥有一个链表，存放对应的一组同义词
- 公共溢出区：单独开辟一块连续空间，发生冲突的词条，顺序存入此区域
- 线性试探：\(r_i(key) = (hash(key) + i) \mod M\)，\(i = 0, 1, 2, 3,..\)
- 平方试探：\(r_i(key) = (hash(key) + i^2) \mod M\)，\(i = 0, 1, 2, 3,..\)
- 双向平方试探：：\(r_i(key) = (hash(key) + (-1)^{i+1}\cdot (\lceil i/2\rceil)^2) \mod M\)，\(i = 0, 1, 2, 3,..\)
- 双散列：预先约定第二散列函数，冲突时，由其确定偏移增量，确定下一试探位置。
2. 桶排序¶
【简单情况】对 \([0,m)\) 内的 \(n(<m)\) 个互异整数，借助散列表做排序。空间 \(\cal{O}(m)\)，时间 \(\cal{O}(m)\)。
【一般情况】若允许相等的元素，可能 \(m\) 远小于 \(n\)，依然使用散列表，每一组同义词，各成一个链表。空间 \(\cal{O}(m+n)\)，时间 \(\cal{O}(n)\)。
【最大缝隙】任意 \(n\) 个互异点均将实轴分为 \(n-1\) 段有界区间，其中最长的一段。
- 一趟线性扫描：找到最左点、最右点
- 散列：将有效范围均等地划分为 \(n-1\) 段（\(n\) 个桶）
- 模余法：通过散列，将各点归入对应的桶
- 在各桶中动态记录最左点、最右点
- 算出相邻（非空）桶之间的距离
- 画家算法：最大的距离即 \(MaxGap\)。
3. 计数排序¶
- 对于小集合 + 大数据类型，计数排序更快。
【纸牌排序】假设已按点数排序，以下稳定地按花色排序
- 经过分桶，统计出各种花色的数量
- 自前向后扫描各桶，依次累加，即可确定各套花色所处的秩区间
- 自后向前扫描每一张牌，对应桶的计数减一，即是其在最终有序序列中对应的秩