散列表HashTable

散列表，又叫哈希表（Hash Table），是能够通过给定的关键字的值直接访问到具体对应的值的一个数据结构。散列表的实现常常叫做散列(hashing)，散列是一种用于以常数平均时间执行插入、删除和查找的技术。也就是说，把关键字映射到一个表中的位置来直接访问记录，以加快访问速度。

通常，我们把这个关键字称为 Key，把对应的记录称为 Value，所以也可以说是通过 Key 访问一个映射表来得到 Value 的地址。而这个映射表，也叫作散列函数或者哈希函数，存放记录的数组叫作散列表。

其中有个特殊情况，就是通过不同的 Key，可能访问到同一个地址，这种现象叫作碰撞（Collision）。而通过某个 Key 一定会得到唯一的 Value 地址。

• 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。
• 数字分析法：通过对数据的分析，发现数据中冲突较少的部分，并构造散列地址。例如同学们的学号，通常同一届学生的学号，其中前面的部分差别不太大，所以用后面的部分来构造散列地址。
• 平方取中法：当无法确定关键字里哪几位的分布相对比较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为散列地址。这是因为：计算平方之后的中间几位和关键字中的每一位都相关，所以不同的关键字会以较高的概率产生不同的散列地址。
• 取随机数法：使用一个随机函数，取关键字的随机值作为散列地址，这种方式通常用于关键字长度不同的场合。
• 除留取余法：取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为散列地址。这种方式也可以在用过其他方法后再使用。该函数对 m 的选择很重要，一般取素数或者直接用 n。

//通用散列的简单实现

int universalHash(int x, int a, int b, int p, int m)
{
	return static_cast(((static_cast(a) * x) + b) % p) % m;
}



const int DIGS = 31;
const int mersennep = (1 << DIGS) - 1;

int universalHash(int x, int a, int b, int m)
{
	long long hashVal = static_cast(a) * x + b;
	
	hashVal = ((hashVal >> DIGS) + (hashVal & mersennep));
	if (hashVal >= mersennep)
		hashVal -= mersennep;
	return static_cast(hashVal) % m;
}


bool isPrime(int n)
{
    if (n == 2 || n == 3)
        return true;

    if (n == 1 || n % 2 == 0)
        return false;

    for (int i = 3; i * i <= n; i += 2)
        if (n % i == 0)
            return false;

    return true;
}


int nextPrime(int n)
{
    if (n % 2 == 0)
        ++n;

    for (; !isPrime(n); n += 2)
        ;

    return n;
}

再好的散列函数也会产生冲突（collision），而且冲突还时有发生，所以一个HashTable必须考虑冲突如何解决。方法有：

• 分离链接法（separate chaining），后面会详细介绍。

不用链表的散列表：

• 线性探测法。就用采用散列函数h0发现有冲突时就采用h1，如果还有冲突就采用h2……其中hi(x)=[ h(x) + f(i) ] mod tableSize。 f(i)为i的线性函数，通常取f(i)=i。
• 平方探测法。与线性探测法法类似， f(i)为i的二次函数，通常取f(i)=i^2。
• 双散列。f(i)=i·h2(x)。

散列表有两种用法：一种是 Key 的值与 Value 的值一样，一般我们称这种情况的结构为 Set（集合）；而如果 Key 和 Value 所对应的内容不一样时，那么我们称这种情况为 Map，也就是人们俗称的键值对集合。

根据散列表的存储结构，我们可以得出散列表的以下特点。

由于散列表有散列函数，可以将指定的 Key 都映射到一个地址上，所以在访问一个 Key（键）对应的 Value（值）时，根本不需要一个一个地进行查找，可以直接跳到那个地址。所以我们在对散列表进行添加、删除、修改、查找等任何操作时，速度都很快。

首先，散列表实际上是存不满的，如果一个散列表刚好能够存满，那么肯定是个巧合。而且当散列表中元素的使用率越来越高时，性能会下降，所以一般会选择扩容来解决这个问题。另外，如果有冲突的话，则也是需要额外的空间去存储的，比如链地址法，不但需要额外的空间，甚至需要使用其他数据结构。

这个特点有个很常用的词可以表达，叫作“空间换时间”，在大多数时候，对于算法的实现，为了能够有更好的性能，往往会考虑牺牲些空间，让算法能够更快些。

散列表还有一个非常明显的特点，那就是无序。为了能够更快地访问元素，散列表是根据散列函数直接找到存储地址的，这样我们的访问速度就能够更快，但是对于有序访问却没有办法应对。

没有完美的散列函数，无论如何总会产生冲突，这时就需要采用冲突解决方案，这也使散列表更加复杂。通常在不同的高级语言的实现中，对于冲突的解决方案不一定一样。

• 完美散列
• 杜鹃散列
• 跳房子散列