哈希函数、哈希表、哈希地址

根据设定的哈希函数\(H(key)\)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集（区间）上，并以关键字在地址集上的“像”作为记录在表中的存储位置，这种表便称为哈希表，这一映像过程称为哈希造表或散列，所得存储位置成哈希地址或散列地址。

冲突、同义词

不同的关键字经哈希函数映像后求得到的哈希地址可能相同，即\(key1\neq key2\ and \ H(key1)=H(key2)\)，这就是冲突（collision）；具有相同哈希地址的关键字对该哈希函数来说就是同义词（synonym）。

哈希函数选得合适可以减少冲突现象。

一般情况下，哈希函数是一个压缩映像（关键字集合到地址集合的映像，而关键字集合的大小远大于地址集合），因此冲突只能尽可能地少而不能完全避免。

哈希函数的构造方法

常用的构造哈希函数的方法有：

1. 直接定址法
2. 数字分析法
3. 平方取中法
4. 折叠法
5. 除留余数法
6. 随机数法

处理冲突的方法

处理冲突过程中会有一个地址序列\(H_i,i=1,2,\dots,k\)，即如果发生冲突，就去找下一个地址。

通常用的处理冲突的方法有下列几种：

1. 开放定址法
2. 再哈希法
3. 链地址法
4. 建立一个公共溢出区

开放定址法

其中\(H(key)\)为哈希函数；\(m\)是哈希表表长；\(d_i\)为增量序列，可以有下面3种取法：

1. \(d_i=1,2,3\dots,m-1\)，称为线性探测再散列
2. \(d_i=1^2,-1^2,2^2,-2^2,3^2,\dots,\pm k^2,(k\leq m/2)\)，称为二次探测再散列
3. \(d_i=伪随机数序列\)，称为伪随机探测再散列

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!

数据结构-哈希

原文：https://www.cnblogs.com/chouxianyu/p/13455884.html