散列表（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
注意： 像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;
    }
};