#4027. [GESP202412 七级 C++] 第 9 题
[GESP202412 七级 C++] 第 9 题
一个哈希表,包括 n 个位置(分别编号 0~(n-1)),每个位置最多仅能存储一个元素。该哈希表只有插入元素和查询两种操作,没有删除或修改元素的操作。以下说法错误的是( )。
{{ select(1) }}
- 如果哈希函数取值范围为
0~(n-1),且当发生哈希函数碰撞时循环向后寻找空位,则查询操作的最差时间复杂度为 。(“循环向后”指:0向后一位为1,1向后一位为2,……,(n-2)向后一位为(n-1),(n-1)向后一位为0) - 如果哈希函数取值范围为
0~(n-1),且当发生哈希函数碰撞时仅循环向后一个位置寻找空位,则查询操作的最差时间复杂度为 。 - 如果哈希函数取值范围为
0~(m-1)(m < n),且当发生哈希函数碰撞时仅在m~(n-1)的范围内寻找空位,则查询操作的最差时间复杂度为 。 - 查询操作时,如果发现查询元素经哈希函数对应的位置为空位,该查询元素仍可能出现在哈希表内。