hash - 为什么在评估散列函数时散列查找的成本 O(1) 可能需要更多的时间？

Question

HashMap(或)HashTable 是 的一个例子键控 大批。在这里，索引是用户定义的键而不是通常的索引号。例如，arr["first"]=99是一个哈希映射的例子，其中 theb 键是 第一 并且值为 99。

由于使用了键，因此需要使用散列函数将键转换为索引元素，然后在数组中插入/搜索数据。这个过程假设有没有碰撞 .

现在，给定要在数组中搜索的键，如果存在，则必须获取数据。因此，每次搜索之前，必须将键转换为数组的索引号。那么这需要 O(1) 时间吗？因为，时间复杂度也取决于散列函数。所以时间复杂度一定是O(散列函数的时间)。

Answer 1

在谈论散列时，我们通常通过谈论在表中搜索元素时需要进行的预期探测次数来衡量哈希表的性能。在大多数散列设置中，我们可以证明预期的探测数量是 O(1)。通常，我们然后从那里跳转到“因此哈希表查找的预期运行时间是 O(1)”。

然而，情况并非一定如此。正如您所指出的，在特定输入上计算散列函数的成本可能并不总是需要时间 O(1)。类似地，比较哈希表中两个元素的成本也可能不需要时间 O(1)。例如，考虑散列字符串或列表。

也就是说，通常正确的是以下内容。如果我们让表中元素的总数为 n，我们可以说执行查找哈希表的预期成本与数量 n 无关。也就是说，哈希表中有 1,000,000 个元素还是 10100 个元素并不重要——您需要证明的点数平均而言是相同的。因此，我们可以说在哈希表中执行查找的预期成本(作为哈希表大小的函数)是 O(1)，因为执行查找的成本不取决于表大小。

也许考虑在哈希表中查找的成本的最好方法是说它是 O(Thash + Teq)，其中 Thash 是散列元素所需的时间，Teq 是比较两个元素所需的时间 table 。例如，对于字符串，您可以说查找的预期成本为 O(L + Lmax)，其中 L 是您正在散列的字符串的长度，而 Lmax 是存储在哈希表中的最长字符串的长度.

希望这可以帮助!