数据结构之哈希表

数据结构之哈希表

哈希表定义：也叫散列表。根据设定的哈希函数及处理冲突的方法，将元素存储在一段有限的连续空间中。即存储地址H（key）与关键字key的关系构建。

常用设置哈希表的方法：
1 直接定址法：利用线性函数来设置。H（key）=a*key+b；其中a≠0，b为常数。
举例：统计各年龄段的人口，用直接定址法设定哈希函数。

2 数字分析法：若关键字是x进制数，且可预知可能出现的所有关键字值，则可以去关键字的若干位构成哈希地址函数。
举例：

3 平方取中法：若关键字较短，则可以先平方再类似上面，取个别的位数为哈希地址。和上面差不多，就不举例了。

4 折叠法：分为移位叠加和间界叠加。将关键字值分割成位数相同的几部分，然后取这几部分的叠加和（舍弃进位）作为哈希地址。
4.1）移位叠加：图书馆编号有0-442-20586-4，即0442205864，按此编号构造哈希地址：

如上图，将该编号分成三部分，将每四位对齐后叠加，进位舍弃，得出来的数据就是哈希地址。
4.2）间界叠加：

如上图，先将低四位写上，再将第二部分倒写对齐，第三部分又与第一部分一样，如此间界的对齐，得出的哈希地址就是间界叠加。

5 除留余数法：设有一组关键字，试用除留余数法求设计哈希函数。关键字组：（19,14,23,01,68,20,84,27,55,11,10,79,12,39,21）。
可以设置为H(key)=key%13；为什么取13？我们可以假设它取9，得出的余数分别为1 5 5 1 5 2 3 0 1 2 1 7 3 3 3。可以看出1 3 5的余数非常多，当它映射到存储地址时，会更容易的造成冲突。所以我们在选择取余数时，一般取质数，让它的冲突尽可能的少。

哈希表解决冲突的常用方法：
1 开放定址法：当出现冲突时，按照一定规律给余数加上相应的值，以此当做其哈希地址。

举例：

当18填进哈希表时，发现余数4已经被填了，所以给其余数加1，发现是空的则填进18。后面的也如此分析。

对比一下线性探测与二次探测与冲突的处理次数：

看深色的字体，线性探测的冲突比较次数为1 1 2 1 3 6 2 5 1，再看二次探测的，明显比线性的少，所以二线探测再散列处理冲突比较好。

2 链地址法：就是当出现冲突时，将冲突的用链表连接起来，末尾为空。
举例：


以0地址为例，当插入84后，再次插入28时，结果发现已被填入，它将28用链表插入至84前面，这就是链地址法。

3 公共溢出区法：使用一个公共区域存储冲突的数据。
举例：


由于取余数为7，所以其哈希地址为0-6,7之后为公共溢出区。当填完67后再填18结果发现4的位置已经被填进，所以将18填进公共溢出区。

最后在哈希表查找元素：根据哈希函数找到哈希地址。首先，若该地址无元素，则查找失败；若有元素就对比该关键字key是否与对应哈希地址的值相等，相等就查找成功；不相等则根据处理冲突的方法继续寻找。

总结：
1）设定哈希函数的方法。直接定址法，数字分析法，平方取中法，折叠法，除留取余法共五个。
2）处理冲突的方法：开放定址法，链地址法，公共溢出区法共三个。