愿你坚持不懈,努力进步,进阶成自己理想的人

—— 2017.09, 写给3年后的自己

散列表(Hash表)总结

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
注意:3625这种散列值不一致,却产生冲突的情况,称为堆积
引申:

  • 如果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;
    }
};