1. 概念

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

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

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

2. 几种哈希函数

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

3. 解决冲突的方法

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

不用链表的散列表：

  • 线性探测法。就用采用散列函数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)。

4. 散列表的特点

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

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

（1） 访问速度很快

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

（2） 需要额外的空间

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

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

（3） 无序

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

（4） 可能会产生碰撞

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

5. 以最坏情形O(1)访问的散列表

  • 完美散列
  • 杜鹃散列
  • 跳房子散列
    通过预先确定的、在计算机结构体系的基础上优化的常数，来为探测序列的最大长度定界。这么做将给出在最坏情形下常数时间的查找，并且像杜鹃散列一样，查找或许与同时检测可能位置的有界集是并行的。
    跳房子散列是相对较新的算法，对那些利用多处理器以及要求并行性和协同性的应用而言。

6. 通用散列

虽然散列表非常有效，并且在适当的装填因子的假设下每次操作花费常数平均开销，但是它们的分析和性能却依赖于具有如下两个基本性质的散列函数：

  • 散列函数必须是常数时间内可计算的(即，与散列表中的项数无关)。
  • 散列函数必须在数组所包含的位置之间均匀地分布表现。

通用散列函数：

如果对任意x≠y，散列函数簇 H 中使得 h(x)=h(y) 的散列函数 h 的个数最多为|H|M，则称散列函数簇 H 是通用的(universal)。

定理1

散列函数簇 H={ Ha,b(x) = (( ax+b )mod p) mod m，其中 1≤ a ≤ p-1，0 ≤ b ≤ p-1}是通用的。

//通用散列的简单实现
/*
* x代表要哈希的对象，m代表TableSize，a、b是随机选出的
* 散列函数簇 H={H(x)=((ax+b)mod p)mod m，其中1<=a<=p-1，0<=b<=p-1}是通用的。
*/
int universalHash(int x, int a, int b, int p, int m)
{
	return static_cast<int>(((static_cast<long long>(a) * x) + b) % p) % m;
}

/*
* 形如2^n-1的素数叫Mersenne素数，如2^5-1、2^61-1、2^31-1等，
* 涉及Mersenne素数的模运算可以通过一次移位和一次减法实现
*/
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<long long>(a) * x + b;
	
	hashVal = ((hashVal >> DIGS) + (hashVal & mersennep));
	if (hashVal >= mersennep)
		hashVal -= mersennep;
	return static_cast<int>(hashVal) % m;
}

通用散列对于字符串也是存在的。首先，选取大于M的任意素数p(并大于最大的字符代码)。然后，使用我们标准的字符串散列函数，在1和p-1之间的中间散列值。最后，应用一个通用散列函数来生成在0和M-1之间的最终的散列值。

原文地址：http://www.cnblogs.com/awst-lee/p/16801383.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性