#4027. [GESP202412 七级 C++] 第 9 题

[GESP202412 七级 C++] 第 9 题

一个哈希表,包括 n 个位置(分别编号 0~(n-1)),每个位置最多仅能存储一个元素。该哈希表只有插入元素和查询两种操作,没有删除或修改元素的操作。以下说法错误的是( )。

{{ select(1) }}

  • 如果哈希函数取值范围为 0 ~ (n-1),且当发生哈希函数碰撞时循环向后寻找空位,则查询操作的最差时间复杂度为 O(n)O(n)。(“循环向后”指:0 向后一位为 11 向后一位为 2,……,(n-2) 向后一位为 (n-1)(n-1) 向后一位为 0
  • 如果哈希函数取值范围为 0 ~ (n-1),且当发生哈希函数碰撞时仅循环向后一个位置寻找空位,则查询操作的最差时间复杂度为 O(1)O(1)
  • 如果哈希函数取值范围为 0 ~ (m-1)m < n),且当发生哈希函数碰撞时仅在 m ~ (n-1) 的范围内寻找空位,则查询操作的最差时间复杂度为 O(nm)O(n-m)
  • 查询操作时,如果发现查询元素经哈希函数对应的位置为空位,该查询元素仍可能出现在哈希表内。