首先,确定哈希表的大小,根据装填因子为0.7,可得哈希表的大小为10(即7/0.7)。

然后,根据哈希函数H(key)=(key×3) mod 7,将关键字序列中的每个元素插入到哈希表中。如果发生冲突,则采用线性探测法,即从当前位置开始,依次向后查找空闲位置,直到找到为止。

具体的哈希表构造过程如下:

  1. 初始化一个大小为10的一维数组,全部置为-1,表示空闲位置。

哈希表:[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

  1. 将关键字序列中的第一个元素7插入哈希表中。根据哈希函数H(7)=(7×3) mod 7=0,可得插入位置为0。

哈希表:[7, -1, -1, -1, -1, -1, -1, -1, -1, -1]

  1. 将关键字序列中的第二个元素8插入哈希表中。根据哈希函数H(8)=(8×3) mod 7=4,可得插入位置为4。

哈希表:[7, -1, -1, -1, 8, -1, -1, -1, -1, -1]

  1. 将关键字序列中的第三个元素30插入哈希表中。根据哈希函数H(30)=(30×3) mod 7=2,可得插入位置为2。

哈希表:[7, -1, 30, -1, 8, -1, -1, -1, -1, -1]

  1. 将关键字序列中的第四个元素11插入哈希表中。根据哈希函数H(11)=(11×3) mod 7=5,可得插入位置为5。

哈希表:[7, -1, 30, -1, 8, 11, -1, -1, -1, -1]

  1. 将关键字序列中的第五个元素18插入哈希表中。根据哈希函数H(18)=(18×3) mod 7=6,可得插入位置为6。

哈希表:[7, -1, 30, -1, 8, 11, 18, -1, -1, -1]

  1. 将关键字序列中的第六个元素9插入哈希表中。根据哈希函数H(9)=(9×3) mod 7=6,由于位置6已经被占用,需要进行线性探测。从位置7开始,依次向后查找,直到找到空闲位置为止,可得插入位置为8。

哈希表:[7, -1, 30, -1, 8, 11, 18, -1, 9, -1]

  1. 将关键字序列中的第七个元素14插入哈希表中。根据哈希函数H(14)=(14×3) mod 7=0,由于位置0已经被占用,需要进行线性探测。从位置1开始,依次向后查找,直到找到空闲位置为止,可得插入位置为3。

哈希表:[7, -1, 30, 14, 8, 11, 18, -1, 9, -1]

最终得到的哈希表如上所示。

线性探测法构造哈希表:关键字序列{7, 8, 30, 11, 18, 9, 14}实例

原文地址: https://www.cveoy.top/t/topic/oto1 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录