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