用关键字序列{1，9，12，11，25，35，17，29}创建一个哈希表，装填因子a=1/2，确定表长m，采用除留余数法构造哈希函数，通过链地址法来处理冲突。 （1）求m的值； （2）画出哈希表； （2）求在等概率情况下，查找成功和查找失败的平均查找长度。

（1）根据装填因子a=1/2，可知每个桶的平均填充因子为0.5，即每个桶最多存放一个关键字。因此，哈希表的长度m应该为关键字个数n的两倍，即m=2n=16。

（2）画出哈希表如下所示：

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |12 |13 |14 |15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| | | | | | | | | | | | | | | | |

（3）在等概率情况下，查找成功的平均查找长度为(1+2)/2=1.5，即查找成功的关键字在哈希表中的位置与其在关键字序列中的位置相同，平均查找长度为1；查找失败的平均查找长度为(1+2+3)/3=2，即查找失败的关键字需要遍历哈希表中的两个桶，平均查找长度为2。

相关问题

用关键字序列{1，9，12，11，25，35，17，29}创建一个哈希表，装填因子a=1/2，确定表长m，采用除留余数法构造哈希函数，通过链地址法来处理冲突。 （1）求m的值； （2）画出哈希表； （2）求在等概率情况下，查找成功和查找失败的平均查找长度。

好的，这是一个关于哈希表的问题。首先，我们需要了解哈希表的概念和构造方法。

哈希表是一种数据结构，它通过哈希函数将关键字映射到表中的位置，以实现快速的查找、插入和删除操作。哈希函数的设计是哈希表的关键，它应该能够将关键字均匀地分布在表中，以最大程度地减少冲突。

在这个问题中，我们需要用关键字序列{1，9，12，11，25，35，17，29}创建一个哈希表，装填因子a=1/2，确定表长m，采用除留余数法构造哈希函数，通过链地址法来处理冲突。

首先，我们需要确定表长m。由于装填因子a=1/2，即每个位置平均存储两个关键字，因此表长m应该为关键字个数n除以装填因子a，再向上取整。即：

m = ceil(n/a) = ceil(8/(1/2)) = 16

接下来，我们需要构造哈希函数。采用除留余数法，即将关键字除以表长m，余数作为哈希地址。即：

h(key) = key % m

对于关键字序列{1，9，12，11，25，35，17，29}，它们的哈希地址分别为：

h(1) = 1 % 16 = 1
h(9) = 9 % 16 = 9
h(12) = 12 % 16 = 12
h(11) = 11 % 16 = 11
h(25) = 25 % 16 = 9
h(35) = 35 % 16 = 3
h(17) = 17 % 16 = 1
h(29) = 29 % 16 = 13
由于有冲突，我们需要采用链地址法来处理。即在哈希表中每个位置上维护一个链表，将哈希地址相同的关键字存储在同一个链表中。因此，我们需要画出哈希表，如下所示：

0
1 -> 1 -> 17
2
3 -> 35
4
5
6
7
8
9 -> 9 -> 25
10
11 -> 11
12 -> 12
13 -> 29
14
15

最后，我们需要求在等概率情况下，查找成功和查找失败的平均查找长度。由于采用链地址法处理冲突，平均查找长度可以分为两部分：查找哈希地址的平均长度和在链表中查找的平均长度。

对于查找哈希地址的平均长度，由于采用除留余数法，每个哈希地址的概率相等，因此平均查找长度为：

ASL1 = (1/m) * (1+2+3+...+n) = (1/m) * (n*(n+1)/2) = (1/16) * (8*9/2) = 2.25

对于在链表中查找的平均长度，由于关键字在链表中的位置是随机的，因此平均查找长度为：

ASL2 = (1/n) * (1+2+3+...+n) = (1/8) * (8*(8+1)/2) = 4.5

因此，查找成功的平均查找长度为：

ASL = ASL1 + ASL2 = 2.25 + 4.5 = 6.75

对于查找失败的平均查找长度，由于每个位置上都有一个空指针，因此平均查找长度为：

ASL = (1/m) * (1+2+3+...+m) = (1/16) * (16*(16+1)/2) = 8.5

用关键字序列{7，8，34，11，18，9，14，25}构造一个哈希表

构造哈希表的一般步骤：

1.选择哈希函数；
2.创建一个数组，大小为哈希表中预计的元素数量；
3.将每个关键字通过哈希函数转换为一个索引值，并将该值放入数组中对应的位置。

具体操作步骤如下：

1.选择哈希函数：采用简单的取模哈希函数 h(key) = key % n，其中 n 为数组大小；
2.创建一个大小为8的数组 table；
3.将关键字序列 {7, 8, 34, 11, 18, 9, 14, 25} 依次插入哈希表中：

- 7 % 8 = 7，将 7 存入 table[7] 中；
- 8 % 8 = 0，将 8 存入 table[0] 中；
- 34 % 8 = 2，将 34 存入 table[2] 中；
- 11 % 8 = 3，将 11 存入 table[3] 中；
- 18 % 8 = 2，发生冲突，采用开放地址法解决，将 18 存入 table[3+1] = table[4] 中；
- 9 % 8 = 1，将 9 存入 table[1] 中；
- 14 % 8 = 6，将 14 存入 table[6] 中；
- 25 % 8 = 1，发生冲突，采用线性探测法解决，将 25 存入 table[1+1] = table[2] 中。

最终的哈希表如下：

|table[0]|table[1]|table[2]|table[3]|table[4]|table[5]|table[6]|table[7]|
|--------|--------|--------|--------|--------|--------|--------|--------|
| 8 | 9 | 34 | 11 | 18 | | 14 | 7 |