写在前边的话：你的支持是我写作的动力，有帮助到你的话麻烦点赞加收藏呦。感激不尽！如有错误也请留言指正。
考研数据结构练习，欢迎订阅我的专辑《考研数据结构题型分类讲解练习》
目录
一、 线性探测
接下来重点讲解查找失败的ASL
二、二次探测再散列
三、线性探测再散列
本文以例题形式讲解散列查找中，散列表的构建，以及查找成功的ASL和失败的ASL。重点讲解求解失败的ASL的过程，巨详细（后边还有其他例题）
【2010年全国试题41（10分）】将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为： H(key) = (keyx3) MOD 7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。
(1) 请画出所构造的散列表。
(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。
表1-1 key78301118914H(key)0365560实际散列位置0365781查找成功需要探测次数1111332（1）装填因子, 所以 n = 10
表 1-2 0123456789714 8 1130189（2）根据表1-1中 查找查找成功需要探测次数，
求解查找失败的ASL需要计算出每个散列位置（即每个模对应的值）查找失败所需要的的次数，本题散列函数模的是7，所以只需要计算模为0,1,2,3,4,5,6的关键字查找失败所需要的次数。查找到空说明查找失败，查找示意图如下
查找模为0的关键字，失败时比较的次数为3将上述过程整理成表格如下
表1-3 0123456789 717 8 1130189 各个模查找失败需要比较的次数321215查找失败的平均比较次数为：
2.【东北大学2002 二、2 (5分)】设有一组关键字(9, 01,23, 14, 55, 20, 84,27)，采用哈希函数: H(key)=key mod 7，表长为10，用开放地址法的二次探测再散列方法
解决冲突。要求:对该关键字序列构造哈希表，并计算查找成功的平均查找长度。
表2-1 901231455208427H(key)=key mod 721206
606第一次冲突+1 3 717第二次冲突+4 40第三次冲突+9 5实际位置21306745查找需要次数11211234 表2-2 哈希表 012345678914192384275520查找成功所需的
3.设散列表的表长m=15,散列函数H(key)=key mod 13,关键码集合为（53, 17,12, 61, 89, 70, 87, 25, 64, 46),采用二次探测法处理冲突,试构造闭散列表,并计算查找成功的平均查找长度。
表3-1 key53171261897087256446H(key)14129115912127第一次冲突应散列的位置 +1 101313 第二次冲突应散列的位置 -1 11 第三次冲突应散列的位置 +4 1 第四次冲突应散列的位置 -4 8 实际散列位置14129115101387查找成功比较次数1111112251 表3-2哈希表 01234567891011121314 53 1770 46646187891225查找成功的
4【东北大学2001六(18分)】对下面的关键字集(30, 15, 21, 40, 25,26, 36, 37),若查找表的装填因子为0.8,采用线性探测再散列方法解决冲突。
(1)设计哈希函数; (2)画出哈希表; (3)计算查找成功和查找失败的平均查找长度;
（1） Hey(key) = key % 7;
（2）
表4-1 key3015214025263637Hey(key)21054512实际散列位置21054637查找成功所需次数11111236 表4-2 哈希表 01234567892115303625402637（3）查找成功的平均查找长度
表4-3 0123456789 2115303625402637 查找失败需要比较的次数9876543查找失败的平均查找长度
3【北京工业大学2000三(8分)1 【烟台大学2007四、4 (10分)】采用哈希函数H(k)-3*k mod 13并用线性探测开放地址法处理冲突,在散列地址空间[0..12]中对关键字序列22, 41, 53, 46, 30, 13, 1, 67,51。
(1)构造哈希表(画示意图);
(2)装填因子;
等概率下(3)成功的和(4)不成功的平均查找长度。
