线性表的关键字集合key = { 37，12，28，55，20，39，9 }，构造哈希表，表长为7（范围0~6），选取哈希函数的方法为“除留余数法”：H ( key ) = key % 7，解决冲突方法为“线性探测再散列”，请按上述条件： （1）求出key中各值的地址，画出相应的哈希表；（2）求出key中各值查找成功时的查找次数

(1) 根据哈希函数H(key) = key % 7，可以得到key中各值的地址：

37 -> H(37) = 2

12 -> H(12) = 5

28 -> H(28) = 0

55 -> H(55) = 6

20 -> H(20) = 6 （冲突，线性探测再散列，H(20) = (H(20)+1) % 7 = 0）

39 -> H(39) = 4

9 -> H(9) = 2 （冲突，线性探测再散列，H(9) = (H(9)+1) % 7 = 3）

根据上述地址，可以画出哈希表如下：

| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| - | - | - | - | - | - | - |
|28 | |37 | 9 |39 |12 |55 |
|20 | | | | | | |

(2) 查找成功的平均查找次数为：

(1+1+1+2+1+1+2)/7 = 1.29

其中，37、12、28、55、39、9都只需要进行一次查找即可找到，平均查找次数为1；而20需要进行两次查找才能找到，平均查找次数为2。

相关问题

线性表的关键字集合key = { 37，12，28，55，20，39，9 }，构造哈希表，表长为7（范围0~6），选取哈希函数的方法为“除留余数法”：H ( key ) = key % 7，解决冲突方法为“线性探测再散列”，请按上述条件： （1）求出key中各值的地址，画出相应的哈希表；

根据除留余数法，将关键字集合中的每个元素除以7取余数，得到的余数即为该元素在哈希表中的地址。

37 % 7 = 2

12 % 7 = 5

28 % 7 = 0

55 % 7 = 6

20 % 7 = 6

39 % 7 = 4

9 % 7 = 2

其中，55和20的哈希地址相同，发生了冲突。根据线性探测再散列的方法，当发生冲突时，依次向后查找哈希表，直到找到空位置为止。具体实现过程如下：

- 首先，将关键字为55的元素插入哈希表的地址为6的位置，得到哈希表为：[0, 0, 2, 0, 0, 0, 55]；
- 接着，将关键字为20的元素插入哈希表的地址为6的下一个位置，即地址为0的位置，得到哈希表为：[20, 0, 2, 0, 0, 0, 55]；
- 最后，将哈希表中的其它元素插入相应的位置，得到最终的哈希表为：[28, 9, 37, 12, 0, 20, 55]。

下面是哈希表的示意图：

哈希地址  0    1    2    3    4    5    6
关键字  28    9    37   12   无   20   55

其中，关键字为无的位置表示该位置未被占用。

3.（10分）线性表的关键字集合key = { 37，12，28，55，20，39，9 }，构造哈希表，表长为7（范围0~6），选取哈希函数的方法为“除留余数法”：H ( key ) = key % 7，解决冲突方法为“线性探测再散列”，请按上述条件： （1）求出key中各值的地址，画出相应的哈希表；（4分）

根据除留余数法，计算各元素的地址：

37 % 7 = 2
12 % 7 = 5
28 % 7 = 0
55 % 7 = 6
20 % 7 = 6
39 % 7 = 4
9 % 7 = 2

因为20和55的地址都为6，所以需要进行线性探测再散列，即往后依次探测空闲位置，直到找到一个空闲位置为止。探测的顺序为6，0，1，2，3，4，5。

因此，各元素在哈希表中的地址为：

0: 28
1:
2: 37 -> 9
3:
4: 39
5: 12
6: 55 -> 20

画出相应的哈希表如下：

+---+---+---+---+---+---+---+
| 28|   |37 |   |39 |12 |55 |
+---+---+---+---+---+---+---+
  0   1   2   3   4   5   6