程序员必读：教你如何摸清哈希表（hash）的脾气

1. 相关概念

在哈希表中，记录的存储位置 = f (关键字)，通过查找关键字的存储位置即可，不用进行比较。散列技术是在记录的存储位置和它的关键字之间建立一个明确的对应关系f 函数，使得每个关键字 key 对应一个存储位置 f(key) 且这个位置是唯一的。这里我们将这种对应关系 f 称为散列函数，又称为哈希(Hash)函数。采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表(Hash table)。

当存储记录时，通过散列函数计算出记录的散列地址；当查找记录时，我们通过同样的是散列函数计算记录的散列地址，并按此散列地址访问该记录。散列技术即使一种存储方法，也是一种查找方法；散列技术之间没有关系，只有关键字和函数之间有关系，所以散列技术是一种面向查找的存储技术

缺点是会存在关键字重复的问题，比如说男女为关键字的时候就不合适了。同样不适合查找范围的，比如说查找18-20岁之间的同学。散列表技术对于1对1的查找是适合的。

2. 构造散列函数

2.1 两个基本原则

“好的散列函数 = 计算简单 + 分布均匀”。其中计算简单指的是散列函数的计算时间不应该超过其他查找技术与关键字比较的时间，而分布均匀指的是散列地址分布均匀。

2.2 具体方法

2.2.1 直接定址法

即使用关键字本身作为函数值，即f(key) = key。假如有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。
如，下图所示

image

又假果现在要统计的是1980年以后出生的人口数，那么我们对出生年份这个关键字可以变换为：用年份减去1980的值来作为地址。即：f(key) = key – 1980

image

所以直接定值法是取关键字的某个线性函数值为散列地址，即 f(key) = a*key + b。其优点是简单、均匀，不会产生冲突；但缺点是需要知道关键字的分布情况，希望数值是连续的。

2.2.2 数字分析法

数字分析法通常适合处理关键字位数比较大的情况，例如我们现在要存储某家公司员工登记表，如果用手机号作为关键字，那么我们发现抽取后面的四位数字作为散列地址是不错的选择，如下图所示

image

2.2.3 平方取中法

平方取中法是将关键字平方之后取中间若干位数字作为散列地址。这种方法适用于不知道关键字的分布，且数值的位数又不是很大的情况。

2.2.4 折叠法

折叠法是将关键字从左到右分割成位数相等的几部分，然后将这几部分叠加求和，并按散列表表长取后几位作为散列地址。

2.2.5 除留余数法

此方法为最常用的构造散列函数方法，对于散列表长为m的散列函数计算公式为：

f(key) = key mod p(p<=m)

事实上，这个方法不仅可以对关键字直接取模，也可以通过折叠、平方取中后再取模。例如下表，我们对有12个记录的关键字构造散列表时，就可以用f(key) = key mod 12的方法。

image

p的选择是关键，如果对于这个表格的关键字，p还选择12的话，那得到的情况未免也太糟糕了：

image

p的选择很重要，如果我们把p改为11，那结果就另当别论啦：

image

当然在上述的这种情况中仍然是有冲突的情况，对于这种情况在后面中会介绍解决的方法。

2.2.6 随机数法

选择一个随机数，取关键字的随机函数值为它的散列地址。

f(key) = random(key)。

这里的random是随机函数，当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。

2.3 哈希表的选择

现实中，我们应该视不同的情况采用不同的散列函数，这里给大家一些参考方向：

(1) 计算散列地址所需的时间；

(2) 关键字的长度；

(3) 列表的大小；

(4) 关键字的分布情况；

(5) 记录查找的频率。

3. 处理散列冲突的方法

3.1 开放定址法

所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。它的公式是：

fi(key) = (f(key)+di) MOD m (di=1,2,…,m-1)

例：假设关键字集合为{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34},使用除留余数法(m=12)求散列表

image

也可以修改di的取值方式，例如使用平方运算来尽量解决堆积问题：

fi(key) = (f(key)+di) MOD m (di=1²,-1²,2²,-2²…,q²,-q²,q<=m/1)

还有一种方法是，在冲突时，对于位移量di采用随机函数计算得到，我们称之为随机探测法：

fi(key) = (f(key)+di) MOD m (di是由一个随机函数获得的数列)

3.2 再散列函数法

同时准备多个散列函数，当第一个散列函数发生冲突的时候可以用备选的散列函数进行计算。

3.3 链地址法

例：假设关键字集合为{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34},同样使用除留余数法求散列表，如下图所示

image

在上面个的链表中，如果没有发生冲突的话，元素后面的地址为空；如果有冲突的话就将他链接到下一个元素。

3.4 公共溢出区法

例：假设关键字集合为{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34},同样使用除留余数法求散列表，如下图所示

image

没有冲突的元素放在左边的表，有冲突的元素，将多余的元素放在右边的那个表。

4. 散列表查找的代码实现

在这里采用除留余数法构造散列函数，代码中还包括散列表的结构定义，散列表的初始化，插入关键字和查找关键字

#define HASHSIZE 12#define NULLKEY -32768// 定义一个散列表的结构typedef struct{    int *elem;  // 数据元素的基址，动态分配数组    int count;  // 当前数据元素的个数}HashTable;// 初始化散列表int InitHashTable(HashTable *H){    H->count = HASHSIZE;    H->elem = (int *)malloc(HASHSIZE * sizeof(int));    if( !H->elem )    {        return -1;      //申请空间失败    }    for( i=0; i < HASHSIZE; i++ )    {        H->elem[i] = NULLKEY;      //迭代进行初始化，其中的NULLKEY是一个默认值    }    return 0;}// 使用除留余数法int Hash(int key){    return key % HASHSIZE;        //除数一般小于等于表长}// 插入关键字到散列表void InsertHash(HashTable *H, int key){    int addr;    addr = Hash(key);     //只是得到一个偏移地址    while( H->elem[addr] != NULLKEY )   // 如果不为空，则冲突出现    {        addr = (addr + 1) % HASHSIZE;   // 开放定址法的线性探测    }    H->elem[addr] = key;}// 散列表查找关键字int SearchHash(HashTable H, int key, int *addr){    *addr = Hash(key);    while( H.elem[*addr] != key )    {        *addr = (*addr + 1) % HASHSIZE;        if( H.elem[*addr] == NULLKEY || *addr == Hash(key) )   //后面那个条件说明循环回到原点        {            return -1;        }    }    return 0;}

image.png