已知一组初始记录关键字序列为(35,20,33,48,59,47,62,50,48)其哈希函数为H(ke
1个回答
关注
![]()
展开全部
# 根据给定的哈希函数H(key)=key%13，可以将初始记录中的关键字映射到0到12的哈希地址中。
处理冲突的方法为链地址法，即使用一个数组来存储哈希表中每个地址对应的关键字链表。
## 哈希表结构
哈希表共有13个地址，每个地址对应的链表中存储该地址哈希到的关键字序列。
| 哈希地址 | 关键字 |
| --- | --- |
| 0 | |
| 1 | 62 |
| 2 | 35 |
| 3 | 48→33 |
| 4 | 47 |
| 5 | 20 |
| 6 | |
| 7 | |
| 8 | 50 |
| 9 | |
| 10 | 59 |
| 11 | |
| 12 | |
注意，当哈希地址发生冲突时，采用链表的方式将新的关键字插入到该地址对应的链表的末尾。
## 等概率查找时查找成功的平均查找长度
等概率查找时查找成功的平均查找长度ASL可以通过公式ASL = (成功查找的关键字的查找长度之和) / (成功查找的关键字总数)来计算。
假设要查找的关键字序列为(33, 62, 48, 50)。
查找关键字33的过程：33经过哈希函数计算，对应的哈希地址为3，访问哈希表中地址为3的链表，查找到33，查找长度为1。
查找关键字62的过程：62经过哈希函数计算，对应的哈希地址为1，访问哈希表中地址为1的链表，查找到62，查找长度为1。
查找关键字48的过程：48经过哈希函数计算，对应的哈希地址为3，访问哈希表中地址为3的链表，查找到48，查找长度为2。
查找关键字50的过程：50经过哈希函数计算，对应的哈希地址为8，访问哈希表中地址为8的链表，查找到50，查找长度为1。
因此，成功查找的关键字的查找长度之和为1+1+2+1=5，成功查找的关键字总数为4，平均查找长度为ASL=5/4=1.25。
综上所述，等概率查找时查找成功的平均查找长度为1.25。
咨询记录 · 回答于2024-01-15
已知一组初始记录关键字序列为(35,20,33,48,59,47,62,50,48)其哈希函数为H(ke
已知一组初始记录关键字序列为(35,20,33,48,59,47,62,50,48)。其哈希函数为H(key)=key%13,处理冲突的方法为链地址法。试求:(1)画出哈希表。(2)计算等概率查找时查找成功的平均查找长度。
根据给定的哈希函数 H(key) = key % 13，可以将初始记录中的关键字映射到 0 到 12 的哈希地址中。处理冲突的方法为链地址法，即使用一个数组来存储哈希表中每个地址对应的关键字链表。
(1) 画出哈希表
哈希表共有 13 个地址，每个地址对应的链表中存储该地址哈希到的关键字序列。下面是将给定的初始记录插入到哈希表中的过程：
| 0 | | 1 | 62 | 2 | 35 | 3 | 48→33 | 4 | 47 | 5 | 20 | 6 | |
| :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: |
| 7 | | 8 | 50 | 9 | |10 | 59 |11 | |12 | |
注意，当哈希地址发生冲突时，采用链表的方式将新的关键字插入到该地址对应的链表的末尾。
(2) 计算等概率查找时查找成功的平均查找长度。
等概率查找时查找成功的平均查找长度 ASL 可以通过公式 ASL = (成功查找的关键字的查找长度之和) / (成功查找的关键字总数) 来计算。
假设要查找的关键字序列为 (33, 62, 48, 50)。
查找关键字 33 的过程：
33 经过哈希函数计算，对应的哈希地址为 3，访问哈希表中地址为 3 的链表，查找到 33，查找长度为 1。
查找关键字 62 的过程：
62 经过哈希函数计算，对应的哈希地址为 1，访问哈希表中地址为 1 的链表，查找到 62，查找长度为 1。
查找关键字 48 的过程：
48 经过哈希函数计算，对应的哈希地址为 3，访问哈希表中地址为 3 的链表，查找到 48，查找长度为 2。
查找关键字 50 的过程：
50 经过哈希函数计算，对应的哈希地址为 8，访问哈希表中地址为 8 的链表，查找到 50，查找长度为 1。
因此，成功查找的关键字的查找长度之和为 1+1+2+1=5，成功查找的关键字总数为 4，平均查找长度为 ASL =5/4=1.25。
综上所述，等概率查找时查找成功的平均查找长度为 1.25。
已赞过
评论
收起
你对这个回答的评价是？
