当评估哈希函数可能需要更长时间时，为什么哈希查找的成本是O（1）？

Question

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

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

现在，给定要在数组中搜索的键，如果存在，则必须获取数据。因此，每次搜索之前，必须将键转换为数组的索引号。那么如何在O(1)时间内完成呢？因为时间复杂度也取决于哈希函数。因此，时间复杂度必须是O(hashing function's time)。

- Java Enthusiast

---

哈希函数的时间被假定为恒定的。 - BeyelerStudios

因为通常字符串的哈希值不取决于整个字符串，而仅仅是它的前/后 O(1) 个字节，所以 O(hashing function's time)=O(1)。 - Egor Skriptunoff

https://dev59.com/q2865IYBdhLWcg3wLbar 和 https://dev59.com/fFnUa4cB1Zd3GeqPdbwe 和 http://cs.stackexchange.com/questions/249/when-is-hash-table-lookup-o1 - Amirhossein Mehrvarzi

@EgorSkriptunoff 不，这不是原因：相对较短的字符串哈希工作与大量工作N（映射中的条目数）相比随着N->inf而减少 - 即如果字符串键的长度受到k的限制，则哈希任何键都是恒定的。 - BeyelerStudios

可能是哈希表真的可以是O（1）吗？的重复。 - DavidRR

Answer 1

谈到哈希时，通常通过讨论在表中搜索元素时需要进行的期望探测次数来衡量哈希表的性能。在大多数哈希设置中，我们可以证明期望探测次数为O(1)。通常情况下，我们会从这里跳跃到“哈希表查找的期望运行时间为O(1)”。但是，并非总是如此。正如你所指出的，计算特定输入的哈希函数的成本可能并不总是需要O(1)时间。同样地，比较哈希表中的两个元素的成本也可能不需要O(1)时间。例如，考虑哈希字符串或列表。

尽管如此，通常情况下以下内容是正确的。如果我们将表中的元素总数设为n，则可以说，在哈希表中执行查找的期望成本与数字n无关。也就是说，无论哈希表中有100万个元素还是10^100个元素，平均探测次数都是相同的。因此，我们可以说，在哈希表大小作为一个函数时，在哈希表中执行查找的期望成本为O(1)，因为执行查找的成本不取决于表大小。

也许最好的方法是考虑哈希表查找的成本为O(T_hash + T_eq)，其中T_hash是哈希元素所需的时间，T_eq是比较哈希表中的两个元素所需的时间。例如，对于字符串，可以说查找的期望成本为O(L + L_max)，其中L是您要哈希的字符串的长度，L_max是存储在哈希表中的最长字符串的长度。

希望这有所帮助！

- templatetypedef

---

我理解如果L很大，T_hash可能会非常重要，但是我认为一个好的哈希表实现不会在查找期间仅进行字符串比较，而是进行哈希比较。我认为存储在哈希表中的字符串的长度不应该影响其性能。 - Albino Cordeiro

@AlbinoCordeiro 在某个时候，您必须比较字符串本身，否则，如果您有一个与表中另一个字符串具有真正哈希冲突的字符串，则会错误地报告该字符串存在，即使它实际上不存在。 - templatetypedef