第11章 散列表

一、概念

1.综述

散表表仅支持INSERT、SEARCH、DELETE操作。

把关键字k映射到槽h(k)上的过程称为散列。

多个关键字映射到同一个数组下标位置称为碰撞。

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

2.散表函数

（1）若函数为h(k)=k，就是直接寻址表

（2）除法散列法：h(k) = k mod m

（3）乘法散列法：h(k) = m (k A mod 1) (0<A<1)

（4）全域散列：从一组仔细设计的散列函数中随机地选择一个。（即使对同一个输入，每次也都不一样，平均性态较好）

3.冲突解决策略

（1）链接法

（2）开放寻址法

a.线性探测：h(k, i) = (h'(k) + i) mod m

b.二次探测：h(k, i) = (h'(k) + c1i + c2 i^2) mod m

c.双重散列：h(k, i) = (h1(k) + i * h2(k)) mod m

（3）完全散列：设计一个较小的二次散列表

二、代码

代码中用到了函数指针，函数指针的用法参考函数指针总结

//Hash.h
#include <iostream>
using namespace std;

int m, NIL = 0;
//11.4 开放寻址法
typedef int (*Probing)(int k, int i);
int h(int k)
{
    return k % m;
}
int h2(int k)
{
    return 1 + k % (m-1);
}
//线性探测
int Linear_Probing(int k, int i)
{
    return (h(k) + i) % m;
}
//二次探测
int Quadratic_Probint(int k, int i)
{
    int c1 = 1, c2 = 3;
    return (h(k) + c1 * i + c2 * i * i) % m;
}
//双重探测
int Double_Probint(int k, int i)
{
    return (h(k) + i * h2(k)) % m;
}
int Hash_Insert(int *T, int k, Probing p)
{
    int i = 0, j;
    do{
        j = p(k, i);
        if(T[j] == NIL)
        {
            T[j] = k;
            return j;
        }
        i++;
    }
    while(i != m);
    cout<<"error:hash table overflow"<<endl;
}

int Hash_Search(int *T, int k, Probing p)
{
    int i = 0, j;
    while(1)
    {
        j = p(k, i);
        if(T[j] == NIL || i == m)
            break;
        if(T[j] == k)
            return j;
        i++;
    }
}