c语言中哈希表的示例分析
这篇文章将为大家详细讲解有关c语言中哈希表的示例分析，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。
一、哈希表的概念
1、查找算法
当我们在一个 链表 或者 顺序表 中 查找 一个数据元素 是否存在 的时候，唯一的方法就是遍历整个表，这种方法称为 线性枚举。
如果这时候，顺序表是有序的情况下，我们可以采用折半的方式去查找，这种方法称为 二分枚举。
线性枚举 的时间复杂度为 O ( n ) O(n) O(n)。二分枚举 的时间复杂度为 O(log2n)。是否存在更快速的查找方式呢？这就是本要介绍的一种新的数据结构 -- 哈希表。
2、哈希表
由于它不是顺序结构，所以很多数据结构书上称之为 散列表，下文会统一采用 哈希表 的形式来说明，作为读者，只需要知道这两者是同一种数据结构即可。
我们把需要查找的数据，通过一个 函数映射，找到 存储数据的位置 的过程称为 哈希。这里涉及到几个概念：
a）需要 查找的数据 本身被称为 关键字；
b）通过 函数映射 将 关键字 变成一个 哈希值 的过程中，这里的 函数 被称为 哈希函数；
c）生成 哈希值 的过程过程可能产生冲突，需要进行 冲突解决；
d）解决完冲突以后，实际 存储数据的位置 被称为 哈希地址，通俗的说，它就是一个数组下标；
e）存储所有这些数据的数据结构就是 哈希表，程序实现上一般采用数组实现，所以又叫 哈希数组。整个过程如下图所示：
3、哈希数组
为了方便下标索引，哈希表 的底层实现结构是一个数组，数组类型可以是任意类型，每个位置被称为一个槽。如下图所示，它代表的是一个长度为 8 的 哈希表，又叫 哈希数组。
4、关键字
关键字 是哈希数组中的元素，可以是任意类型的，它可以是整型、浮点型、字符型、字符串，甚至是结构体或者类。如下的 A、C、M 都可以是关键字；
int A = 5;char C[100] = "Hello World!";struct Obj { };Obj M; 哈希表的实现过程中，我们需要通过一些手段，将一个非整型的 关键字 转换成 数组下标，也就是 哈希值，从而通过O(1) 的时间快速索引到它所对应的位置。
而将一个非整型的 关键字 转换成 整型 的手段就是 哈希函数。
5、哈希函数
哈希函数可以简单的理解为就是小学课本上那个函数，即
y = f ( x )
，这里的 f(x) 就是哈希函数，x是关键字，y是哈希值。好的哈希函数应该具备以下两个特质：
a）单射；
b）雪崩效应：输入值x的 1比特的变化，能够造成输出值y至少一半比特的变化；
单射很容易理解，图 ( a ) (a) (a) 中已知哈希值 y 时，键 x 可能有两种情况，不是一个单射；而图 (b) 中已知哈希值 y时，键 x 一定是唯一确定的，所以它是单射。由于 x 和 y 一一对应，这样就从本原上减少了冲突。
雪崩效应是为了让哈希值更加符合随机分布的原则，哈希表中的键分布的越随机，利用率越高，效率也越高。
常用的哈希函数有：直接定址法、除留余数法、数字分析法、平方取中法、折叠法、随机数法 等等。有关哈希函数的内容，下文会进行详细讲解。
6、哈希冲突
哈希函数在生成 哈希值 的过程中，如果产生 不同的关键字得到相同的哈希值 的情况，就被称为 哈希冲突。
即对于哈希函数y=f(x)，当关键字 x1≠x2 ，但是却有f(x1)=f(x2)，这时候，我们需要进行冲突解决。
冲突解决方法有很多，主要有：开放定址法、再散列函数法、链地址法、公共溢出区法 等等。有关解决冲突的内容，下文会进行详细讲解。
7、哈希地址
哈希地址 就是一个 数组下标 ，即哈希数组的下标。通过下标获得数据，被称为 索引。通过数据获得下标，被称为 哈希。平时工作的时候，和同事交流时用到的一个词 反查 就是说的 哈希。
二、常用哈希函数
1、直接定址法
直接定址法 就是 关键字 本身就是 哈希值，表示成函数值就是
f(x)=x
例如，我们需要统计一个字符串中每个字符的出现次数，就可以通过这种方法。任何一个字符的范围都是 [0,255]，所以只要用一个长度为 256 的哈希数组就可以存储每个字符对应的出现次数，利用一次遍历枚举就可以解决这个问题。C代码实现如下：
int i, hash[256];for(i = 0; str[i]; ++i) { ++hash[ str[i] ];} 这个就是最基础的直接定址法的实现。hash[c]代表字符c在这个字符串str中的出现次数。
2、平方取中法
平方取中法 就是对 关键字 进行平方，再取中间的某几位作为 哈希值。
例如，对于关键字 1314，得到平方为1726596，取中间三位作为哈希值，即265。
平方取中法 比较适用于 不清楚关键字的分布，且位数也不是很大 的情况。
3、折叠法
折叠法 是将关键字分割成位数相等的几部分（注意最后一部分位数不够可以短一些），然后再进行求和，得到一个 哈希值。
例如，对于关键字 5201314，将它分为四组，并且相加得到：52+01+31+4=88，这就是哈希值。
折叠法 比较适用于 不清楚关键字的分布，但是关键字位数较多 的情况。
4、除留余数法
除留余数法 就是 关键字 模上 哈希表 长度，表示成函数值就是
f(x)=x mod m
其中 m 代表了哈希表的长度，这种方法，不仅可以对关键字直接取模，也可以在 平方取中法、折叠法 之后再取模。
例如，对于一个长度为 4 的哈希数组，我们可以将关键字 模 4 得到哈希值，如图所示：
5、位与法
哈希数组的长度一般选择 2 的幂，因为我们知道取模运算是比较耗时的，而位运算相对较为高效。
选择 2 的幂作为数组长度，可以将 取模运算 转换成 二进制位与。
令 m = 2^k，那么它的二进制表示就是：
，任何一个数模上 m，就相当于取了 m 的二进制低 k 位，而
，所以和 位与m−1 的效果是一样的。即：
除了直接定址法，其它三种方法都有可能导致哈希冲突，接下来，我们就来讨论下常用的一些哈希冲突的解决方案。
三、常见哈希冲突解决方案
1、开放定址法
1）原理讲解
开放定址法 就是一旦发生冲突，就去寻找下一个空的地址，只要哈希表足够大，总能找到一个空的位置，并且记录下来作为它的 哈希地址。公式如下：
这里的di 是一个数列，可以是常数列(1,1,1,...,1)，也可以是等差数列(1,2,3,...,m−1)。
2）动画演示
上图中，采用的是哈希函数算法是 除留余数法，采用的哈希冲突解决方案是 开放定址法，哈希表的每个数据就是一个关键字，插入之前需要先进行查找，如果找到的位置未被插入，则执行插入；否则，找到下一个未被插入的位置进行插入；总共插入了 6 个数据，分别为：11、12、13、20、19、28。
这种方法需要注意的是，当插入数据超过哈希表长度时，不能再执行插入。
本文在第四章讲解 哈希表的现实 时采用的就是常数列的开放定址法。
2、再散列函数法
1）原理讲解
再散列函数法 就是一旦发生冲突，就采用另一个哈希函数，可以是 平方取中法、折叠法、除留余数法 等等的组合，一般用两个哈希函数，产生冲突的概率已经微乎其微了。
再散列函数法 能够使关键字不产生聚集，当然，也会增加不少哈希函数的计算时间。
2）动画演示
待补充
3、链地址法
1）原理讲解
当然，产生冲突后，我们也可以选择不换位置，还是在原来的位置，只是把 哈希值 相同的用链表串联起来。这种方法被称为 链地址法。
2）动画演示
上图中，采用的是哈希函数算法是 除留余数法，采用的哈希冲突解决方案是 链地址法，哈希表的每个数据保留了一个 链表头结点 和 尾结点，插入之前需要先进行查找，如果找到的位置，链表非空，则插入尾结点并且更新尾结点；否则，生成一个新的链表头结点和尾结点；总共插入了 6 个数据，分别为：11、12、13、20、19、28。
4、公共溢出区法
1）原理讲解
一旦产生冲突的数据，统一放到另外一个顺序表中，每次查找数据，在哈希数组中到的关键字和给定关键字相等，则认为查找成功；否则，就去公共溢出区顺序查找，这种方法被称为 公共溢出区法。
这种方法适合冲突较少的情况。
2）动画演示
待补充
四、哈希表的实现
1、数据结构定义
由于哈希表的底层存储还是数组，所以我们可以定义一个结构体，结构体中定义一个数组类型的成员，如果需要记录哈希表元素的个数，还可以记录一个 size字段。
C语言实现如下：
#define maxn (1<<17) // (1)#define mask (maxn-1) // (2)#define DataType int // (3)#define Boolean int // (4)#define NULLKEY (maxn+2) // (5)typedef struct { DataType data[maxn];}HashTable;(1) 利用位运算计算哈希函数进行加速，哈希表的长度为 2 的幂；
(2) 利用上文提到的 位与法 作为哈希函数，进行位与的掩码必须是二进制表示都是1的，所以等于 2 的幂减一；
(3) 定义关键字类型为整型int；
(4) 定义一个布尔变量类型；
(5) NULLKEY作为哈希表对应位置为空时的标记，必须是一个非关键字能取到的值；
2、哈希表初始化
哈希表初始化要做的事情，就是把哈希表的每个位置都置空。C语言代码实现如下：
void HashInit(HashTable *ht) { int i; for(i = 0; i < maxn; ++i) { ht->data[i] = NULLKEY; // (1) }}(1) 将哈希表的每个位置都置空；
3、哈希函数计算
哈希函数计算采用 除留余数法 的优化版本 位与法。C语言代码实现如下：
int HashGetAddr(DataType key) { return key & mask;}4、哈希表查找
查找需要采用和插入时相同的哈希冲突方案，即开放寻址法。C语言代码实现如下：
Boolean HashSearchKey(HashTable *ht, DataType key, int *addr) { int startaddr = HashGetAddr(key); // (1) *addr = startaddr; // (2) while(ht->data[*addr] != key) { // (3) *addr = HashGetAddr(*addr + 1); // (4) if(ht->data[*addr] == NULLKEY) // (5) return 0; if(*addr == startaddr) // (6) return 0; } return 1; // (7)}(1) 根据 哈希函数HashGetAddr计算得到一个哈希值startaddr；
(2) addr是需要作为返回值的，所以要用解引用；
(3) 在哈希表的addr对应查找，如果不是空位，则继续(4)；否则，跳出循环；
(4) 往后找一个位置；
(5) 如果发现一个空位，说明这个关键字在哈希表中没有对应数据，直接返回 0，代表查找失败；
(6) 代表整个 哈希表 都已经遍历完毕，都没有找到合适的关键字，直接返回 0，代表查找失败；
(7) 否则，返回 1 代表查找成功；
5、哈希表插入
哈希冲突时（即当没有合适位置），就找下一相邻位置，即寻址数列为常数列 (1,1,1,...,1)。插入需要注意当哈希表慢时，不能再执行插入操作。C语言代码实现如下：
int HashInsert(HashTable *ht, DataType key) { int addr = HashGetAddr(key); // (1) int retaddr; if ( HashSearchKey(ht, key, &retaddr ) ) { // (2) return retaddr; } while(ht->data[addr] != NULLKEY) // (3) addr = HashGetAddr(addr + 1); // (4) ht->data[addr] = key; // (5) return addr; // (6)}(1) 根据 哈希函数HashGetAddr计算得到一个哈希值addr；
(2) 插入前需要先查找是否存在，如果已经存在，则不执行插入；
(3) 在哈希表的addr对应查找，如果不是空位，则继续 (3)；否则，跳出循环；
(4) 往后找一个位置，继续判断是否为空；
(5) 跳出循环则代表当前哈希表的addr位置没有其它元素占据，则可以作为当前key的位置进行插入；
(6) 返回addr作为key的哈希地址；
6、哈希表删除
有了查找的基础，删除操作就比较简单了，如果不能找到一个关键字的位置，则不对哈希表进行任何操作，返回空关键字；否则，将找到的位置赋为空关键字，并且返回删除的位置；
int HashRemove(HashTable *ht, DataType key) { int addr; if ( !HashSearchKey(ht, key, &addr ) ) { // (1) return NULLKEY; } ht->data[addr] = NULLKEY; // (2) return addr;}(1) 首先执行查找；
(2) 对找到的位置，将找到位置关键字清空；
7、哈希表完整实现
最后，给出一个 开放定址法 的哈希表的完整实现，如下：
/******************** 哈希表 开放定址法 ********************/#define maxn (1<<17)#define mask (maxn-1)#define DataType int#define Boolean int#define NULLKEY (1<<30)typedef struct { DataType data[maxn];}HashTable;void HashInit(HashTable *ht) { int i; for(i = 0; i < maxn; ++i) { ht->data[i] = NULLKEY; }}int HashGetAddr(DataType key) { return key & mask; }Boolean HashSearchKey(HashTable *ht, DataType key, int *addr) { int startaddr = HashGetAddr(key); *addr = startaddr; while(ht->data[*addr] != key) { *addr = HashGetAddr(*addr + 1); if(ht->data[*addr] == NULLKEY) { return 0; } if(*addr == startaddr) { return 0; } } return 1;}int HashInsert(HashTable *ht, DataType key) { int addr = HashGetAddr(key); int retaddr; if ( HashSearchKey(ht, key, &retaddr ) ) { return retaddr; } while(ht->data[addr] != NULLKEY) addr = HashGetAddr(addr + 1); ht->data[addr] = key; return addr;}int HashRemove(HashTable *ht, DataType key) { int addr; if ( !HashSearchKey(ht, key, &addr ) ) { return NULLKEY; } ht->data[addr] = NULLKEY; return addr;}/******************** 哈希表 开放定址法 ********************/关于"c语言中哈希表的示例分析"这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。
