第12篇:C++ 哈希表 -散列函数的构造方法
我们前面已经简单说过散列函数的相关概念，阅读了之前哈希表的系列随笔后，想必你对哈希表有个大概的了解。下面会基于前面的基础深入探讨一下散列函数常用的构造方法，因为一个设计良好的散列函数实现，必须满足以下几点指导原则
- 计算尽可能地简化，因为我们希望尽可能达成O(1)的时间消耗
- 键(key)对应的散列值(哈希表中元素的地址)分布均匀，尽可能减少冲突
数字关键字的散列函数构造
直接定址法
就是按照线性函数的表达式计算数字关键的散列值，如下表达式
例如：下面，我们需要将下表的以年份为键，将每年的销售额数据散列到哈系表中，那么直接情况就比较简单，我们可以取年份中的地一个年份作为一个常数，这里显然另常数A=1,B=-2010,可以让年份关键字转换为更小的整数，这样做有助于节省哈希表的内存空间。
取模运算法
这这方法也叫除留余数法，一般表达式为
其中N通常是哈希表的尺寸，并且N是素数，因为与数字关键字与取模会最大限度减少散列冲突的发生，取模运算后的值作为插入元素的地址，下面就是一个示例，通常在使用开放寻址方案实现的哈希表，经常使用到取模运算法
无标题.gif
反例演示
对于数字关键字，使用取模运算方法有个致命的弱点，考虑一下上面的示例，我们假设哈系表的尺寸N=11
那么h(k)=k mod 11,探测函数使用的是线性探测p(x)=x，那么要插入哈希表的集合中有某个数字关键字的散列值达到哈系表的最大索引值，并且还与集合中其他元素的散列数值冲突，若计算递增x，那么该数字关键字重算的散列已经发生哈系表溢出的情况，
例如下面这个示例，下表中数字关键字383的初始散列数值为9与关键字42冲突，按照线性探测的逻辑就是这么样：
- x=0,i=h(383)+p(0)=(383 mod 11)+0=9 和关键字42冲突
- x=1,i=h(383)+p(1)=(383 mod 11)+1=10 和关键字32冲突
-
x=2,i=h(383)+p(2)=(383 mod 11)+2=11，更糟糕的事情发生了哈希表溢出
ss8.png
然后，你可能会说，让哈希表重散列啊～不就有更多闲置空间吗？这种做法是得不尝失的，没有从根源上去解决问题。
- 首先，哈希望左侧的索引为{1,2,3,4,5}的存储桶空间没有利用上。
- 其次，过早重散列导致内存空间巨大浪费，而且导致哈系表中元素没必要深度拷贝。
于是，在好些资料你甚至会发现有人对取莫运算的散列函数表达式，做了一些修改，例如这样：
h(x)=k mod N的修订版本
其实，这条表达式的思想是，假若k mod N计算的值达到了哈系表的最大索引(高地址的边界)，用N减去k mod N令最终的散列函数的结果跳转到哈希表的低地址查找可用存储桶。但事实上做法仍然会导致哈系表溢出的情况，于事无补的。因为当k mod N=0时，h(k)=N，此时就是哈希表溢出。
通过上面的例子，我们看到取模运算法实现的散列函数的缺陷在于，当作为传入数据源的关键字集合的个数m和哈系表的初始尺寸N，但N-m这个绝对值不够大的话，会容易导致关键字插入哈希表溢出或冲突次数的发生概率会增大。
数字分析法
当给定的数字关键字由很多位组成，有些位是相对固定，而有些位会随机变化，数字分析法的主要思想就是从这些关键字中提取随机变化的部分组合一起作为这些数字关键字的地址，从而达到映射均匀的目地。
例如:我们的身份证号18位，如下图特征
- 索引0-4，索引6-8，索引10-12，索引14都是相对固定不会有太大的的变化
- 索引5，索引9，索引13，索引15-17，这些是随机变动的
我们可以将随机变动的位提取出来组合成一个数字，例如下图，
- Step1:从红色的随机位中提取数字字符出来组合成42321,最后一位是检验位要么是X或0-9,检验位最后一步处理
- Step2:将随机数字字符串"42321"从ASCII码转换为实际的整数，对应如下图h2(k)散列函数
-
Step3:将带有特殊含义的随机位做特殊处理，在本例中若检验位是字符'X'(罗马数字X)，若是k[17]等于字符'X'就新增一个10进位后+10,若出现0-9之间的ASCII字迹,就以k[17]-'0'转换为ASCII数字字符对应意义上的各位整数，最后和h2(k)的整数结果相加
ss8.png
最终h1(k)是对应本示例中对应身份证号码的主散列函数(Primary Hash Function)，而h2(k)我们称为辅助函数(Secondary Hash Function),一个主散列函数可以有多个解决子问题的辅助散列函数.
备注：数字分析法经常用到进制位以及ASCII转换为整数这两项基础知识，若不熟悉的读者，请自行恶补这方面的知识。
折叠法
更新中......
