设散列函数h(k)=k％13，散列表地址空间，对给定的一组关键序列为（19，14，01，68，20，84，27，26，50，36），用拉链法解决冲突构造散列表

使用散列函数 \( h(k) = k \mod 13 \)，我们将键值映射到13个哈希桶（因为取模13的结果范围是0到12）。对于给定的关键序列：

1. 对于键值19，\( h(19) = 19 \mod 13 = 6 \)。开始搜索第6个位置。
2. 14映射到 \( h(14) = 14 \mod 13 = 1 \)，发现14已经存在，需要处理冲突。我们创建一个拉链（链接）结构，在第1个位置添加一个链表。
3. 01映射到 \( h(01) = 1 \)（忽略前导零），同样发现冲突，将它加到第1个链表。
4. 68映射到 \( h(68) = 6 \)，在第6个位置插入。
5. 20映射到 \( h(20) = 7 \)，找到空位插入。
6. 84映射到 \( h(84) = 1 \)，再次冲突，加入到第1个链表。
7. 27映射到 \( h(27) = 4 \)，插入第4个位置。
8. 26映射到 \( h(26) = 3 \)，插入第3个位置。
9. 50映射到 \( h(50) = 10 \)，插入第10个位置。
10. 36映射到 \( h(36) = 5 \)，插入第5个位置。

最终的散列表会是这样的，每个数字表示对应桶的位置，链表包含冲突的元素：

[ ] [01, 14] [20] [6] [36] [10, 50] [4, 27] [26]

相关问题

设有一组关键字{29,01,13,15,56,20,87,27,69,9,10,74},散列函数为：H(key)=key % 17,采用线性测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表，并计算成功查找的平均查找度。手写过程

### 回答1：
首先，我们需要将关键字序列通过散列函数映射到散列表中。根据题目给出的散列函数H(key)=key % 17，我们可以得到以下散列地址：

- H(29) = 12
- H(01) = 1
- H(13) = 13
- H(15) = 15
- H(56) = 5
- H(20) = 3
- H(87) = 4
- H(27) = 10
- H(69) = 4
- H(9) = 9
- H(10) = 10
- H(74) = 8

可以看到，有两个关键字（87和69）映射到了同一个散列地址4上，这就是冲突。

接下来，我们采用线性探测法解决冲突。具体来说，当关键字key映射到散列地址i上时发生冲突，我们就依次检查散列地址i+1，i+2，i+3……，直到找到一个空闲的散列地址为止。这里需要注意的是，我们在检查下一个散列地址时需要使用散列函数重新计算，即H(i+1)，H(i+2)，H(i+3)……。

下面是具体的构造过程：

- 将关键字29映射到散列地址12，放置关键字29。
- 将关键字01映射到散列地址1，放置关键字01。
- 将关键字13映射到散列地址13，放置关键字13。
- 将关键字15映射到散列地址15，放置关键字15。
- 将关键字56映射到散列地址5，放置关键字56。
- 将关键字20映射到散列地址3，放置关键字20。
- 发现关键字87映射到散列地址4时发生冲突，依次检查散列地址5、6、7、8、9、10、11、12、13、14、15、16、0、1、2，发现散列地址9是空闲的，将关键字87放置在散列地址9上。
- 将关键字27映射到散列地址10，放置关键字27。
- 发现关键字69映射到散列地址4时再次发生冲突，依次检查散列地址5、6、7、8、9、10、11、12、13、14、15、16、0、1、2，发现散列地址11是空闲的，将关键字69放置在散列地址11上。
- 将关键字9映射到散列地址9，放置关键字9。
- 发现关键字10映射到散列地址10时发生冲突，依次检查散列地址11、12、13、14、15、16、0、1、2、3、4、5、6、7、8，发现散列地址0是空闲的，将关键字10放置在散列地址0上。
- 将关键字74映射到散列地址8，放置关键字74。

现在，我们已经成功构造了散列表。下面计算平均查找度。假设查找一个关键字时，需要检查k个散列地址（包括散列地址本身），则成功查找的平均查找度为：

平均查找度 = (1/12)*(1+1+1+1+1+1+3+1+2+1+1+1) = 1.25

因此，成功查找的平均查找度为1.25。

### 回答2：
首先，“散列函数为：H(key)=key % 17”表示散列函数将关键字除以17取余数作为散列地址。

根据线性探测法，当出现冲突时，依次尝试下一个散列地址，直到找到空闲的地址为止。

我们可以按照以下步骤进行构造散列表：

1. 创建一个长度为 19 的数组（0 到 18），用于存储关键字。
2. 将关键字序列逐个进行散列，并插入到对应的散列地址中。
- 将关键字 29 散列到 12 号地址（29%17=12）。
- 将关键字 01 散列到 1 号地址（1%17=1）。
- 将关键字 13 散列到 13 号地址（13%17=13）。
- 将关键字 15 散列到 15 号地址（15%17=15）。
- 将关键字 56 散列到 5 号地址（56%17=5）。
- 将关键字 20 散列到 3 号地址（20%17=3）。
- 将关键字 87 散列到 4 号地址（87%17=4）。
- 将关键字 27 散列到 10 号地址（27%17=10）。
- 将关键字 69 散列到 18 号地址（69%17=1）（出现冲突，尝试下一个地址，然后再次冲突，依次尝试下一个地址，直到找到空闲地址）。
- 将关键字 9 散列到 9 号地址（9%17=9）。
- 将关键字 10 散列到 10 号地址（10%17=10）（出现冲突，尝试下一个地址）。插入到 11 号地址（11%17=11）。
- 将关键字 74 散列到 7 号地址（74%17=7）（出现冲突，依次尝试下一个地址，直到找到空闲地址）。

散列表为：[ ,01 , ,15 ,87 ,20 , ,74 , , ,29 , ,13 , ,56 , , ,69 , ,10 ]。

3. 计算成功查找的平均查找度。即，对所有关键字进行查找，计算查找每个关键字时需要查找的次数，并求平均值。
- 查找关键字 29，需要查找 1 次。
- 查找关键字 01，需要查找 1 次。
- 查找关键字 13，需要查找 1 次。
- 查找关键字 15，需要查找 1 次。
- 查找关键字 56，需要查找 1 次。
- 查找关键字 20，需要查找 1 次。
- 查找关键字 87，需要查找 1 次。
- 查找关键字 27，需要查找 2 次。
- 查找关键字 69，需要查找 1 次。
- 查找关键字 9，需要查找 1 次。
- 查找关键字 10，需要查找 2 次。
- 查找关键字 74，需要查找 1 次。

总共查找次数为 13 次，平均查找次数为 13/12 ≈ 1.083 次。

注：由于散列函数本身的性质以及关键字的选取，可能会导致冲突的发生，而线性探测法可能会出现聚集的问题，即多个关键字在散列表中相邻的位置，这会影响到散列表的性能。因此，在实际应用中，需要根据具体情况选择合适的散列函数和解决冲突的方法。

### 回答3：
首先，根据给定的散列函数H(key)=key % 17，将关键字序列依次计算散列地址：

29 % 17 = 12
01 % 17 = 1
13 % 17 = 13
15 % 17 = 15
56 % 17 = 5
20 % 17 = 3
87 % 17 = 3
27 % 17 = 10
69 % 17 = 1
9 % 17 = 9
10 % 17 = 10
74 % 17 = 8

然后，根据线性探测方法处理冲突，从散列地址为12的位置开始向后探测，直到找到一个空的位置：

12：29 13：13 14： 15：15 16： 17： 18：
3：20
10：27 11： 12： 13： 14： 15： 16：
0：01
1：69
2：15
3：87
4： 5：56
6：
7： 8：74
9：9

依次将关键字插入散列表中，直到所有关键字都插入完毕。

成功查找的平均查找度计算如下：
查找度为线性探测过程中查找到的位置与实际应该存放的位置之间的距离。
对于每个关键字来说，总共有17个散列地址，我们可以将距离加起来再除以17，得到平均查找度。

29的查找度：0
01的查找度：1（69的实际位置-69的散列地址）
13的查找度：0
15的查找度：0
56的查找度：0
20的查找度：4（20的实际位置-20的散列地址）
87的查找度：0
27的查找度：3（10的实际位置-10的散列地址）
69的查找度：0
9的查找度：0
10的查找度：0
74的查找度：0

总查找度：0 + 1 + 0 + 0 + 0 + 4 + 0 + 3 + 0 + 0 + 0 + 0 = 8

平均查找度：总查找度 / 关键字个数 = 8 / 12 = 0.67

所以成功查找的平均查找度为0.67。