设哈希表的长度m=12,哈希函数H(key)= key % 11,关键字序列为(9,31,26,24,19, 1,12,27,16,13),采用线性探测法解决冲突,请对该关键字序列构造哈希表。
时间: 2024-03-29 10:39:00 浏览: 69
好的,我来帮您解决这道题目。
根据题目所给条件,我们可以得到哈希函数: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中。
希望这个例子能够帮助您更好地理解哈希表的构造过程。
相关问题
关键字序列{23,35,12,56,123,39,342,90,78,110},按照哈希函数 h(key)=key%13 和链地址法处理冲突,请画出其哈希表的结构
根据给定的哈希函数 h(key) = key % 13 和链地址法处理冲突,我们可以画出哈希表的结构如下:
哈希表:
0 -> 78 -> NULL
1 -> NULL
2 -> 90 -> NULL
3 -> 23 -> 123 -> 39 -> NULL
4 -> 342 -> NULL
5 -> 35 -> NULL
6 -> 56 -> NULL
7 -> NULL
8 -> NULL
9 -> NULL
10 -> NULL
11 -> NULL
12 -> 12 -> NULL
解释:
- 关键字序列中的每个元素通过哈希函数计算得到对应的哈希值,然后将其插入到哈希表中。
- 如果发生冲突,即两个元素计算得到的哈希值相同,采用链地址法处理冲突,即在哈希表中的对应位置上使用链表存储冲突的元素。
- 哈希表中的每个位置都指向一个链表,链表中存储了具有相同哈希值的元素。
已知一组关键字序列为{5,88,12,56,71,28,33,43,93,17},哈希表长为13,哈希函数为h(key)=key%13,请用线性探测再散列、二次线性探测再散列以及链地址法解决冲突构造这组关键字的哈希表,并计算查找成功时的平均查找长度。
线性探测再散列:
哈希表长为13,哈希函数为h(key)=key%13。
插入关键字序列{5,88,12,56,71,28,33,43,93,17},得到哈希表为:
: 71
1: 12
2: 93
3: 33
4: 43
5: 5
6: 56
7: 28
8: 17
9: 88
10:
11:
12:
查找成功时的平均查找长度为(1+2+3+4+5+6+7+8+9+10)/10=5.5。
二次线性探测再散列:
哈希表长为13,哈希函数为h(key)=key%13。
插入关键字序列{5,88,12,56,71,28,33,43,93,17},得到哈希表为:
: 71
1: 12
2: 93
3: 33
4: 43
5: 5
6: 56
7: 28
8: 17
9: 88
10:
11:
12:
查找成功时的平均查找长度为(1+2+4+7+11+3+8+12+9+5)/10=6。
链地址法:
哈希表长为13,哈希函数为h(key)=key%13。
插入关键字序列{5,88,12,56,71,28,33,43,93,17},得到哈希表为:
:
1: 71
2: 12
3: 33 -> 93
4: 43
5: 5
6: 56
7: 28
8: 17
9: 88
10:
11:
12:
查找成功时的平均查找长度为(1+1+2+1+1+1+1+1+1+1)/10=1。
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)