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