1, 词典:散列原理
- 寻值访问
- 两项基本任务:
2,散列函数
- 散列函数的设计原则与评价标准:确定,快速,满射,均匀。
-
散列函数种类:
- 除余法:表长需取做素数。
- MAD法(Multiply-Add-Divide Method)
- 平方取中法:取key2中间的若干位,构成地址。
- 折叠法
- 伪随机数法
- 多项式法:很适合于英文字符串。
- key的预处理:非整数型(浮点数,字符串)转化为整数型。
3,冲突解决: 开散列策略 vs. 闭散列策略
- 开散列(封闭定址)策略方法
- 多槽位法:存在空间效率与时间效率上存在两难处境。
- 独立链法:
-闭散列(开放定址)策略方法
- 开放定址:为每个桶事先约定若干备用桶,他们构成一个查找链。
- 线性试探法
-
需使用惰性删除(查找时跳过,插入时不跳过),以保持查找链连续。
- 平方试探法:改进线性试探法中大量增加的冲突。
- 优缺点分析:
- 优点:数据聚集(clustering)现象缓解。
- 缺点:
- 1) 若涉及外存,I/O将增加;
- 2)无法到达某些空桶位置 -> 改进:表长是素数,且装填因子小于0.5.
-
平方试探法的进一步改进:双向平方试探法。
- 要求表长满足 4k+3,否则正向/逆向子查找链会存在公共桶的情况(不互异).
- 其证明:双平方定理。
- 要求表长满足 4k+3,否则正向/逆向子查找链会存在公共桶的情况(不互异).
4,散列表应用:桶/计数排序
- 原理:将待排序数组数据分到有限数量散列表的桶子里,然后顺序遍历该散列表。
- 时间复杂度:O(n) (在n >> M时).
- 可参考:https://www.cnblogs.com/skywang12345/p/3602737.html