一、线性探测再散列法
Hash 表: 元素的值 (value) 和在数组中索引位置 (index) 有一个确定关系
Index = Hash(key) ==> y = f(x)Index 有可能相同, 怎么处理冲突?
在 “处理冲突” 上可能会有不同的方法。
示例 :
将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从 0 开始的一维数组。散列函数为： H(key) = (key * 3) MOD 7，处理冲突采用线性探测再散列法，要求装填（载）因子为 0.7。
(1) 请画出所构造的散列表；
(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。
- 散列表
// 计算哈希表长度
α = (表中填入的记录数 / 哈希表长度)
哈希表长度 = ceil(7 / 0.7) = ceil(10)
// Hash函数计算
H(7) = (7 * 3) MOD 7 = 0
H(8) = (8 * 3) MOD 7 = 3
H(30)= (30 * 3) MOD 7 = 6
H(11)= (11 * 3) MOD 7 = 5
H(18)= (18 * 3) MOD 7 = 5
H(9)= (9 * 3) MOD 7 = 6
H(14)= (14 * 3) MOD = 0
//按关键字序列顺序依次向哈希表中填入，发生冲突后按照 “线性探测”探测到第一个空位置填入。
- 查找长度：
2.1 查找成功的平均查找长度
（待查找的数字肯定在散列表中才会查找成功）
查找数字 A 的长度 = 需要和散列表中的数比较的次数；
步骤：
比如 查找数字：8
则 H(8) = (8x3) MOD 7 = 3
哈希表中地址 3 处的数字为 8，进行了第一次比较：8 = 8，则查找成功，查找长度为 1；
比如查找数字：14
则 H(14) = (14x3) MOD 7 = 0
哈希表中地址 0 处的数字为 7，进行第一次比较：7≠14
哈希表中地址 1 处的数字为 14，进行第二次比较：14=14 ，则查找成功，查找长度为 2。 _
_
所以总的查找成功的平均查找长度 = （1+1+1+1+3+3+2）/7 = 12/7
2.2 查找不成功的平均查找长度 （待查找的数字肯定不在散列表中）
【解题的关键之处】根据哈希函数地址为 MOD7，因此任何一个数经散列函数计算以后的初始地址只可能在 06 的位置 6 位置查找失败的查找次数为：
查找 0
地址 0，到第一个关键字为空的地址 2 需要比较 3 次，因此查找不成功的次数为 3.
地址 1，到第一个关键字为空的地址 2 需要比较 2 次，因此查找不成功的次数为 2.
地址 2，到第一个关键字为空的地址 2 需要比较 1 次，因此查找不成功的次数为 1.
地址 3，到第一个关键字为空的地址 4 需要比较 2 次，因此查找不成功的次数为 2.
地址 4，到第一个关键字为空的地址 4 需要比较 1 次，因此查找不成功的次数为 1.
地址 5，到第一个关键字为空的地址 9，因此查找不成功的次数为 5.
地址 6，到第一个关键字为空的地址 9，因此查找不成功的次数为 4. 于是得到如下数据： _
_
二、平方探测再散列（二次探测再散列）：
线性探测再散列
二次探测再散列
