算法导论详解(9) 第十一章散列表

直接寻址表(direct-address table)缺点：如果全域U很大，分配直接寻址表T也不太现实；另一方面，实际存储的关键字集合K相对于U来说可能很小，导致浪费空间。

散列表综述

散列表（hash table，也叫哈希表），支持INSERT、SEARCH、DELETE操作。

散列表可以使得在表小的情况下仍能够保存数据，并且能够在常数时间O(1)内完成查询。为什么是常数时间呢？因为我们不需要比较，不需要遍历查找，只要计算出地址，有待查询的值那么就找到了；没有，那么表中就不存在。

把关键字k映射到槽h(k)上的过程称为散列。h表示散列函数(hash function)，由关键字k计算出槽(slot)的位置。

多个关键字映射到同一个数组下标位置(槽)称为碰撞（或冲突，collision）。

好的散列函数应使每个关键字都等可能地散列到m个槽位中。

链接法解决冲突

链接法：把散列到同一个槽的所有元素都放在一个链表中。槽中存放指向该槽的所有元素的链表的表头；如果不存在这样的元素，则槽中为NIL。

链接法散列的分析

一个存放n个元素的、具有m个槽位的散列表T，其装载因子(load factor)为：$\alpha = \frac nm$，表示一个链的平均存储元素数。

简单均匀散列(simple uniform hashing)：一个给定元素，等可能地散列到m个槽位中的任意一个上，且与其他元素被散列到什么位置无关。

在简单均匀散列的假设下，对于用链接法解决冲突的散列表，一次不成功查找的平均时间为$\Theta(1+\alpha)$，一次成功查找所需的平均时间也为$\Theta(1+\alpha)$

当散列表的槽数与表中元素个数成正比，则有$n= \text{O}(m)$，查找需要常数时间$\text{O}(1)$。当链表为双向链表时，插入和删除的最坏情况也是$\text{O}(1)$。

Hash函数（11.3，P147）

我们如何设计一个好的Hash函数（哈希函数，散列函数）？本节介绍了三种设计哈希函数的方法：除法散列、乘法散列和全域散列。

好的哈希函数的特点

这里有两个要点：

一个好的哈希函数应该能够将关键字均匀的分配到哈希表T中；

而关键字的分布率不应该影响这种均匀性。

除法散列法

定义hash函数为 $h(k) = k \;\text{mod}\; m$

m取值的原则就是m选为质数且不能太接近2或者10的幂次。

原因：键值的低位可能具有某种分布规律，如果选择2或者10的幂次容易出现冲突。比如$2^r$，关键字只会考虑二进制的低r位；十进制类似。

乘法散列法

乘法散列法的公式为：$h(k) = m(kA\; \text{mod}\; 1) $

其中，$0<A<1$。

一般的实现方法如下：假设计算机字长是w位，限制A是形如$A =\frac {s}{2^w}$的分数，整数s取值范围为$0< s <2^w $。用整数$s=A\cdot 2^w$乘上k，其结果是2w位的值$r_1 2^w + r_0 $

A的取值理想情况为$ A \approx \sqrt 5-1 = 0.6180339887\cdots $。（这不就是黄金分割率么……）根据A的取值计算s的值。

乘法散列法的优点是m的取值不是很关键，一般取为m=2^r。

11.3-4

考虑一个大小为m=1000的散列表和一个对应的散列函数h(k)=m(kAmod1),其中A=(√5-1)/2,试计算关键字61,62,63,64和65被映射到位置。

直接根据公式计算，实现代码如下：

#include <iostream>  
#include <math.h>  
using namespace std;  
const double A=(sqrt(5)-1)/2.0;  
int hash(int k,int m)  
{  
    double x=(A*k-(int)(A*k))*m;  
    return x;  
}  
void main()  
{  
   int k;  
   while (cin>>k)  
   {  
       cout<<"Hash["<<k<<"]="<<hash(k,1000)<<endl;  
   }  
}

开放寻址法

开放寻址法是另一种解决冲突的方法。

开放寻址法的特点：装载因子不会超过1；不用指针就可以计算出槽的序列。

插入元素的过程叫做探查(probe)：连续地检查散列表，直到找到一个空槽来放置待插入的关键字为止。检查顺序依赖于待插入的关键字

开放寻址法的散列函数有第二个参数：探查序号。

插入元素的伪码：

HASH-INSERT(T,k)
	i = 0
    repeat
    	j = h(k, i)
        if T[j] = NIL
        	T[j] = k 
            return j
        else i = i + 1
    util i == m
    error "hash table overflow"

查找元素的伪码：（由于是依次插入，因此可以依次查找；有个前提：关键字不会被删除）

HASH-SEARCH(T,k)
	i = 0
    repeat
    	j = h(k, i)
        if T[j] = K 
            return j
        else i = i + 1
    util T[j] == NIl or i == m
    return NIL

在开放寻址法中，删除操作比较困难，但也有解决办法，在必须删除关键字的应用中，往往采用链接法解决碰撞。

三种探查技术

三种探查技术来计算探查序列：

1)线性探查：
$$h(k,i)=(h’(k)+i)\text{mod}\; m,\; i=0,1,\cdots,m-1$$
线性探查存在问题：一次群集(primary clustering)。

2)二次探查：
$$h(k,i)=(h’(k)+c_1i+c_2i^2)\text{mod}\; m, \; i=0,1,\cdots,m-1$$
二次探查存在问题：二次群集(secondary clustering)。二次探查与线性探查都是初始位置决定了探查序列，且只有m个探查序列被使用到。

3)双重探查：
$$h(k,i)=(h_1(k)+ih_2(k))\text{mod}\; m, \; i=0,1,\cdots,m-1 $$
双重探查要求值$h_2(k)$与表的大小m互素。一种简便的方法是：m取2的幂，$h_2(k)$只产生奇数；或者m为素数，h2总是返回比m小的正整数。

由于每一对可能的$ (h_1(k), h_2(k))$都会产生一个不同的探查序列，因此双重散列法用到了$\Theta(m^2) $种探查序列。

双重散列的例子：
$$h_1(k) = k \;\text{mod}\; m ,\;h_2(k) = 1+(k\; \text{mod} \;m’) $$
取m为素数，$m’ $略小于m（比如，m-1）

开放寻址散列的分析：

定理11.6 给定一个装载因子a=n/m<1的开放寻址散列表，假设散列是均匀的，在一次不成功的查找中，期望的探查数至多为1/(1-a).。

不成功的查找即：最后一次查找为NIL，且前面的Hash table查找都是被占用但是不包含所查的关键字。因此，可以推论插入的期望值，即：插入前需要做一次不成功的查找。

推论11.7 均匀散列，平均情况下，向一个装载因子为a的开放寻址散列表中插入一个元素时，至多需要做1/(1-a)次探查。

查找的过程和插入类似，假设待查找的关键字k的插入位置为i，则，根据推论11.7，有探查的期望次数至多为$1/(1-i/m) = m/(m - i)$。对散列表的所有n个关键字求平均，则得到一次成功查找的探查期望次数：
$$\begin{align}
\frac 1 n \sum_{i = 0}^{n-1} \frac {m}{m-i}
& = \frac mn \sum_{i = 0}^{n-1}\frac {1}{m-i} =\frac 1\alpha \sum_{k = m-n+1}^{n} \frac 1k \leqslant\frac 1 \alpha \int_{m-n}^{m}\frac 1x dx\\
& =\frac 1\alpha ln \frac m{m-n} = \frac 1a ln\frac1{1-a}
\end{align}$$

因此得到定理11.8：

定理11.8 给定一个装载因子为a<1的开放寻址散列表，假设散列是均匀的，一次成功查找中的期望探查数至多为(1/a)ln(1/(1-a)).

11.4-1

考虑将关键字10,22,31,4,15,28,17,88,59用开放寻址法插入到一个长度为m=11的散列表中，主散列函数为h'(k)=k mod m.说明用线性探查，二次探查(c1=1,c2=3)以及双重散列h2(k)=1+(k mod (m-1))将这些关键字插入散列表的结果。

C++实现代码：
Introduction_to_Algorithms/Part_3/Chap_11/hash_table.cpp

#include<iostream>
#include<cstring> // for memset
using namespace std;
 
#define Null -1
#define DELETED -2
/*
 * 算法导论习题11.4-1 开放寻址法实现散列表。
 * 顺便也实现了搜索与删除。
 * 
 * Linux下g++5.4.0编译通过。
 * 命令：
 *   $ g++ -o hash_table.out hash_table.cpp -std=c++11
 *   $ ./hash_table.out
 */
const int m = 11;  //槽位数量
const int c1 = 1;
const int c2 = 3;
void Print(int *T)
{
    int i;
    for(i = 0; i < m; i++)
        cout << T[i] << ' ';
    cout << endl;
}
int h(int k) {
    return k % m;
}
// 线性探查
int linear_probing(int key, int i) {
    return (key + i) % m;
}
//二次探查
int quadratic_probing(int key, int i) {
    return (key + c1 * i + c2 * i * i) % m;
}
//双重散列
int double_hashing(int key, int i) {
    return (key + i * (1 + key % (m - 1))) % m;
}
using PF = int (*) (int, int);   //函数指针
PF hash_functions[3] = {linear_probing, quadratic_probing, double_hashing};
// 判断探查的状态：当槽为空或者已到末尾时，为True
bool probe_state(int T[], int j) {
    return T[j] == Null || T[j] == DELETED || T[j] == 0;
}
int hash_insert(int T[], int key, PF hash_function) {
    int k = key;
    int i = 0;
    do
    {
        int j = hash_function(k, i);  //这里通过函数指针，可以在调用时选择线性、二次及双重探查。关于函数指针的简单介绍，可以查看http://wangwlj.com/2018/01/06/CPP_06/
        if (probe_state(T, j))
        {
            T[j] = k;
            return j;
        }
        else ++i;
    } while (i != m);
    cerr << "hash table overflow" << endl;
}
int hash_search(int T[], int k, PF hash_function) {
    int i = 0, j = 0;
    do
    {
        j = hash_function(k, i);  //这里可以替换成二次，双重探查。插入，查找，删除函数同时被替换  
        if (T[j] == k)
        {
            return j;
        }
        else ++i;
    } while (!probe_state(T, j));
    return Null;
}
void hash_delete(int T[], int k, PF hash_function)  
{  
    int j = hash_search(T, k, hash_function);  //首先先找到该关键字k  
    if (j != Null)  
    {  
       T[j] = DELETED;  //如果找到了，那么设置其为空。  
       cout << "关键字：" << k << " 删除成功！" << endl;  
    }  
    else cout << "待删除的数据不在表中！" << endl;  
}
int main() {
    int key[9] = {10, 22, 31, 4, 15, 28, 17, 88, 59};	
    static int T[11];
   
    for (int i = 0; i < 3; ++i) { 
        memset(T, 0, sizeof(T));  // 初始化T为全零
    	for (int j = 0; j < 9; ++j) {
            hash_insert(T, key[j], hash_functions[i]); 
        }
	    Print(T);
	    cout << "搜索关键字：88，返回结果：" << hash_search(T, 88, hash_functions[i]) << endl;
	    hash_delete(T, 88, hash_functions[i]);
	    cout << "删除 88 之后元素为：";
	    Print(T);
	    cout << endl;
    }
	return 0;
}