《数据结构》学习笔记 第9章 词典

1， 词典：散列原理

• 寻值访问
• 
• 两项基本任务：
  • 

2，散列函数

• 散列函数的设计原则与评价标准：确定，快速，满射，均匀。
  • 

• 散列函数种类：

  • 除余法：表长需取做素数。
  • MAD法（Multiply-Add-Divide Method）
    • 
  • 平方取中法：取key²中间的若干位，构成地址。
  • 折叠法
    • 
  • 伪随机数法
  • 多项式法：很适合于英文字符串。
    • key的预处理：非整数型（浮点数，字符串）转化为整数型。
  • 

3，冲突解决: 开散列策略 vs. 闭散列策略

• 开散列（封闭定址）策略方法
  • 多槽位法：存在空间效率与时间效率上存在两难处境。
  • 独立链法：
    • 
-闭散列（开放定址）策略方法
• 开放定址：为每个桶事先约定若干备用桶，他们构成一个查找链。
• 线性试探法
  • 

  • 需使用惰性删除（查找时跳过，插入时不跳过），以保持查找链连续。 

• 平方试探法：改进线性试探法中大量增加的冲突。
• 
• 优缺点分析：
  • 优点：数据聚集（clustering）现象缓解。
  • 缺点：
    • 1) 若涉及外存，I/O将增加；
    • 2）无法到达某些空桶位置 -> 改进：表长是素数，且装填因子小于0.5.

• 平方试探法的进一步改进：双向平方试探法。 

  • 要求表长满足 4k+3，否则正向/逆向子查找链会存在公共桶的情况（不互异）.
    • 其证明：双平方定理。

4，散列表应用：桶/计数排序 

• 原理：将待排序数组数据分到有限数量散列表的桶子里，然后顺序遍历该散列表。
• 时间复杂度：O(n) （在n >> M时）.
• 可参考：https://www.cnblogs.com/skywang12345/p/3602737.html