题目
设哈希表[1]的地址范围为 0 ~ 17 ,哈希函数[2]为: H ( key ) =key%16 。用线性探测法处理冲突,输入关键字序列:( 10 , 24 , 32 , 17 , 31 , 30 , 46 , 47 , 40 , 63 , 49 ),构造哈希表,试回答下列问题: 1 画出哈希表的示意图; 2 若查找关键字 63 ,需要依次与哪些关键字进行比较? 3 若查找关键字 60 ,需要依次与哪些关键字比较? 4 假定每个关键字的查找概率相等,求查找成功时的平均查找长度[3]。
设哈希表[1]的地址范围为 0 ~ 17 ,哈希函数[2]为: H ( key ) =key%16 。用线性探测法处理冲突,输入关键字序列:( 10 , 24 , 32 , 17 , 31 , 30 , 46 , 47 , 40 , 63 , 49 ),构造哈希表,试回答下列问题: 1 画出哈希表的示意图; 2 若查找关键字 63 ,需要依次与哪些关键字进行比较? 3 若查找关键字 60 ,需要依次与哪些关键字比较? 4 假定每个关键字的查找概率相等,求查找成功时的平均查找长度[3]。
题目解答
答案
1 画表如下: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 24 40 10 30 31 46 47 2 查找 63, 首先要与 H(63)=63%16=15 号单元内容比较,即 63 与 31 比较 , 不匹配 ; 然后顺移,与 46,47,32,17,63 相比,一共比较了 6 次! 3 查找 60, 首先要与 H(60)=60%16=12 号单元内容比较,但因为 12 号单元为空(应当有空标记),所以应当只比较这一次即可。 4 对于加粗的数据元素,各比较 1 次;共 6 次;其余元素 “ 63 ”需要 6 次,“ 49 ”需要 3 次,“ 40 ”需要 2 次,“ 46 ”需要 3 次,“ 47 ”需要 3 次, 所以 ASL=1/11 ( 6 + 2 + 3 × 3+6 )= 23/11
解析
步骤 1：构造哈希表
根据哈希函数 H(key) = key % 16，将关键字序列 (10, 24, 32, 17, 31, 30, 46, 47, 40, 63, 49) 依次插入哈希表中。当发生冲突时，使用线性探测法处理冲突，即在哈希表中寻找下一个空闲位置。
步骤 2：查找关键字 63
根据哈希函数 H(63) = 63 % 16 = 15，首先查找哈希表中 15 号单元的内容，然后顺移，直到找到关键字 63。
步骤 3：查找关键字 60
根据哈希函数 H(60) = 60 % 16 = 12，首先查找哈希表中 12 号单元的内容，然后顺移，直到找到关键字 60。
步骤 4：计算查找成功时的平均查找长度
根据哈希表中每个关键字的查找次数，计算查找成功时的平均查找长度。
根据哈希函数 H(key) = key % 16，将关键字序列 (10, 24, 32, 17, 31, 30, 46, 47, 40, 63, 49) 依次插入哈希表中。当发生冲突时，使用线性探测法处理冲突，即在哈希表中寻找下一个空闲位置。
步骤 2：查找关键字 63
根据哈希函数 H(63) = 63 % 16 = 15，首先查找哈希表中 15 号单元的内容，然后顺移，直到找到关键字 63。
步骤 3：查找关键字 60
根据哈希函数 H(60) = 60 % 16 = 12，首先查找哈希表中 12 号单元的内容，然后顺移，直到找到关键字 60。
步骤 4：计算查找成功时的平均查找长度
根据哈希表中每个关键字的查找次数，计算查找成功时的平均查找长度。