哈希表的使用(C++代码)

概念

散列技术是在记录的存储位置和他的关键字之间建立一个确定的对应关系f，是的每个关键字key对应一个存储位置f(key)。查找时，根据这个对应的关系找到给定值key的映射f(key)，若查找集合中存在这个记录，则必定在f(key)的位置上。我们把这种对应关系f成为散列函数，又称为哈希(Hash)函数。采用散列技术将记录存储在一块连续的存储空间中，这块连续空间称为散列表或哈希表(Hash-Table)。

散列表的构造方法

1.直接定址法

直接定址法使用下面的公式

比如统计出生年份，那么就可以使用f(key)=key−1990$f(key)=key-1990$来计算散列地址。

2.除留取余法

这种方法是最常用的散列函数构造方法，对于表长为m的散列公式为

3.数字分析法

分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址这里使用一个手机号码作为例子，手机号码是一个字符串，一般的说，后面4位是真正的用户号。

4.折叠法

把关键词分割成位数相同的几个部分，然后叠加。

5.平方取中法

冲突解决方法

常用处理冲突的思路：

• 换个位置: 开放地址法
• 同一位置的冲突对象组织在一起: 链地址法

1.开放地址法

一旦产生了冲突（该地址已有其它元素），就按某种规则去寻找另一空地址.若发生了第 i 次冲突，试探的下一个地址将增加di$d_i$， 基本公式是：

这里面di$d_i$ 决定了不同的解决冲突方案： 线性探测、平方探测、双散列。下面依次介绍各中方法。

1.1 线性探测法
线性探测法以增量序列1，2，……，（TableSize−1）$1，2，\dots \dots ，（TableSize-1）$循环试探下一个存储地址。

[例]设关键词序列为 {47， 7， 29， 11， 9， 84， 54， 20， 30},散列表表长TableSize$TableSize$ =13 （装填因子 α$\alpha$= 9/13 ≈ 0.69）,散列函数为： h(key)=keymod11$h(key)=key\mathrm{mod}11$。 用线性探测法处理冲突，列出依次插入后的散列表，并估算查找性能。

[解]初步的散列地址如下表所示。

关键词(key)$(key)$	47	7	29	11	9	84	54	20	30
散列地址h(key)$h(key)$	3	7	7	0	9	7	10	9	8

可以看出，有多个关键词的散列地址发生了冲突，具体见下表。

关键词(key)$(key)$	47	7	29	11	9	84	54	20	30
散列地址h(key)$h(key)$	3	7	7	0	9	7	10	9	8
冲突次数	0	0	1	0	0	1	0	0	0

具体的哈希表构建过程可以用下面的图表来表示

这里引出一下散列表的的查找性能分析

散列表的查找性能，一般有两种方法
1.成功平均查找长度(ASLs)
2.不成功平均查找长度 (ASLu)

对于上面一题的散列地址冲突次数为

散列地址h(key)$h(key)$	0	1	2	3	4	5	6	7	8	9	10	11	12
关键词(key)$(key)$	11	30		47				7	29	9	84	54	20
冲突次数	0	6		0				0	1	0	3	1	3

ASLs： 查找表中关键词的平均查找比较次数（其冲突次数加1）

冲突次数 0 6 0 0 1 0 3 1 3
ASLu：不在散列表中的关键词的平均查找次数（不成功）
一般方法：将不在散列表中的关键词分若干类。
如：根据H(key)值分类