哈希函数H(K)=3 K mod 11,哈希地址空间为0~10,对关键字序列(32,13,49,24,38,21,4,12),按下述两种解决冲突的方法构造哈希表,并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。
时间: 2024-06-13 11:08:50 浏览: 205
根据题目要求,哈希函数H(K)=3 K mod 11,哈希地址空间为0~10,关键字序列为(32,13,49,24,38,21,4,12)。下面分别介绍两种解决冲突的方法构造哈希表,并求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。
方法一:链地址法
首先,根据哈希函数计算每个关键字的哈希地址,然后将其插入到对应的链表中。具体步骤如下:
1. 初始化哈希表,创建11个空链表。
2. 对于每个关键字,计算其哈希地址H(K)=3 K mod 11。3. 将关键字插入到对应的链表中。
4. 计算查找成功时的平均查找长度ASLsucc和查找失败时的平均查找长度ASLunsucc。
根据上述步骤,可以得到构造的哈希表如下:
| 哈希地址 | 链表 |
| -------- | ---- |
| 0 | |
| 1 | 21 |
| 2 | 12 |
| 3 | 13 |
| 4 | 24 |
| 5 | 38 |
| 6 | 32 |
| 7 | |
| 8 | |
| 9 | 49 |
| 10 | 4 |
其中,哈希地址为0、7、8没有对应的关键字,因此对应的链表为空。
根据定义,查找成功时的平均查找长度ASLsucc为所有查找成功的关键字的查找长度之和除以关键字总数。查找失败时的平均查找长度ASLunsucc为所有查找失败的关键字的查找长度之和除以关键字总数加1。因此,可以得到如下计算公式:
ASLsucc = (1+2+1+1+1+1+1)/8 = 1.25
ASLunsucc = (3+1+1)/9 = 0.56
方法二:二次探测再散列法
二次探测再散列法是一种解决冲突的方法,其具体步骤如下:
1. 初始化哈希表,创建11个空槽位。
2. 对于每个关键字,计算其哈希地址H(K)=3 K mod 11。
3. 如果对应的槽位为空,则将关键字插入到该槽位中;否则,使用二次探测再散列法寻找下一个空槽位。
4. 计算查找成功时的平均查找长度ASLsucc和查找失败时的平均查找长度ASLunsucc。
根据上述步骤,可以得到构造的哈希表如下:
| 哈希地址 | 槽位 |
| -------- | ---- |
| 0 | 32 |
| 1 | 13 |
| 2 | 12 |
| 3 | 24 |
| 4 | 38 |
| 5 | 21 |
| 6 | 49 |
| 7 | 4 |
| 8 | |
| 9 | |
| 10 | |
其中,哈希地址为8、9、10没有对应的关键字,因此对应的槽位为空。
根据定义,查找成功时的平均查找长度ASLsucc为所有查找成功的关键字的查找长度之和除以关键字总数。查找失败时的平均查找长度ASLunsucc为所有查找失败的关键字的查找长度之和除以关键字总数加1。因此,可以得到如下计算公式:
ASLsucc = (1+1+1+1+1+1+1)/8 = 1
ASLunsucc = (2+1+1)/9 = 0.44
阅读全文