为什么在评估散列函数时散列查找的成本可能比这花费更多时间？

Question

HashMap（或）HashTable 是键控数组的一个示例。这里，索引是用户定义的键而不是通常的索引号。例如，arr["first"]=99是一个哈希映射的示例，其中 b 键为第一个，值为 99。

由于使用了键，因此需要哈希函数将键转换为索引元素，然后在数组中插入/搜索数据。此过程假设不存在冲突。

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

Answer 1

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

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

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

也许计算哈希表中查找成本的最佳方法是说它是 O(T _hash + T _eq )，其中 T _hash是对元素进行哈希处理所需的时间，T _eq是对元素进行哈希处理所需的时间。比较表中的两个元素。例如，对于字符串，您可以说查找的预期成本为 O(L + L _max )，其中 L 是要散列的字符串的长度，L _max是存储在哈希表。

希望这可以帮助！