为什么在搜索密钥时只有O(1)时间的哈希表查找是O(n)？

从技术上讲,根据我在这里读到的帖子,哈希表在最坏的情况下确实是O(n)时间查找.但我不知道内部机制如何保证它平均为O(1)时间.

我的理解是,给定n个元素,理想情况是有n个桶,这导致O(1)空间.这就是我被困住的地方.假设我想查找一个键是否在字典中,这肯定需要O(n)时间.那么,当我想通过使用其键的哈希值来搜索元素是否在哈希表中时,为什么会有所不同呢？简而言之,使用原始键值进行搜索会得到O(n)时间,但使用哈希值时会得到O(1)时间.这是为什么？

难道我还不需要逐个查找哈希值来查看哪一个匹配？为什么哈希让我立即知道要检索哪个元素或者是否存在这样的元素？

我认为你会混淆术语,并且通过考虑桶来使问题复杂化.

让我们设想一个a以长度数组形式实现的哈希表n.让我们也可以想象,我们有n可能的密钥和一个完美的散列函数H,每个键映射k到一个唯一索引i在a.

让我们通过设置ato中的每个值来初始化我们的哈希表nil.

我们可以(k1, v1)通过将值放在数组中的适当位置,将键值对插入到哈希表中:

a[H(k1)] = v1

现在让我们说稍后我们忘记了是否k1在哈希表中,我们想检查它是否在那里.要做到这一点,我们只需查看a[H(k1)]并查看是否存在任何值,即a[H(k1)] != nil.这显然是一个恒定的时间查找.

但是,如果我们想要查看哈希表中是否有任何v1其他v2内容,甚至其他内容呢？这并不容易,因为我们没有将a映射vi到数组中的位置的函数.它可以与任何密钥相关联.因此,查看表中是否存在的唯一方法是扫描整个数组,检查每个值:

for i in 0..n-1:
  if a[i] == v2:
    return true
return false

为了使这一点更具体,想象你的钥匙是名字,你的价值观是居住的城市.现在比较问"哈希琼斯是否在哈希表中？" "哈希表中有没有来自纽约的人？" 我们可以散列"Bob Jones"并查看相应的数组位置是否有任何内容(因为这就是"Bob Jones"的插入方式),但我们没有类似的快速方式来查找"纽约".

我假设这是你要问的,你有点混淆术语.如果这不是你想要的,请评论.