知识摘要

散列函数：

• （可使用Horner法则）

• 装填因子 λ ：

  • 散列表中元素个数与散列表大小的比值

    冲突解决：

    - 分离链接法：

  • 其做法是将散列到同一个值的所有元素保留在一个表中。

  • 如果在散列的诸例程中不包括删除操作，则最好不要使用表头，因为表头不仅不能简化问题而且还浪费了大量空间

  • 期望：

    • 尽量使得表的大小与预料的元素个数差不多，即让

      - 开放定址法：

  • 当冲突发生时尝试选择另外的单元。一般地，单元满足

  • 期望：

    • 尽量使元素个数不多于表大小的一半，即让

      一、线性探测法

    • 典型情形：

    • 优点：
      • 1. 只要表足够大，总能找到一个自由单元

    • 缺点：

      • 1. 花费的时间多
      • 1. 占据的单元会开始形成区块，其结果称为一次聚集（primary clustering）.于是，散列到区块中的任何关键字都需要多次试选单元才能解决冲突

           二、平方探测法

    • 典型情形：

    • 优点：
      • 1. 消除线性探测中一次聚集问题
      • 1. 当表的大小是素数且表至少有一半是空的时候，保证能插入一个新的元素

    • 缺点：

      • 1. 虽然消除了一次聚集，但散列到同一位置上的那些元素将探测相同的备选单元。这叫做二次聚集。二次聚集是理论上的一个小缺憾
      • 1. 当装填因子大于0.5时，容易造成插入的失败

           三、双散列

    • 典型情形：

（其中R为小于TableSize的素数）

  - 优点：
     - 1. 排除二次聚集问题的缺憾
  - 缺点：
     - 1. 造成额外的一些乘法和除法的开销

- 再散列：

• 当原散列元素个数超过表大小的一半后将重新设置新的散列函数。一般地转变有

=>
（其中S2为两倍S1后的第一个素数）

• 运行时间：O(N)
• 优点：
  • 1. 无需担心表的大小，因为它总能根据自身元素规模自动扩大
• 缺点：
  • 1. 操作较为昂贵，但由于不是经常发生，故实际效果并没有太差

       - 可扩散列：