哈希表（Hash Table）

哈希表（Hash table，也叫散列表)

根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。例如：给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash)表，函数f(key)为哈希(Hash) 函数。

常用操作：

1、插入

2、查找

3、删除

计算地址的方法（映射函数的构造）

构造映射函数要考虑的因素：

计算映射函数所需时间 （简单）、关键字的长度、哈希表大小、关键字分布情况、记录查找频率

1． 数字分析法

如果事先知道关键字集合，并且每个关键字的位数比哈希表的地址码位数多时，可以从关键字中选出分布较均匀的若干位，构成哈希地址。

2． 平方取中法

当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。

3． 除留余数法

假设哈希表长为m，p为小于等于m的最大素数，则哈希函数为

h（k）=k  %  p ，其中%为模p取余运算。

例如，已知待散列元素为（18，75，60，43，54，90，46），表长m=10，p=7，则有

    h(18)=18 % 7=4    h(75)=75 % 7=5    h(60)=60 % 7=4   

    h(43)=43 % 7=1    h(54)=54 % 7=5    h(90)=90 % 7=6   

    h(46)=46 % 7=4

此时冲突较多。为减少冲突，可取较大的m值和p值，如m=p=13，结果如下：

    h(18)=18 % 13=5    h(75)=75 % 13=10    h(60)=60 % 13=8    

    h(43)=43 % 13=4    h(54)=54 % 13=2    h(90)=90 % 13=12   

    h(46)=46 % 13=7

此时没有冲突，如图8.25所示。

  0      1      2     3     4     5      6     7     8     9     10     11    12

54

43

18

46

60

75

90

                     

图8.25  除留余数法求哈希地址

4． 伪随机数法

采用一个伪随机函数做哈希函数，即h(key)=random(key)。

解决冲突的方法：

1、开放定址法

这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：

          Hi=（H（key）+di）% m   i=1，2，…，n

其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。

例:已知哈希表长度m=11，哈希函数为：H（key）= key  %  11，则H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为69，则H（69）=3，与47冲突。

 (1)线性探测再散列

dii=1，2，3，…，m-1

特点：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

如果用线性探测再散列处理冲突，下一个哈希地址为H1=（3 + 1）% 11 = 4,仍然冲突，再找下一个哈希地址为H2=（3 + 2）% 11 = 5，还是冲突，继续找下一个哈希地址为H3=(3+3)%1 = 6,此时不再冲突,将69填入5号单元。 

47

26

60

69

 

 

(2)二次探测再散列

  di=12，-12，22，-22，…，k2，-k2    ( k<=m/2 )

特点：冲突发生时，在表的左右进行跳跃式探测，比较灵活。

如果用二次探测再散列处理冲突，下一个哈希地址为H1=（3 + 12）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 - 12）% 11 = 2，此时不再冲突，将69填入2号单元。

69

47

26

60

 

 

(3)伪随机探测再散列

    di=伪随机数序列。

具体实现时，应建立一个伪随机数发生器（如i=(i+p) % m）,并给定一个随机数做起点。

如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，……..，则下一个哈希地址为H1=（3 + 2）% 11 = 5，仍然冲突，再找下一个哈希地址为H2=（3 + 5）% 11 = 8，此时不再冲突，将69填入8号单元，参图8.26 (c)。

47

26

60

69

 

 

2、再哈希法

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

 Hi=RH1（key）  i=1，2，…，k

当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

3、链地址法

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

4、建立公共溢出区

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

代码实现：

链地址法（使用不定长数组实现链表）

#include<iostream>
#include<vector>
using namespace std;
const int M=10000;
const int mod=10000;
struct node
{
    int key;
    int value;
    bool visited;
};
node ha[M];
int hash_find(int key)//返回键值为key在hash表中的地址，如果没找到返回-1
{
    int address=key%mod;
    for(int i=1;i<=M;i++)
        if(ha[address].key==key&&ha[address].visited)
            return address;
    else
            address=(key+i)%mod;
    return -1;
}
int getaddress(int key)//给键值为key的元素在hash表中找一个位置，无法找到返回-1
{
    int address=hash_find(key);
    if(address==-1)
    {
        address=key%mod;
        for(int i=1;i<=M;i++)
        if(!ha[address].visited)
            return address;
    else
            address=(key+i)%mod;
    }
    else
    return address;
    return -1;//hash表已经装满
}
bool hash_insert(int key,int value)//返回是否插入成功
{
    int address=getaddress(key);
    if(address!=-1)
    {
        ha[address].key=key;
        ha[address].value=value;
        ha[address].visited=1;
        return 1;
    }
    else
        return 0;//hash表已经装满
}
bool hash_delete(int key)//返回是否删除成功
{
    int address=hash_find(key);
    if(address!=-1)
    {
        ha[address].key=0;
        ha[address].value=0;
        ha[address].visited=0;
        return 1;
    }
    else
        return 0;
}
int main()
{
       return 0;
}

开放定址法（线性探测再序列解决冲突）

#include<iostream>
#include<vector>
using namespace std;
const int M=10000;
const int mod=10000;
struct node
{
    int key;
    int value;
    bool visited;
};
node ha[M];
int hash_find(int key)//返回键值为key在hash表中的地址，如果没找到返回-1
{
    int address=key%mod;
    for(int i=1;i<=M;i++)
        if(ha[address].key==key&&ha[address].visited)
            return address;
    else
            address=(key+i)%mod;
    return -1;
}
int getaddress(int key)//给键值为key的元素在hash表中找一个位置，无法找到返回-1
{
    int address=hash_find(key);
    if(address==-1)
    {
        address=key%mod;
        for(int i=1;i<=M;i++)
        if(!ha[address].visited)
            return address;
    else
            address=(key+i)%mod;
    }
    else
    return address;
    return -1;//hash表已经装满
}
bool hash_insert(int key,int value)//返回是否插入成功
{
    int address=getaddress(key);
    if(address!=-1)
    {
        ha[address].key=key;
        ha[address].value=value;
        ha[address].visited=1;
        return 1;
    }
    else
        return 0;//hash表已经装满
}
bool hash_delete(int key)//返回是否删除成功
{
    int address=hash_find(key);
    if(address!=-1)
    {
        ha[address].key=0;
        ha[address].value=0;
        ha[address].visited=0;
        return 1;
    }
    else
        return 0;
}
int main()
{
       return 0;
}