1.已知哈希表长11,地址区间为0~10,给定关键字序列(20,30,70,15,8,12,18,63,19)。设哈希函数为h(k)=k%11,分别采用线性探查法和链地址法处理冲突,构造哈希表。要求写出各自的计算过程并画出对应的哈希表。
时间: 2023-04-25 12:02:40 浏览: 106
线性探查法:
首先将关键字序列插入哈希表中,插入过程如下:
1. 20 % 11 = 9,将20插入哈希表的第9个位置;
2. 30 % 11 = 8,将30插入哈希表的第8个位置;
3. 70 % 11 = 5,将70插入哈希表的第5个位置;
4. 15 % 11 = 4,将15插入哈希表的第4个位置;
5. 8 % 11 = 8,发生冲突,线性探查到下一个位置,即第9个位置,将8插入哈希表的第9个位置;
6. 12 % 11 = 1,将12插入哈希表的第1个位置;
7. 18 % 11 = 7,将18插入哈希表的第7个位置;
8. 63 % 11 = 8,发生冲突,线性探查到下一个位置,即第9个位置,发现该位置已经被占用,继续线性探查到下一个位置,即第10个位置,将63插入哈希表的第10个位置;
9. 19 % 11 = 8,发生冲突,线性探查到下一个位置,即第9个位置,发现该位置已经被占用,继续线性探查到下一个位置,即第10个位置,发现该位置已经被占用,继续线性探查到下一个位置,即第个位置,将19插入哈希表的第个位置。
最终得到的哈希表如下:
: 19
1: 12
2:
3:
4: 15
5: 70
6:
7: 18
8: 30
9: 20
10: 63
链地址法:
首先创建一个长度为11的链表数组,将关键字序列插入哈希表中,插入过程如下:
1. 20 % 11 = 9,将20插入哈希表的第9个位置,链表为:9->20;
2. 30 % 11 = 8,将30插入哈希表的第8个位置,链表为:8->30;
3. 70 % 11 = 5,将70插入哈希表的第5个位置,链表为:5->70;
4. 15 % 11 = 4,将15插入哈希表的第4个位置,链表为:4->15;
5. 8 % 11 = 8,将8插入哈希表的第8个位置,链表为:8->30->8;
6. 12 % 11 = 1,将12插入哈希表的第1个位置,链表为:1->12;
7. 18 % 11 = 7,将18插入哈希表的第7个位置,链表为:7->18;
8. 63 % 11 = 8,将63插入哈希表的第8个位置,链表为:8->30->8->63;
9. 19 % 11 = 8,将19插入哈希表的第8个位置,链表为:8->30->8->63->19。
最终得到的哈希表如下:
:
1: 12
2:
3:
4: 15
5: 70
6:
7: 18
8: 30->8->63->19
9: 20
10: