设有一组关键字{9,1,23,14,55,20,84,27},采用哈希函数:H(key)=key mod 7 ,表长为10,用开放地址法的线性探测再散列方法解决冲突。要求:对该关键字序列构造哈希表。计算查找成功,失败的平均查找长度。 依次给出哈希表地址0--9单元的值。
时间: 2024-04-02 17:31:46 浏览: 88
首先,我们使用哈希函数 H(key) = key mod 7,将关键字映射到哈希表的0-6单元中。因为表长为10,所以我们需要对哈希表进行再散列,采用线性探测解决冲突,即如果第一次哈希的地址已经被占用,就尝试下一个地址,直到找到一个空闲的地址为止。
按照这个方法,我们可以得到以下哈希表:
|地址|关键字|
|---|---|
|0|20|
|1|55|
|2|9|
|3|1|
|4|23|
|5|14|
|6|27|
|7|84|
|8||
|9||
注意,这里我们使用了0-6单元,因为哈希函数的值域是0-6。
接下来,我们计算查找成功和失败的平均查找长度。
对于查找成功的情况,假设我们要查找关键字23。它的哈希值是23 mod 7 = 2,所以我们首先在哈希表的2号单元查找。因为23就在2号单元中,所以查找成功,平均查找长度为1。
对于查找失败的情况,假设我们要查找关键字30。它的哈希值是30 mod 7 = 2,所以我们首先在哈希表的2号单元查找。但是,2号单元中存储的是关键字9,而不是我们要查找的30。因此,我们需要继续向后查找,直到找到一个空闲的地址或者找到关键字30为止。在这个例子中,我们需要继续向后查找,直到找到8号单元或者9号单元才能确定关键字30没有被存储在哈希表中。因此,平均查找长度为(2+3+4)/3 = 3。
最后,哈希表地址0-9单元的值为:
|地址|关键字|
|---|---|
|0|20|
|1|55|
|2|9|
|3|1|
|4|23|
|5|14|
|6|27|
|7|84|
|8||
|9||
注意,8号和9号单元为空,因为哈希表长度为10,而哈希函数的值域是0-6。
阅读全文