用哈希函数 H(key)=key%17 将具有关键字 15、80、100、88、23、45、93、50、20、10、28、44、99、21、66 的一组元素映射到长度为 17 的哈希表中,冲突时采用线性探测再散列的方法,试画出这组元素在哈希表中的存储情况。
时间: 2023-09-29 20:06:55 浏览: 58
首先,我们需要创建一个长度为17的哈希表。这里我们用H(key)%17的结果来确定元素在哈希表中的位置。
```
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
```
接下来,我们将每个元素插入到哈希表中。如果遇到冲突,我们采用线性探测再散列的方法,即继续寻找下一个可用的位置。
```
key: 15 80 100 88 23 45 93 50 20 10 28 44 99 21 66
index: 15 13 15 4 6 11 9 0 3 10 12 1 15 2 8
```
最终,这组元素在哈希表中的存储情况如下:
```
0: 50
1: 44
2: 21
3: 20
4: 88
5:
6: 45
7:
8: 66
9: 93
10: 10
11: 28
12: 99
13: 80
14:
15: 15, 100, 23
16:
```
相关问题
数据结构实验之查找七:线性之哈希表\ndescription\n根据给定的一系列整数关键字和素数p,用除留余数法定义hash函数h(key)=key%p,将关键字映射到长度为p的哈希表中,用线性探测法解决
这道题目要求使用哈希表实现一个线性探测法解决哈希表冲突的哈希表。给定一个关键字和一个素数p,哈希函数使用余数法h(key)=key%p进行映射。冲突解决方法则是使用线性探测法,即将关键字映射到哈希表中的位置,如果这个位置已经被占用,则往后顺延,直到找到一个空位置插入关键字。题目要求实现这个数据结构并进行测试。
设哈希表的长度m=12,哈希函数H(key)= key % 11,关键字序列为(9,31,26,24,19, 1,12,27,16,13),采用线性探测法解决冲突,请对该关键字序列构造哈希表。
好的,我来帮您解决这道题目。
根据题目所给条件,我们可以得到哈希函数:H(key) = key % 11,即key对11取模。
接下来,我们可以按照以下步骤构造哈希表:
1. 初始化一个长度为12的哈希表,全部元素设为-1,表示该槽位为空。
2. 对于关键字序列中的每一个元素,计算其哈希值,即H(key)。
3. 如果哈希表中该槽位为空,将该元素插入到该槽位中,否则进行线性探测,直到找到一个空的槽位。
4. 线性探测的方式为:从当前槽位开始,一直往后遍历哈希表,直到找到一个空的槽位或者遍历了整个哈希表。如果找到了空槽位,则插入该元素;如果遍历了整个哈希表,那么从头开始重新遍历,直到找到一个空的槽位为止。
根据上述步骤,我们可以得到完整的哈希表构造过程如下:
|索引|关键字|
|---|---|
|0|19|
|1|1|
|2|31|
|3|12|
|4|13|
|5|24|
|6|26|
|7|27|
|8|16|
|9|9|
|10|-1|
|11|-1|
其中,-1表示空槽位。
注意,这里我们采用了线性探测的方式解决冲突,因此有些元素并不是按照哈希函数计算出来的哈希值所对应的槽位存储的。例如,关键字9的哈希值为9,但是由于槽位0已经被关键字19占用了,因此它被插入到了槽位9中。
希望这个例子能够帮助您更好地理解哈希表的构造过程。