hashtable - 封闭哈希算法的时间复杂度

Question

假设我们在 (4, 2, 12, 3, 9, 11, 7, 8, 13, 和 18) 上应用了紧密散列算法。并假设哈希表的长度最初为7 。在最坏的情况下，如何在O(1)时间内完成对此类哈希表的搜索。

Answer 1

你做什么真的不重要。因为数据集是预先确定的，所以对于任何散列函数（只要散列函数保证终止），最坏情况的查找都有一个恒定的上限。（如果找到一个元素比其他元素花费更长的时间，那就是上限。）恒定的上限意味着 O(1) 复杂度。QED。