Hash表是一种十分高效的、可用于查找的数据结构,它既是一种存储方法,也是一种查找方法。一个设计良好的Hash表,可以实现在平均O(1)的实际内查找数据。但是Hash表主要适用于
=
和!=
的情况,对于范围比较、排序的情况下,并不适用
一、Hash表的主要概念
- 散列函数:用于计算存储位置的函数,建立起关键字和存储位置之间的映射,实现
存储位置 = f(关键字)
- 冲突:关键字
key1 != key2
,但是f(key1) == f(key2)
的情况,成为冲突 - 同义词:冲突情况下,key1和key2是同义词
- 装填因子:
装填因子α = 填入表中的记录个数 / 散列表长度
,α越大,产生冲突的可能性就越大。散列表的平均查找长度取决于装填因子,而非集合中的记录个数
二、散列函数的构造方法
散列函数是实现Hash表的核心,一个好的散列函数,可以尽最大可能地避免冲突。设计散列函数的原则:
- 计算简单: 散列函数应该尽可能计算简单,避免出现散列函数计算时间比其他查找方式还长的情况,否则散列技术就没有意义了
- 散列地址分布均匀: 分布均匀可以尽可能避免出现冲突,冲突越少,Hash表的性能越高
常用的散列函数构造法:
1、直接定址法
直接定址法,就是取关键字的某个线性函数值作为散列地址,即:f(key) = a*key+b
,这种情况下的产生的散列地址不会发生冲突,但是需要我们预先知道关键字的分布状况。比较适合查找表较小且连续的情况。如我们需要统计0~100岁
年龄的人口分布,就可以采用直接定址法
,用年龄直接作为散列地址,即:
int getHash(int age) {
return age;
}
2、数字分析法
根据关键字的分布情况,采用数值反转、环位移、数字叠加等方式,来得到散列函数。如福州大学有一批联通卡的手机号码均是1310760
开头的,那么我们就可以选取最后4位作为散列地址。如:
int getHash(string tel) {
return (tel[7]-'0')*1000+
(tel[8]-'0')*100+
(tel[9]-'0')*10+
(tel[10]-'0');
}
3、平方取中法
对关键词进行平方,然后再截取其中几位,如99
的平方为9801,截中间两位,得80为散列地址
4、折叠法
对关键字分为多部分,叠加求和。如:12345678,3位3位叠加,如:123
456
78
,相加得657
,可以根据散列表的表长,取其中几位作为散列地址
5、除留余数法
f(key) = key % p (p <= 表长)
确定常数p的经验:p选择离表长最接近的最大质数(如表长为100,可以选择97),或者是不包含小于20质因子的合数
三、处理冲突的方法
再好的散列函数,也难以完全避免出现冲突的情况。这种情况下,就需要有处理散列冲突的方法
1、开放定址法
该方法的思想为:一旦出现了冲突,就继续寻找下一个为空的散列地址。即:
f(key) = ( f(key) + d ) % 表长
,如对于一组数据{12, 36, 25},表长为3,则:
- f(12) = 0
- f(36) = 0,冲突,使用开放地址法,得到f(36) = ( 0 + 1 ) % 3 = 1
- f(25) = 1,冲突,使用开放定址法,得到f(25) = ( 1 + 1 ) % 3 = 2
如此一来,得到的散列表为:
[ 0 ] 12
[ 1 ] 36
[ 2 ] 25
注意: 像36
和25
这种散列值不一致,却产生冲突的情况,称为堆积
引申:
- 如果d取
1的平方
,1的平方的负数
,2的平方
,2的平方的负数
,...,q的平方
,q的平方的负数
,这种情况下,称为二次探测法
- d也可以取一个随机数(但是这种情况下需要保存随机种子),这种情况成为`随机探测法
2、再散列函数法
再散列函数法就是,使用一组散列函数备用。当其中一个散列函数算出的散列地址发生了冲突,就选用下一个散列函数来算出新的散列地址。
3、链地址法
链地址法使用到了链表
这一数据结构,可以不需要冲突换址,核心在于对于同义词就存在同一个链表中。缺点是会带来链表查找的消耗。但是如果平均链表表长很小,那么平均情况下,性能还是很好的。如:
{12, 36, 25}这组数据,存储后如下:
[ 0 ] ===> [12]->[36]->NULL
[ 1 ] ===> [25]->NULL
[ 2 ] ===> NULL
每当有新的冲突产生,只要往相应的链表末尾加入数据即可
4、公共溢出区法
此种方法使用两个区域来存储Hash表,对于第一次计算出来的Hash地址,放于基本表
中,对于产生冲突的关键字,放在溢出表
中,如果基本表中没有找到数据,则到溢出表进行顺序查找。如
{12, 36, 25, 26}可以存储如:
基本表:
[ 0 ] 12
[ 1 ] 25
[ 2 ] 26
溢出表:
[ 0 ] 36
[ 1 ] NULL
[ 2 ] NULL
散列表实现
以下以开放定址法为基础,来实现一个Hash表
#define NULLKEY 0x11111111
class HashTable {
private:
int m; // 表长
int *table; // 表空间
public:
HashTable(int _m): m(_m) {
this->table = new int[_m];
for(int i=0; i<m; ++i) {
this->table[i] = NULLKEY;
}
}
int getHash(int key) {
return key % this->m;
}
void insert(int key) {
int hash = this->getHash(key);
while(this->table[hash] != NULLKEY) {
hash = (hash + 1) % this->m;
}
this->table[hash] = key;
}
bool has(int key) {
int hash = this->getHash(key);
while(this->table[hash] != key) {
hash = (hash + 1) % this->m;
if( this->table[hash] == NULLKEY || this->table[hash] == this->getHash(key) ) {
return false;
}
}
return true;
}
};