散列表（哈希表）

散列表

• 散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f（key）。查找时，根据这个确定的对应关系找到给定值key的映射f(key),若查找集合中存在这个记录，则必定在f(key)的位置上。

• 这里我们把这种对应关系f称为散列函数，又称为哈希（Hash）函数。按这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表或者哈希表（Hash table）。关键字对应的记录存储位置称为散列地址。

• 散列过程步骤：
  1.在存储时，通过散列函数计算记录的散列地址，并按照此散列地址存储该记录。
  2.查找记录时，通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录。

• 散列技术既是一种存储方法，也是一种查找方法。与线性表、树等结构不同的是，数据元素之间不存在逻辑关系，只与关键字有关，因此散列主要是面向查找的存储结构。

• 散列技术最适合的求解问题是查找与给定值相等的记录。但是不具备很多常规数据结构的能力，比如那种同样的关键字可能对应很多记录的情况，不适合用散列技术，同样也不适合范围查找。

散列函数

• 理想情况下，每个关键字通过散列函数计算出来的地址是不一样的，然而存在当key1不等于key2时，但是有f(key1)=f(key2),这种现象称为冲突（collision），并把key1和key2称为这个散列函数的同义词（synonym）。这个冲突不能完全避免，故需要进行处理。
• 散列函数的构造原则：
  1.计算简单
  2.散列地址分布均匀
• 常用的散列函数构造方法：
  1.直接定址法：即f(key)=key,也可以取关键字的某个线性函数值为散列地址，即f(key)=a x key+b（a,b为常数）。这样的散列函数优点是简单、均匀，也不会产生冲突，但问题是这需要事先知道关键字的分布情况，适合查找表较小且连续的情况。故在现实应用中，虽然简单，但不常用。
  2.数字分析法：抽取关键字中的一部分来计算散列存储位置。通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布比较均匀，可以考虑用这个方法。
  3.平方取中法：对关键字平方后取中间的几位作为散列地址。
  4.折叠法：关键字从左到右分割成位数相等的几部分（最后一部分位数不够可以短些），然后将这几部分叠加求和，按照散列表表长取后几位作为散列地址。不需要事先知道关键字的分布，适合关键字位数较多的情况。
  5.除留余数法：最常用的构造散列函数的方法，对于散列表长为m的散列函数公式为：f(key)=key mod (p<=m),mod是取模（求余数）的意思。事实上，这种方法也可以在折叠后、平方取中后取模。通常p为小于或等于表长（接近m）的最小质数或不包含小于20质因子的合数。
  6.随机数法：取关键字的随机函数值作为它的散列地址。即f(key)=random(key)。
  总之，应该视不同的情况采用不同的散列函数，综合考虑以下因素，决定选择哪种散列函数更为合适。
  1.计算散列地址所需时间
  2.关键字的长度
  3.散列表的大小
  4.关键字的分布情况
  5.记录查找的频率。

处理散列冲突

• 开放定址法：即如果发生了冲突，寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。公式为：fi(key)=(f(key)+di) MOD m (di=1,2,3,……,m-1),把这种解决冲突的开放定址法称为线性探测法。
  在解决冲突的时候， 我们还会碰到本来不是同义词，但是却要争夺一个地址的情况，称这种现象为堆积。显然，堆积的出现使得我们需要不断处理冲突，无论是存入还是查找，效率都会大大降低。
  为了不让关键字都聚集在一块区域，可以增加平方运算，即di=12,-12,22,-22,……,q2,-q2,(q<=m/2),这样就可以双向寻找可能的空位置，称这种方法为二次探测法。即fi(key)=(f(key)+di) MOD m (di=12,-12,22,-22,……,q2,-q2,q<=m/2)。
  还有一种方法，在冲突时，对于位移量di采用随机函数计算得到，称为随机探测法。即fi(key)=(f(key)+di) MOD m (di是一个随机数列)。
  开放定址法只要在散列表未填满时，总能找到不发生冲突的地址，是常用的方法。
• 再散列函数法：可以事先准备多个散列函数fi(key)=Rhi(key) (i=1,2,……,k)，RHi为不同的散列函数，如除留余数、折叠等，每当发生散列地址冲突时，就换一个散列函数计算，总有一个可以把冲突解决掉。这种方法使得关键字不产生聚集，当然，相应地增加了计算时间。
• 链地址法：当然，发生冲突也不一定要换地方，在原地直接解决。将所有关键字为同义词的记录存储在一个单链表中，称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。对于可能会造成很多冲突的散列函数来说，该方法提供了绝不会出现找不到地址的保障，但是也带来了查找时需要遍历单链表的性能损耗。
• 公共溢出区法：即给所有冲突的关键字建立一个公共的溢出区来存放。在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行对比，如果相等，则查找成功；如果不相等，则到溢出表进行顺序查找。如果对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。

代码示例

Hash.h

#pragma once

#define HASHSIZE 12         //定义散列表长为数组的长度
#define NULLKEY -32768

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

//初始化散列表
bool InitHashTable(HashTable& H);

//散列函数
int Hash(int key);

//插入关键字到散列表
void InsertHash(HashTable& H, int key);

//散列表查找关键字
bool SearchHash(HashTable H, int key, int* addr);

Hash.cpp

#include "Hash.h"

//初始化散列表
bool InitHashTable(HashTable& H)
{
    H.elem = new int[HASHSIZE];
    H.count = HASHSIZE;
    for (int i = 0; i < H.count; i++)
    {
        H.elem[i] = NULLKEY;
    }
    return true;
}

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

//插入关键字到散列表
void InsertHash(HashTable& H, int key)
{
    int addr = Hash(key);           //求散列地址

    while (H.elem[addr] != NULLKEY) //开放定址法的线性探测
    {
        addr = (addr + 1) % H.count;
    }

    H.elem[addr] = key;
}

//散列表查找关键字
bool SearchHash(HashTable H, int key, int* addr)
{
    *addr = Hash(key);
    while (H.elem[*addr] != key)
    {
        *addr = (*addr + 1) % H.count;

        if (H.elem[*addr] == NULLKEY || *addr == Hash(key))
        {
            //如果循环到原点，说明关键字不存在
            return false;

        }
    }

    return true;
}

main.cpp

#include "Hash.h"

#include <iostream>

using namespace std;

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

    HashTable H;
    if (InitHashTable(H))
    {
        cout << "初始化成功" << endl;
    }
    else
    {
        cout << "初始化失败" << endl;
    }

    for (int i = 0; i < H.count; i++)
    {
        InsertHash(H, arr[i]);
    }

    int key = 34;
    int addr = 0;
    if (SearchHash(H, key, &addr))
    {
        cout << "找到了，addr=" << addr << endl;
    }
    else
    {
        cout << "未找到" << endl;
    }

    for (int i = 0; i < H.count; i++)
    {
        SearchHash(H, arr[i], &addr);
        cout << arr[i] << ":" << addr << endl;
    }
    cout << endl;

    return 0;
}