散列（Hash）表

基本概念

  • 基本思想：记录的储存位置与关键字之间存在对应关系
  • 对应关系-hash函数
  • Address(i) = H(key) 根据关键字函数映射

散列表的查找

1
2
3
根据散列表函数 H(key)=k
查找key=9 ，则访问H(9)=9号位置 ，若内容为9则成功；
若查不到，则返回一个特殊值 ，如空指针或空记录。

正题

  1. 数值的哈希

    Hash函数的作用就是通过对数据进行计算。得出存放该放该数据的对应位置。使得数据和存放位置相对应完成高效的查找。因此，Hash表的各种操作能否做到常数时间的关键就是Hash函数的构造。

  • 取余法

    用关键字key除于M的余数作为hash表中的位置函数表达式可以写成：h(k)=k%P ，适用于整数

  • 乘积取整法

    用关键字k除于一个在（0 ，1）中的实数A （最好是无理数） ，得到一个（0 ，k）之间的实数；取出小数部分 ，乘以M，再取整数部分 ，即得k在Hash表中位置。函数表达式为：

    这类函数适用于小数

  1. 冲突处理法

    散列表会有冲突，即多个不同的关键值对应同一个索引，所以需要设计一些结构去解决这些冲突

  • 挂链法（Separate Chaining)

    挂链法是一种解决冲突的方法。具体来说就是当有两个不同键值对应的索引相同的是，用链表去把它们连起来。

    当查询/插入/删除一个元素时 ，只需要进入对应链表暴力查询/插入/删除即可。

  • 开放地址法

    在开放地址法中，所有的元素都被直接散列表，散列表中，而非像挂链法一样，在每个散列表的位置上再挂出去一条链。所以我们需要闪电表的大小不能小于插入的元素个数。

    开放地址法依赖于一个特殊的函数H(x ,k) ,它指明了如果前K次尝试访问位置都被占住，那么下一个应该尝试访问哪个位置。

    特殊的，我们不能简单将一个元素从散列表中删除。因为这可能会使部分元素在将再不能被查询到，所以我们只能将它打上删除标记及标记为“已删除”。当尝试插入“已删除”的位置时就插入。查询时则并不在“已删除”的位置停下，而是接着通过H(x ,k)。尝试下一次访问。