将关键字序列 { 7,8,30,11,18,9,14 },散列存储到散列列表中,散列表的存储空间是一

散列表的存储空间是一组连续的存储单元，通常用数组来实现。散列存储是根据关键字直接进行访问的存储方式，因此需要将关键字进行哈希处理，将其转换为散列地址。具体实现过程中，可以使用哈希函数将关键字转换为散列地址，然后将关键字存储到对应的散列表中。对于给定的关键字序列 { 7,8,30,11,18,9,14 }，可以使用哈希函数将每个关键字转换为散列地址，然后将其存储到散列表中。具体的实现方法和哈希函数选择，需要根据具体的应用场景和性能需求进行选择。

相关问题

将关键字序列{7，8，30，11，18，9，14}散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组散列，函数为：H（key）-（key

% 5），其中H（key）表示关键字key的散列地址。请问这些关键字在散列表中的存储位置是怎样的？

首先，对于每一个关键字key，我们需要通过散列函数H(key)计算出它的散列地址。根据给定的散列函数H(key) = key % 5，我们可以得到每个关键字的散列地址：

- key=7，H(7) = 7 % 5 = 2
- key=8，H(8) = 8 % 5 = 3
- key=30，H(30) = 30 % 5 = 0
- key=11，H(11) = 11 % 5 = 1
- key=18，H(18) = 18 % 5 = 3
- key=9，H(9) = 9 % 5 = 4
- key=14，H(14) = 14 % 5 = 4

接下来，我们需要将每个关键字存储到散列表中。由于散列表是一个下标从0开始的一维数组，因此我们可以将每个关键字存储到对应的数组下标中。根据上面计算出的散列地址，我们可以将每个关键字存储到如下位置：

- key=7，存储到数组下标2的位置
- key=8，存储到数组下标3的位置
- key=30，存储到数组下标0的位置
- key=11，存储到数组下标1的位置
- key=18，存储到数组下标3的下一个空闲位置，即数组下标4的位置
- key=9，存储到数组下标4的下一个空闲位置，即数组下标5的位置
- key=14，存储到数组下标4的下一个空闲位置，即数组下标6的位置

最终，这些关键字在散列表中的存储位置如下：

| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 值 | 30 | 11 | 7 | 8 | 18 | 9 | 14 |

注意，由于散列表的存储空间是有限的，因此可能会出现关键字散列到同一个地址的情况，这种情况称为散列冲突。在这个问题中，我们没有考虑散列冲突的情况，实际应用中需要使用合适的散列函数以及解决冲突的方法来保证散列表的效率和正确性。

将关键字序列 { 7，8，30，11，18，9，14 }，散列存储到散列列表中，散列表的存储空间是一个下标从 0 开始的一维数组。处理冲突采用线性探测法。散列函数为 h(key)=(key×3)% 表长，要求装入因子为 0.7。则成功查找的平均查找长度为 __

### 回答1：
根据装入因子为.7，散列表的长度应该为10，即能存储7个关键字。

散列函数为h(key)=(key×3)%表长，将关键字序列散列存储到散列列表中：

h(7)=(7×3)%10=1，散列到下标为1的位置

h(8)=(8×3)%10=4，散列到下标为4的位置

h(30)=(30×3)%10=，散列到下标为的位置

h(11)=(11×3)%10=3，散列到下标为3的位置

h(18)=(18×3)%10=4，发生冲突，线性探测到下标为5的位置

h(9)=(9×3)%10=7，散列到下标为7的位置

h(14)=(14×3)%10=2，散列到下标为2的位置

散列列表为：{30, 7, 14, 11, 18, 9, 8, null, null, null}

成功查找的平均查找长度为：

(1×1 + 4×1 + ×1 + 3×1 + (4+1)×1 + 7×1 + 2×1) / 7 = 3

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

### 回答2：
将关键字序列 { 7，8，30，11，18，9，14 } 散列存储到散列列表中，需要先确定散列表的大小，以便计算装入因子。根据题目要求，采用线性探测法，散列函数为 h(key)=(key×3)%表长，可知表长为：

表长 = 散列成功存储关键字的数量 / 装入因子
表长 = ceil(7 / 0.7)
表长 = 10

于是散列表的空间就是一个下标从 0 开始，长度为 10 的一维数组。

现在开始散列存储。对于每个关键字，先计算出其散列地址，如果该地址已经被占用，就采用线性探测法在散列表中依次向后查找，直到找到空位置为止。具体操作如下：

1. 将 7 存储到散列表中，计算其散列地址为 h(7) = (7×3) % 10 = 1，将其存储到下标为 1 的位置处；
2. 将 8 存储到散列表中，计算其散列地址为 h(8) = (8×3) % 10 = 4，将其存储到下标为 4 的位置处；
3. 将 30 存储到散列表中，计算其散列地址为 h(30) = (30×3) % 10 = 0，将其存储到下标为 0 的位置处；
4. 将 11 存储到散列表中，计算其散列地址为 h(11) = (11×3) % 10 = 7，将其存储到下标为 7 的位置处；
5. 将 18 存储到散列表中，计算其散列地址为 h(18) = (18×3) % 10 = 4，由于下标为 4 的位置已经被占用，采用线性探测法，依次查找下标为 5、6、7、8、9 的位置，直到找到空位置下标为 2，将其存储到下标为 2 的位置处；
6. 将 9 存储到散列表中，计算其散列地址为 h(9) = (9×3) % 10 = 7，由于下标为 7 的位置已经被占用，采用线性探测法，依次查找下标为 8、9、0、1 的位置，由于这些位置都被占用，将会回到起始位置，继续查找下标为 2、3、4 的位置，最终找到下标为 3 的空位置，将其存储到下标为 3 的位置处；
7. 将 14 存储到散列表中，计算其散列地址为 h(14) = (14×3) % 10 = 2，将其存储到下标为 2 的位置处。

现在散列表中的数据为：

0: 30
1: 7
2: 14
3: 9
4: 8
5:
6:
7: 11
8:
9: 18

其中空位置用空格表示。

接下来计算成功查找的平均查找长度。对于每个关键字的查找，从其散列地址开始，依次查找散列表中的位置，直到找到该关键字或者找到一个空位置。假设每个关键字的查找次数为 x，那么成功查找的平均查找长度为所有关键字的查找次数之和除以成功查找的关键字数目。即：

成功查找的平均查找长度 = 所有关键字的查找次数之和 / 成功查找的关键字数目

现在依次对每个关键字进行查找：

1. 查找 7，其散列地址为 1，查找次数为 1；
2. 查找 8，其散列地址为 4，查找次数为 1；
3. 查找 30，其散列地址为 0，查找次数为 1；
4. 查找 11，其散列地址为 7，由于下标为 7 的位置存储的是 9，于是向下查找，查找到下标为 8 的位置为空，查找次数为 2；
5. 查找 18，其散列地址为 4，由于下标为 4 的位置存储的是 8，于是向下查找，查找到下标为 5 的位置为空，查找次数为 2；
6. 查找 9，其散列地址为 7，查找次数为 1；
7. 查找 14，其散列地址为 2，查找次数为 1。

所有关键字的查找次数之和为：1 + 1 + 1 + 2 + 2 + 1 + 1 = 9

成功查找的关键字数目为 7，因为散列表中共有 7 个关键字。因此，成功查找的平均查找长度为：

成功查找的平均查找长度 = 所有关键字的查找次数之和 / 成功查找的关键字数目
成功查找的平均查找长度 = 9 / 7
成功查找的平均查找长度 ≈ 1.29

因此，成功查找的平均查找长度为约 1.29。

### 回答3：
散列存储是一种通过散列函数将数据存储到一定范围内的连续地址上，以提高数据访问速度的存储方式。将关键字序列 { 7，8，30，11，18，9，14 } 散列存储到散列列表中，散列表的存储空间是一个下标从 0 开始的一维数组。处理冲突采用线性探测法。散列函数为 h(key)=(key×3)%表长，要求装入因子为 0.7。则成功查找的平均查找长度为：

1. 计算表长
由于要求装入因子为 0.7，故需要表长为（7/0.7=10）。所以，散列表的存储空间为一个长度为 10 的一维数组。

2. 散列存储
根据散列函数，计算关键字在散列表中的存储地址：
h(7) = (7×3) % 10 = 1
h(8) = (8×3) % 10 = 4
h(30) = (30×3) % 10 = 0
h(11) = (11×3) % 10 = 9
h(18) = (18×3) % 10 = 6
h(9) = (9×3) % 10 = 7
h(14) = (14×3) % 10 = 2

然后，将关键字序列 { 7，8，30，11，18，9，14 } 散列存储到散列表中：
[30, 7, 14, 11, 18, 8, 9, _, _, _]
下划线表示空闲单元格。

3. 查找关键字
假设要查找的关键字为 18，其散列地址为 6。在散列表中的单元格 6 已经存储了关键字 18。查找成功，平均查找长度为 1。

4. 成功查找的平均查找长度
根据线性探测法，平均查找长度为 1/(1-α/2)。其中，α=装入因子=7/10=0.7。带入公式，可得：
平均查找长度 = 1 / (1-0.7/2) = 1 / 0.65 ≈ 1.538

故，成功查找的平均查找长度为约 1.538。