哈希表

散列表(Hashtable,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。这种方式不需要进行任何的比较,其查找的效率相较于前面所介绍的查找算法是更高的。
哈希技术的基本思想是通过由哈希函数决定的键值。(key)与哈希地址(H(x.key))之间的对应关系来实现存储组织和查找运算,哈希技术的核心是哈希函数。

Hashing Data Structure

这里有一个电话簿(查找表),电话簿中有 5个人的联系方式:
张三 13911879643
李四 13309876542
王五 13498456821
赵六 13546738294
孙七 13648391025

假如想查找王四的电话号码,对于一般的查找方式最先想到的是从头遍历,一一比较。而如果将电话簿构建成一张哈希表,可以直接通过名字“李四”直接找到电话号码在表中的位置。哈希函数为:每个名字的姓的首字母的 ASCII 值即为对应的电话号码的存储位置。

哈希冲突
张三和赵六两个关键字的姓的首字母都是 Z ,最终求出的电话号码的存储位置相同,这种现象称为冲突。
即:不同关键字通过哈希函数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

哈希函数设计原则:
引起哈希冲突的一个原因可能是:哈希函数设计不够合理。 所以哈希函数设计原则:
1、哈希函数的定义域必须包括需要存储的全部关键码
2、如果散列表允许有m个地址时,其值域必须在0到m-1之间
3、哈希函数计算出来的地址能均匀分布在整个空间中
4、哈希函数应该比较简单

哈希冲突的避免

通常用的处理冲突的方法有以下几种:
1、开放定址法
H(key)=(H(key)+ d)MOD m(其中 m 为哈希表的表长,d 为一个增量) 当得出的哈希地址产生冲突时,选取以下 3 种方法中的一种获取 d 的值,然后继续计算,直到计算出的哈希地址不在冲突为止,这 3 种方法为:
线性探测法:d=1,2,3,…,m-1
二次探测法:d=12,-12,22,-22,32,…
伪随机数探测法:d=伪随机数
2、再哈希法
当通过哈希函数求得的哈希地址同其他关键字产生冲突时,使用另一个哈希函数计算,直到冲突不再发生。
3、链地址法
将所有产生冲突的关键字所对应的数据全部存储在同一个线性链表中。

常见哈希函数

1、直接定制法–(常用)
取关键字的某个线性函数为散列地址:Hash(Key)=a*Key +b 优点:简单、均匀 缺点:需要事先知道关键字的分布情况 使用场景:适合查找比较小且连续的情况 面试题:字符串中第一个只出现一次字符。

2、除留余数法–(常用)
设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:
Hash(key) = key% p(p<=m),将关键码转换成哈希地址 。

3、平方取中法–(了解)
假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址; 再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况。

4、折叠法–(了解)
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况。

5、随机数法–(了解)
选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法。

6、数学分析法–(了解)
设有n个d位数,每一位可能有r种不同的符号,这r种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散列地址。
数字分析法通常适合处理关键字位数比较大的情况,如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突

Scroll to Top