Home 计算机科学 数据结构与算法

# 哈希表 / 散列表

应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表

# 哈希查找 / 散列查找

利用哈希函数进行查找的过程叫哈希查找

# 哈希映射函数 / 散列函数

在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数

# 原始 hash 函数

简单一点的 hash 算法就是直接取模 (除留余数法)。

高级一点的 hash 算法会模乘以一个大素数来将源数据的分布规律变得不那么显著，也就是说，不管输入的是一串分布很紧凑的数字序列还是很稀疏的数字序列，生成的结果都是非常分散的数字序列。

linux 内核代码里面的这个 hash 要更高一级，包含 2 个特征：
最接近 32 位或者者 64 位上限黄金分割点的素数，
只要要最少的移位和求和就能生成。
这个素数定义如下：

c
/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
#define GOLDEN_RATIO_PRIME_32 0x9e370001UL

前者确保即便是 1，2 这样的小数也会被乘溢出，被轻易打散。素数非常大还可以使无论输入如何，生成的哈希值的高位都是足够随机的，有助于改善生成哈希值高位总是相近的问题。

后者确保任何一个整数乘这个大素数的时候都可以通过最少的移位和求和就可得到乘积，不用傻傻的真的相乘。

# 直接定址法

取关键字或关键字的某个线性函数作哈希地址，即H(key)=keyH(key)=key 或H(key)=a⋅key+bH(key)=a·key+b (a,b 为常数)

特点：直接定址法所得地址集合与关键字集合大小相等，不会发生冲突，但实际中很少使用。

# 数字分析法

对关键字进行分析，取关键字的若干位或组合作为哈希地址。

适用于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。

# 平方取中法

将关键字平方后取中间几位作为哈希地址。一个数平方后中间几位和数的每一位都有关，则由随机分布的关键字得到的散列地址也是随机的。散列函数所取的位数由散列表的长度决定。

适于不知道全部关键字情况，是一种较为常用的方法

# 折叠法

将关键字分割成位数相同的几部分 (最后一部分可以不同)，然后取这几部分的叠加和作为哈希地址。

数位叠加有移位叠加和间界叠加两种：

  • 移位叠加：将分割后的几部分低位对齐相加。
  • 间界叠加：从一端到另一端沿分割界来回折迭，然后对齐相加。

适于关键字位数很多，且每一位上数字分布大致均匀情况。

# 除留余数法

取关键字被某个不大于哈希表表长 m 的数 p 除后所得余数作哈希地址，即:
H(key)=key%p(p≤m)H(key)=key\ \% \ p\ (p\leq m)
是一种简单、常用的哈希函数构造方法。

利用这种方法的关键是 p 的选取，p 选的不好，容易产生同义词。p 的选取的分析:

  • 选取p=2i(p≤m)p=2^i\ (p\leq m): 运算便于用移位来实现，但等于将关键字的高位忽略而仅留下低位二进制数。高位不同而低位相同的 关键字是同义词。
  • 选取p=q×f(q、f都是质因数，p≤m)p=q\times f\ (q、f 都是质因数，p\leq m): 则所有含有 q 或 f 因子的关键字的散列地址均是 q 或 f 的倍数。
  • 选取pp 为素数或p=q×f(q、f是质数且均大于20，p≤m)p=q\times f\ (q、f是质数且均大于20，p\leq m): 常用的选取方法，能减少冲突出现的可能性。

# 随机数法

取关键字的随机函数值作哈希地址，即H(key)=random(key)H(key) = random(key)

当散列表中关键字长度不等时，该方法比较合适。

# 冲突处理

# 开放定址法

当冲突发生时，形成某个探测序列；按此序列逐个探测散列表中的其他地址，直到找到给定的关键字或一个空地址 (开放的地址) 为止，将发生冲突的记录放到该地址中。散列地址的计算公式是：

Hi(key)=(H(key)+di)%m,i=1,2,...,k(k≤m−1)H_i(key)=(H(key)+d_i) \% m, i=1, 2, ..., k (k \leq m-1)

其中：
H(key)H(key)：哈希函数；
mm：散列表长度；
did_i：第 i 次探测时的增量序列；
Hi(key)H_i(key)：经第 i 次探测后得到的散列地址。

核心在于探测序列did_i，即如何形成探测序列。

# 线性探测法

将散列表T[0...m−1]T[0 ...m-1] 看成循环向量。当发生冲突时，从初次发生冲突的 位置依次向后探测其他的地址。

增量序列为:di=1,2,3,...,m−1d_i=1, 2, 3, ..., m-1

设初次发生冲突的地址是 h，则依次探测 T[h+1],T[h+2]...,T[h+1],T[h+2]..., 直到T[m−1]T[m-1] 之后又循环到表头，再次探测T[0]，T[1]...T[0]，T[1]...，直到 T [h-1]$。探测过程终止的情况是:

  • 探测到的地址为空：表中没有记录。
    • 若是查找则失败；
    • 若是插入则将记录写入到该地址；
  • 探测到的地址有给定的关键字:
    • 若是查找则成功；
    • 若是插入则失败；
  • 直到T[h−1]T[h-1] 之后回到T[h]T[h]:
    • 仍未探测到空地址或给定的关键字，散列表满。

优点：只要空间未满，总能找到空闲的位置存放新插入的数据，能充分利用整个表的空间。

问题：例如原本有两个 cluster 数据，随着哈希表不断扩充，两个 cluster 会逐渐聚集为一个更大的 cluster，产生数据聚集的问题。

循环上限did_i 的ii 最大为nn.

# 二次探测法 (平方探测法) (变体很多，需要看题)

原始did_i：di=i2d_i = i^2

原始序列：di=12,22,32...d_i = 1^2, 2^2, 3^2 ...

改进did_i：di=(−1)i−1⋅⌊i+12⌋2d_i = (-1)^{i-1}\cdot\left\lfloor\frac{i+1}{2}\right\rfloor^2

改进序列：di=12,−12,22,−22,32,−32...di = 1^2, -1^2, 2^2, -2^2, 3^2, -3^2 ...

循环上限：did_i 的ii 最大为nn，有时可以是\frac{n}

二次探测针对线性探测法的 “聚集” 问题进行了改进，避免了 “聚集” 现象产生。

原始did_i 在不断扩充哈希表时会导致一半的空间用不上，改进的did_i 针对这一问题进行了改进。

优点：探测序列跳跃式地散列到整个表中，不易产生 “冲突聚集” 现象。

问题：不能保证探测到散列表的所有地址，不能充分利用整个表的空间。(“表满不了”)

# 伪随机探测法

增量序列使用一个伪随机函数来生成一个落在闭区间 [1,m-1] 的随机序列。

# 再哈希法

这种方法是同时构造多个不同的哈希函数：

Hi=RHi（key），i=1，2,3，…,nH_i=RH_i（key），i=1，2,3，…,n

RHiRH_i：一组不同的哈希函数，第 1 次发生冲突时用RH1RH_1 计算，第 2 次发生冲突时用RH2RH_2 计算，以此类推直到某个HiH_i 不再发生冲突为止。

优点：不易产生聚集

问题：增加了计算时间

# 链定址法 (拉链法)

将所有关键字为同义词 (散列地址相同) 的记录存储在一个单链表中，并用一维数组存放链表的头指针

设散列表长为 m，定义一个一维指针数组: RecNode *linkhash[m] ，其中 RecNode 是结点类型，每个分量的初值为空。

凡是散列地址为 k 的记录都插入到以 linkhash[k] 为头指针的链表中，插入位置可以在表头或表尾或按关键字排序插入。

注意：若某一位置已存储的冲突元素有 4 个，查找失败需要比较 5 次，包括最后一次空指针。

# 建立公共溢出区

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表.(注意：在这个方法里面是把元素分开两个表来存储)

# 哈希表的删除操作

不能抹除该位置的元素，而是需要一个特殊字符 "special key" 取代原来的位置，代表这里原本有元素但是被删除了。

# 哈希表查找分析

由于 “冲突” 的存在，哈希表效率的评价仍然需要 ASL。

哈希表的 填满因子 / 装载因子 λ\lambda ( 或α\alpha ) 定义：

λ=已经插入的元素数哈希表长度\lambda=\frac{已经插入的元素数}{哈希表长度}

The expected number U(2)U(2) of probes in an unsuccessful search is:

U(λ)=∑k=1∞kλk−1(1−λ)=11−λU(\lambda)=\sum_{k=1}^{\infty}k\lambda^{k-1}(1-\lambda)=\frac{1}{1-\lambda}

So the expected number of probes for successful searches (AVL) is:

S(λ)=1λ∫0λU(λ)dx=1λln11−λS(\lambda)=\frac{1}{\lambda}\int_{0}^{\lambda}{U(\lambda)dx}=\frac{1}{\lambda}ln\frac{1}{1-\lambda}

线性探测法的平均查找长度是：

Snl成功≈12×(1+11−λ)Snl失败≈12×(1+1(1−λ)2)S_{nl成功}≈\frac{1}{2}\times(1+\frac{1}{1-\lambda})\\ S_{nl失败}≈\frac{1}{2}\times(1+\frac{1}{(1-\lambda)^2})

二次 / 平方探测法的平均查找长度是：

Snl成功≈−1λ×ln(1−λ)Snl失败≈1λS_{nl成功}≈-\frac{1}{\lambda}\times ln(1-\lambda)\\ S_{nl失败}≈\frac{1}{\lambda}

链地址法解决冲突的平均查找长度是：

Snl成功≈1+λ2Snl失败≈λ+e−λS_{nl成功}≈1+\frac{\lambda}{2}\\ S_{nl失败}≈\lambda+e^{-\lambda}

# 代码例题

假设构建哈希表使用线性探查法解决冲突，试计算每次查找的关键字比较次数。

  1. 可能的关键字为正整数；
  2. 使用哈希函数 h (k,M)= k % M, M 为哈希表的长度；
  3. 因为 0 不是关键字，所以，假定用 0 表示空单元；
  4. 为了区分空单元和删除后的 “空单元”，给每个单元添加一个布尔型标识，表示该单元是否空；空单元设置为 true，非空设置为 false;
  5. 假定删除关键字时，只将标识置为 true, 关键字域不变。
c++
#include <iostream>
#include <vector>
using namespace std;
typedef int Key;
typedef pair<Key, bool>  Cell;
//a cell consists of a key and a flag of bool. If the cell is empty, the second component is set to true, otherwise false.
typedef vector<Cell> Table; //type of a hash table
//hash function, where M should be the hash table size.
size_t h(Key k, size_t M = 11){
    return k % M;
}
// 它返回线性探查法解决冲突查找是否成功、查找终止的下标以及关键字的比较次数
pair<pair<bool, size_t>, int> lookup(const Table& t, const Key k){
    size_t M=t.size();
    size_t hi=h(k,M),j,i;
    int count = 0;
    for(j=0;j<M;++j){
        i=(hi+j)%M;
        ++count;
        if(t[i].first==0)break;
        else if(t[i].first==k&&!t[i].second)return make_pair(make_pair(1,i),count);
    }
    return make_pair(make_pair(0,i),count);
}