数据结构之哈希表（HASH）
前⾔
当我们在编程过程中，往往需要对线性表进⾏查操作。在顺序表中查时，需要从表头开始，依次遍历⽐较a[i]与key的值是否相等，直到相等才返回索引i；在有序表中查时，我们经常使⽤的是⼆分查，通过⽐较key与a[i]的⼤⼩来折半查，直到相等时才返回索引i。最终通过索引到我们要的元素。
但是，这两种⽅法的效率都依赖于查中⽐较的次数。我们有⼀种想法，能不能不经过⽐较，⽽是直接通过关键字key⼀次得到所要的结果呢？这时，就有了散列表查（哈希表）。 1、什么是哈希表
要说哈希表，我们必须先了解⼀种新的存储⽅式—散列技术。
散列技术是指在记录的存储位置和它的关键字之间建⽴⼀个确定的对应关系f，使每⼀个关键字都对应⼀个存储位置。即：存储位置=f（关键字）。这样，在查的过程中，只需要通过这个对应关系f 到给定值key的映射f（key）。只要集合中存在关键字和key相等的记录，则必在存储位置f（key）处。我们把这种对应关系f 称为散列函数或哈希函数。 按照这个思想，采⽤散列技术将记录存储在⼀块连续的存储空间中，这块连续的存储空间称为哈希表。所得的存储地址称为哈希地址或散列地址。 2、哈希表查步骤
①、存储数据时，将数据存⼊通过哈希函数计算所得哪那个地址⾥⾯。
②、查时，使⽤同⼀个哈希函数通过关键字key计算出存储地址，通过该地址即可访问到查的记录。
在理想的情况下，每⼀个 关键字，通过哈希函数计算出来的地址都是不⼀样的。但是在实际情况中，我们常常会碰到两个关键字
key1≠key2，但是f(key1) = f(key2), 这种现象称为冲突，并把key1和key2称为这个散列函数的同义词。
冲突的出现会造成查上的错误，具体解决⽅法会在后⽂提到。
4、哈希函数的构造⽅法
（1）、原则
①、计算简单；
②、散列地址分布均匀。
（2）、构造⽅法
①、直接定址法：不常⽤
取关键字或关键字的某个线性函数值为哈希地址：
即：Ｈ(key) = key 或 H(key) = a*key+b
优点：简单，均匀，不会产⽣冲突；
缺点：需要实现直到关键字的分布情况，适合查表⽐较⼩且连续的情况。
②、数字分析法
数字分析法⽤于处理关键字是位数⽐较多的数字，通过抽取关键字的⼀部分进⾏操作，计算哈希存储位置的⽅法。
例如：关键字是⼿机号时，众所周知，我们的１１位⼿机号中，前三位是接⼊号，⼀般对应不同运营商的⼦品牌；中间四位是ＨＬＲ识别号，表⽰⽤户号的归属地；最后四位才是真正的⽤户号，所以我们可以选择后四位成为哈希地址，对其在进⾏相应操作来减少冲突。 数字分析法适合处理关键字位数⽐较⼤的情况，事先知道关键字的分布且关键字的若⼲位分布均匀。
③、平⽅取中法
具体⽅法很简单：先对关键字取平⽅，然后选取中间⼏位为哈希地址；取的位数由表长决定，适⽤于不知道关键字的分布，⽽位数⼜不是很⼤的情况。
④、折叠法
将关键字分成位数相同的⼏部分（最后⼀部分位数 可以不同），然后求这⼏部分的叠加和（舍去进位），并按照散列表的表长，取后⼏位作为哈希地址。平顶山棉纺厂
适⽤于关键字位数很多，⽽且关键字每⼀位上数字分布⼤致均匀。
⑤、除留余数法
此⽅法为最常⽤的构造哈希函数⽅法。对于哈希表长为m的哈希函数公式为：
f(key) = key mod p (p <= m)
此⽅法不仅可以对关键字直接取模，也可以在折叠、平⽅取中之后再取模。
所以，本⽅法的关键在于选择合适的p，若是p选择的不好，就可能产⽣ 同义词；根据前⼈经验，若散列表的表长为m，通常p为⼩于或等于表长（最好接近m）的最⼩质数或不包含⼩于20质因⼦的合数。
⑥、随机数法
选择⼀个随机数，取关键字的随机函数值作为他的哈希地址。
即：f(key) = random (key)
当关键字的长度不等时，采⽤这个⽅法构造哈希函数较为合适。当遇到特殊字符的关键字时，需要将其转换为某种数字。
（3）、参考因素
在实际应⽤过程中，应该视不同的情况采⽤不同的哈希函数。下列是⼀些参考因素：
①计算哈希地址所需的时间；
②关键字的长度；
③哈希表的⼤⼩；
④关键字的分布情况；
⑤查的频率。
选择哈希函数时，我们应该综合以上因素，选择合适的构建哈希函数的⽅法。
５、哈希冲突的解决
前⽂提到，哈希冲突不能避免，所以我们需要到⽅法来解决它。
哈希冲突的解决⽅案主要有四种：开放地址法；再哈希；链地址法；公共溢出区法。
（1）、开放地址法
开放地址法就是指：⼀旦发⽣了冲突就去寻下⼀个空的哈希地址，只要哈希表⾜够⼤，空的散列地址总能到，并将记录存⼊。为什么自然界中少有绿的花
公式：Hi=(H(*key) + Di) mod m (i = 1,2,3,….,k k<=m-1)
其中：H（key）为哈希函数；m为哈希表表长；Di为增量序列，有以下3中取法:
①Di = 1,2,3,…,m-1, 称为线性探测再散列；
②Di = 1²，－１²，２²，－２²，。。。，±ｋ²，（ｋ<= m/2)称为⼆次探测再散列
③Di = 伪随机数序列，称为伪随机数探测再散列。
例如：在长度为12的哈希表中插⼊关键字为38的记录：
从上述线性探测再散列的过程中可以看出⼀个现象：当表中i、i+1位置上有记录时，下⼀个哈希地址为i、i+1、i+2的记录都将填⼊i+3的位置，这种本不是同义词却要争夺同⼀个地址的现象叫“堆积“。即在处理同义词的冲突过程中⼜添加了⾮同义词的冲突；但是，⽤线探测再散列处理冲突可以保证：只要哈希表未填满，总能到⼀个不发⽣冲突的地⽅。
（2）、再哈希法
公式：Hi = RHi（key） i = 1，2，…，k
RHi均是不同的哈希函数，意思为：当繁盛冲突时，使⽤不同的哈希函数计算地址，直到不冲突为⽌。这种⽅法不易产⽣堆积，但是耗费时间。
（3）、链地址法
将所有关键字为同义字的记录存储在⼀个单链表中，我们称这种单链表为同义词⼦表，散列表中存储同义词⼦表的头指针。
安阳市三官庙小学 如关键字集合为{19，14，23，01，68，20，84，27，55，11，10，79}，按哈希函数H（key） = key mod 13；
链地址法解决了冲突，提供了永远都能到地址的保证。但是，也带来了查时需要遍历单链表的性能损耗。
（4）、公共溢出区法
即设⽴两个表：基础表和溢出表。将所有关键字通过哈希函数计算出相应的地址。然后将未发⽣冲突的关键字放⼊相应的基础表中，⼀旦发⽣冲突，就将其依次放⼊溢出表中即可。
在查时，先⽤给定值通过哈希函数计算出相应的散列地址后，⾸先 ⾸先与基本表的相应位置进⾏⽐较，如果不相等，再到溢出表中顺序查。
6、哈希表查算法的实现
⾸先定义⼀个散列表的结构以及⼀些相关的常数。其中，HashTables是散列表结构。结构当中的elem为⼀个动态数组。
#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12 /*定义哈希表长为数组的长度*/
#define NULLKEY -32768
{
int *elem; /*数组元素存储基址，动态分配数组*/
int count; /*当前数据元素的个数*/
}HashTable;
int m = 0;
初始化哈希表
/*初始化哈希表*/
Status InitHashTable(HashTable *H)
{
int i;
m = HASHSIZE;
H->count = m;
H->elem = (int *)malloc(m*sizeof(int));
for(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;
}
7、总结
１、哈希表就是⼀种以键值对存储数据的结构。
2、哈希表是⼀个在空间和时间上做出权衡的经典例⼦。如果没有内存限制，那么可以
直接将键作为数组的索引。那么所查的时间复杂度为Ｏ(1)；如果没有时间限制，那么我们可以使⽤⽆序数组并进⾏顺序查，这样只需要很少的内存。哈希表使⽤了适度的时间和空间来在这两个极端之间到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议