设一组关键字{19,1,23,14,5520,84,27,68},采用哈希函数H(key)=key%1 3,分别采用开放地址法的线性探测发及二次探测再散列方法解决冲突,试在0~12的散列地址空间中对该关键字序列构造哈希表,并分别求出平均查找长度。
时间: 2024-04-06 07:33:34 浏览: 126
好的,让我来回答你的问题。
首先,我们需要明确一下什么是哈希表和哈希函数。哈希表是一种根据关键字直接访问内存存储位置的数据结构,而哈希函数则是将关键字映射为哈希表中的地址。
针对你的问题,我们可以按照以下步骤进行:
1. 确定哈希表的大小为13,即散列表的地址空间为0~12。
2. 设计哈希函数H(key)=key%13,即采用除留余数法将关键字映射为0~12之间的整数。
3. 采用开放地址法的线性探测法进行冲突解决。具体地,对于关键字k,如果H(k)被占用,则尝试探测下一个地址,即H(k)+1,如果H(k)+1也被占用,则继续探测下一个地址,即H(k)+2,以此类推,直到找到一个空的地址为止。
4. 采用二次探测再散列法进行冲突解决。具体地,对于关键字k,如果H(k)被占用,则尝试探测下一个地址,即H(k)+1^2,如果(H(k)+1^2)%13也被占用,则继续探测下一个地址,即(H(k)+2^2)%13,以此类推,直到找到一个空的地址为止。
根据上述方法,我们可以构造出如下的哈希表:
|地址|关键字(线性探测法)|关键字(二次探测法)|
|----|------------------|------------------|
| 0 | 84 | 84 |
| 1 | 23 | 23 |
| 2 | 1 | 1 |
| 3 | 14 | 14 |
| 4 | 27 | 27 |
| 5 | 68 | 68 |
| 6 | 19 | 19 |
| 7 | | 5520 |
| 8 | | |
| 9 | | |
| 10 | | |
| 11 | | |
| 12 | | |
其中,采用线性探测法时,关键字5520没有找到合适的空闲位置,无法插入哈希表中;而采用二次探测法时,关键字5520则被插入在地址7处。
最后,我们需要计算每种冲突解决方法的平均查找长度。平均查找长度指的是在哈希表中查找一个关键字的平均比较次数。设哈希表中共有n个关键字,查找一个关键字的平均查找长度为ASL,则:
ASL = (查找成功时的比较次数 + 查找失败时的比较次数) / n
对于线性探测法,查找成功时的比较次数为1,查找失败时的比较次数为(1/2)*(1+(1/(1-8/13)))≈2.385。因此,线性探测法的平均查找长度为:
ASL = (1 + 2.385) / 8 ≈ 0.423
对于二次探测法,查找成功时的比较次数为1,查找失败时的比较次数为(1/2)*(1+(1/(1-2*(3/13))))≈1.308。因此,二次探测法的平均查找长度为:
ASL = (1 + 1.308) / 8 ≈ 0.189
综上所述,二次探测法的平均查找长度要比线性探测法的平均查找长度小,因此二次探测法更适合解决此问题。
阅读全文