哈希表查找概述

0.前言

本节内容如下：
1.散列表查找定义
2.散列函数的构造方法
3.处理散列冲突的方法
4.散列表查找算法实现
5.STL中hashtable结构概述

1.散列表查找定义

1.散列表定义：

在说明散列表查找的概念之前，我们来说说什么是散列表呢？散列表：亦称哈希表。采用散列技术将记录存储在一块连续的存储空间内，这块连续存储空间称为散列表。(hash table)。

2.散列技术：

现在可能会好奇什么是散列技术呢？散列技术：在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。我们将这种对应关系f称为哈希函数或者散列函数。散列函数的构造我们在后面讲。

3.散列表查找定义：

散列表查找：在查找时，直接得到待查找值（关键字）的存储位置，然后查找存储位置上有没有这个关键字。那么怎么获取存储位置呢？当然是根据散列函数找到待查找值得存储位置呢。这样一来，我们在查找得时候无需进行比较就可以获得待查找值得存储位置。

2.散列函数的构造方法

一个好的散列函数有两个简单的原则可以参考：
1.计算简单：也就是通过散列函数求存储位置得计算时间不应该超过其他查找技术与关键字比较得时间。如果设计得散列函数得计算时间都超过了其他查找技术与关键字比较的时间，那这个散列函数是不是得枪毙了。
2.散列地址分布均匀：尽量让散列地址均匀分布在存储空间中，这样可以保证存储空间得有效利用，也可以减少处理冲突而消费得时间。

几种常用的散列函数构造函数方法：

1.直接定址法

笔者认为这是最简单得散列函数构造方法。假如我们要存储0到100岁的人口统计表。那么我们选择一条年龄-人口记录中的主码年龄并按照f(key) = key的关系进行存储。假如我们要存储1980年到2000年的出生人口数统计表呢？我们可以选择出生年份并按照f(key) = key - 1980的关系进行存储。我们现在应当对直接定址法有了认识，也就是说取关键字的某个线性函数值为散列地址，即f(key) = a * key + b,其中ab均为常数。
这种方法虽然简单，但是得事先知道关键字分布情况，并且此法只适合查找表较小并且连续得情乱。由于这些缺点此法并不常用。

2.数字分析法

假设我们现在选取了一条记录中得关键字进行存储（通常关键字位数较多），那么我们抽取关键字得一部分来计算散列存储位置。这个抽取方法通常有反转数字，右环位移等方法。
此法通常适合处理关键字位数较多的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀则考虑这个方法。

3.平方取中法

假设有一个待存储的关键字为4321，那么它的平方为18671041，再抽取中间三位就可以是671或者710用作散列地址。
这个方法适用于不知道关键字的分布情况，而位数又不是很大的情况。

4.折叠法

折叠法是将关键字从左到右分割成位数相等的几部分（最后一位位数不够可以短些），然后将这几部分叠加求和，并按散列表表长取后几位作为散列地址。比如说待存储的关键字为9876543210.我们的散列表表长为987，654，321，0，叠加求和为1962，然后再选取后三位962（长度为散列表的长度）作为散列地址。
这个方法不需要知道关键字的分布，适合关键字位数较多的情况。

5.除留余数法

对于散列表长为m的散列函数公式为：f(key) = key % p(p <= m)。这个方法可以对关键字直接取模也可以在折叠，或者平方取中后取模。
这个方法关键在于选取p，如果p选择不当极有可能在计算存储地址时产生冲突。当然根据前辈们的经验，如果散列表表长为m,则p为小于或者等于表长的最小质数或不包含小于20质因子的合数。此法是最常用的散列函数构造方法。

6.随机数法

选择一个随机数，取关键字的随机函数值为它的散列地址，也就是f(key) = random(key).这里的random为随机函数。这个方法适用于关键字的长度不等的情况下。

3.处理散列冲突的方法

我们可能会碰到这种情况：有两个或者多个关键字通过散列函数计算得到的存储地址确实同一个。也就是说，有两个不同的关键字key1,key2,它们得f(key1)和f(key2)确是相同得。这种现象称为碰撞或者冲突(collision)。并且我们将key1和key2称为这个散列函数得同义词(synonym)。
下面介绍几种处理散列冲突的方法：

1.开放定址法

开放定址法就是一旦发生了冲突就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。我们也把这种解决冲突的开放定址法称为线性探测法。一旦发生冲突计算下一个存储位置的散列函数为：fi(key) = (f(key) + di) % m(di = 1,2,3,4.....m-1)其中m为散列表表长。i为第i次在某个存储位置发生冲突。

二次探测法：我们对上述的散列函数稍微做修改，为了不让关键字都聚集在某一块区域，增加平方运算。即fi(key) = (f(key) + di) % m(di = 1^2,-12,2^2,-22,.....q^2,-q2,q <= m/2).

随机探测法：在冲突发生时，我们采用随机函数计算位移量di。即fi(key) = (f(key) + di) % m(di是一个随机数列)

总之，开放定址法只要在散列表没有被填满时，总是能找到不发生冲突的散列地址。这是我们常用的解决冲突的方法。在解决冲突的时候，我们会碰到都不是同义词却需要争夺一个地址的情况，我们称这种现象为堆积。堆积的出现，使得我们需要不断处理冲突，使得插入和查找效率降低。

2.再散列函数法

每当发生散列地址冲突时，就换一个散列函数计算散列地址，总会有一个散列函数可以将冲突解决掉。即fi(key) = RHi(key)(i = 1,2,3....k).这个方法需要要求我们预先准备好多个散列函数，这样也会增加计算时间，并使得关键字不聚集。

3.链地址法

链地址法：将所有关键字为同义词的记录存储再一个单链表中（同义词的概念我们前面讲过），我们称这种表为同义词子表，在散列表中只存储所有同义词表的头指针。这种方法的优点是不存在冲突换址的问题，有多少个冲突都只是在单链表中增加结点的问题。这也是标准库hashtable的底层实现处理散列冲突的方法。

举个例子，假设我们要对关键字集合{12，67，56，16，25，37，22，29，15，47，48，34}采用除留余数法p取12这种哈希函数进行链地址法存储，则可以得到如下图结构：

链地址法示例.png
链地址法的优点是对于可能会造成很多冲突的散列函数来说，提供了绝不会出现找不到地址的保障。但缺点是如果在某个位置冲突过多，那么单链表的结点数较多就会带来查找关键字（需要遍历单链表）的性能损耗。那么标准库如何缓解呢？标准库用一个动态数组vector（vector中的每个元素也称为篮子）存储头指针，如果所有同义词表即单链表的总结点数超过了vector的容量则再次rehashing打散。也就是说vector容量扩充为下一个已经预定义好的容量。重新使用除留余数法来计算关键字的存储位置。

4.公共溢出区法

公共溢出区法：如果对某个关键字根据哈希函数求解出的存储位置已有关键字（发生冲突）则将该关键字存储在溢出表中。
在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行比对，如果相等则查找成功。如果不相等就到溢出表顺序查找。如果相对于基本表而言，溢出表的冲突数据较少，公共溢出区的结构查找性能还是可以的。

4.散列表查找算法实现

#include <stdio.h>    
#include <stdlib.h>   
#include <cassert>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100 /* 存储空间初始分配量 */

#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12 /* 定义散列表长为数组的长度 */
#define NULLKEY -32768 

typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */

typedef struct
{
    int* elem; /* 数据元素存储基址，动态分配数组 */
    int count; /*  当前数据元素个数 */
}HashTable;

int m = 0; /* 散列表表长，全局变量 */

/* 初始化散列表 */
Status InitHashTable(HashTable* H)
{

    m = HASHSIZE;
    H->count = m;
    H->elem = (int*)malloc(m * sizeof(int));
    assert(H->elem != nullptr);

    for (int i = 0 ; i < m ; i++)
        H->elem[i] = NULLKEY; 

    return OK;
}

/* 散列函数 */
int Hash(int key)
{
    return key % m; /* 除留余数法 */
}

/* 插入关键字进散列表 */
void InsertHash(HashTable * H, int key)
{
    int addr = Hash(key);               /* 求散列地址 */
    while (H->elem[addr] != NULLKEY)    /* 如果不为空，则冲突 */
    {
        addr = (addr + 1) % m;          /* 开放定址法的线性探测 */
    }
    H->elem[addr] = key;                /* 直到有空位后插入关键字 */
}

/* 散列表查找关键字 */
Status SearchHash(HashTable H, int key, int* addr)
{
    *addr = Hash(key);              /* 求散列地址 */
    while (H.elem[*addr] != key)    /* 如果不为空，则冲突 */
    {
        *addr = (*addr + 1) % m;    /* 开放定址法的线性探测 */
        if (H.elem[*addr] == NULLKEY || *addr == Hash(key)) /* 如果循环回到原点 */
            return UNSUCCESS;       /* 则说明关键字不存在 */
    }
    return SUCCESS;
}

测试程序如下：

int main()
{
    int arr[HASHSIZE] = { 12,67,56,16,25,37,22,29,15,47,48,34 };
    HashTable H;

    InitHashTable(&H);
    for (int i = 0; i < m; i++)
        InsertHash(&H, arr[i]);

    int p = 0,key = 39;
    int result = SearchHash(H, key, &p);
    if (result)
        printf("查找 %d 的地址为：%d \n", key, p);
    else
        printf("查找 %d 失败。\n", key);

    for (int i = 0; i < m; i++)
    {
        key = arr[i];
        SearchHash(H, key, &p);
        printf("查找 %d 的地址为：%d \n", key, p);
    }

    return 0;
}
//运行结果如下：
//查找 39 失败。
//查找 12 的地址为：0
//查找 67 的地址为：7
//查找 56 的地址为：8
//查找 16 的地址为：4
//查找 25 的地址为：1
//查找 37 的地址为：2
//查找 22 的地址为：10
//查找 29 的地址为：5
//查找 15 的地址为：3
//查找 47 的地址为：11
//查找 48 的地址为：6
//查找 34 的地址为：9

散列函数的构造方法是很多种的，并且处理散列冲突的方法也有好多种。在上述测试程序中，我们在根据哈希函数和处理散列冲突的公式求关键字34的存储位置的时候，hash(34) = 10，与22这个关键字的地址冲突，然后不断根据散列冲突公式（开放定址法的线性探测）求得存储位置分别为11，0，1，2，3，4，5，6，7，8然后发现存储位置上已经有关键字了，最后9这个位置没有元素存储到9号位置中。34与37等关键字不是同义词却争夺1号地址，显然出现堆积现象。显然这样不断求得余数得到存储位置效率很低，所以我们可以改进处理散列冲突的方法改用开放定址法的二次线性探测法。这样当发现11号位置已有关键字，然后求解下一存储位置为9，发现没有关键字就存储进去。

散列表查找性能分析：
假设散列表中没有冲突的话，那么散列表查找算法将会比其他查找算法要高，因为它的时间复杂度达到了O(1)。但是实际情况中 冲突是不可避免的。那么散列表的平均查找长度取决于哪些因素呢？

1.散列函数是否均匀
2.处理冲突的方法
3.散列表的装填因子
装填因子a= 填入表中的记录个数除以散列表长度。a表示散列表的填满程度。填入表中的记录越多，a越大产生冲突的可能性就越高。通常来说，我们都是将散列表的空间设置的比查找集合大，这牺牲空间换取时间。

5.STL中hashtable结构概述

STL中的容器unordered_set,unordered_multiset,unordered_map,unorded_multimap的底部实现都可以看到hashtable的影子。其结构如下图：

hashtable底部结构.png