查找算法【哈希表】- 散列函数

查找算法【哈希表】- 散列函数

散列函数（Hash Function），又被称为哈希函数，是将关键字映射到存储地址的函数，被记为hash(key)=Addr。

设计散列函数时需要遵循两个原则：

• ①散列函数尽可能简单，能够快速计算出任一关键字的散列地址；
• ②散列函数映射的地址应均匀分布在整个地址空间，避免聚集，以减少冲突。

散列函数的设计原则可简化为四字箴言：简单、均匀。

常见的散列函数包括直接定址法、除留余数法、随机数法、数字分析法、平方取中法、折叠法、基数转换法和全域散列法。

【直接定址法】

直接定址法指直接取关键字的某个线性函数作为散列函数，其形式如下：

hash(key)=a ×key+b
1

其中，a 、b 为常数。

直接定址法适用于事先知道关键字而关键字集合不是很大且连续性较好的情况。如果关键字不连续，则有大量空位，造成空间浪费。

例如，学生的学号为{601001,601002,601005,…,601045}，可以设计散列函数为H (key)= key-601000，这样可以将学生的学号直接映射到存储地址下标，符合简单、均匀的设计原则。

【除留余数法】

除留余数法是一种最简单、常用的构造散列函数的方法，并且不需要事先知道关键字的分布情况。

假定散列表的表长为m ，取一个不大于表长的最大素数p ，设计散列函数为hash(key)= key%p ，选择p 为素数是为了避免发生冲突。在实际应用中，访问往往具有某种周期性，若周期与p 有公共的素因子，则发生冲突的概率将急剧上升。

例如，手表中的齿轮，两个交合齿轮的齿数最好是互质的，否则出现齿轮磨损绞断的概率很大。因此，发生冲突的概率随着p 所含素因子的增多而迅速增加，素因子越多，冲突越多。

【随机数法】

随机数法指将关键字随机化，然后使用除留余数法得到存储地址。

散列函数为hash(key)= rand(key)%p ，其中，rand()为C、C++中的随机函数，rand(n )表示求0～n -1的随机数。p 的取值和除留余数法相同。

【数字分析法】

数字分析法指根据每个数字在各个位上的出现频率，选择均匀分布的若干位作为散列地址，适用于已知的关键字集合，可以通过观察和分析关键字集合得到散列函数。

例如，一个关键字集合如下图所示，

第1、2位的数字完全相同，不需要考虑，第4、7、8位的数字只有个别不同，而第3、5、6位的数字均匀分布，可以将第3、5、6位的数字作为散列地址，或者将第3、5、6位的数字求和后作为散列地址。

【平方取中法】

首先求关键字求的平方，然后按散列表的大小，取中间的若干位作为散列地址（求平方后截取），适用于事先不知道关键字的分布且关键字的位数不是很大的情况。

例如，散列地址为3位，计算关键字10123的散列地址，取10123^{2的中间3位数，即475：10123}2 =102475 129。

【折叠法】

折叠法指将关键字从左到右分割成位数相等的几部分，将这几部分叠加求和，取后几位作为散列地址，适用于关键字位数很多且事先不知道关键字分布的情况。

折叠法分为移位折叠和边界折叠两种。

• 移位折叠指将分割后的每一个部分的最低位对齐，然后相加求和；
• 边界折叠如同折纸，将相邻部分沿边界来回折叠，然后对齐相加。

例如，设关键字为4 5 2 0 7 3 7 9 6 0 3，散列地址为3位。因为散列地址为3位，因此将关键字每3位划分一块，叠加后将进位舍去，移位叠加得到的散列地址为324，边界叠加得到的散列地址为648，如下图所示。

【基数转换法】

例如，将十进制数转换为其他进制表示，例如345的九进制表示为423。

另外，散列函数大多数是基于整数的，如果关键字是浮点数，则可以将关键字乘以M 并四舍五入得到整数，再使用散列函数；或者将关键字表示为二进制数然后使用散列函数。

如果关键字是字符，则可以将字符转换为R 进制的整数，然后使用散列函数。

例如，在字符串str="asabasarcsar…"中有5种字符，字符串的长度不超过10^6 ，求在这个字符串中有多少个长度为3的不同子串。

（1）按字符串顺序统计出5种字符（不需要遍历整个串，得到5种字符即可），将其与数字对应：a-0；s-1；b-2；r-3；c-4。

（2）将所有长度为3的子串取出来，根据字符与数字的对应关系，将其转换为五进制数并放入hash[]数组中，hash[]数组为布尔数组，将其初始化为0，表示未统计该子串。

• “asa”：0×5^2 +1×5^1 +0×5^0 =5，hash[5]=1，计数count=1。
• “sab”：1×5^2 +0×5^1 +2×5^0 =27，hash[27]=1，计数count=2。
• “aba”：0×5^2 +2×5^1 +0×5^0 =10，hash[10]=1，计数count=3。
• “bas”：2×5^2 +0×5^1 +1×5^0 =51，hash[51]=1，计数count=4。
• “asa”：0×5^2 +1×5^1 +0×5^0 =5，hash[5]已为1，表示已统计过该子串，不计数。
• …

【全域散列法】

如果对关键字了解不多，则可以使用全域散列法，即将多种备选的散列函数放在一个集合H 中，在实际应用中随机选择其中的一个作为散列函数。

如果任意两个不同的关键字key1≠key2、hash(key1)=hash(key2)的散列函数个数最多为|H |/m ，|H |为集合中散列函数的个数，m 为表长，则称H 是全域的。