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

EN

我认为你混淆了术语，也因为思考桶而使事情复杂化。

让我们设想一个哈希表，它是作为长度为a的n数组实现的。让我们想象一下，我们有n可能的键和一个完美的哈希函数H，它将每个键k映射到a中的唯一索引i。

让我们通过将a中的每个值设置为nil来初始化哈希表。

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

a[H(k1)] = v1

现在，假设稍后我们忘记了k1是否在哈希表中，我们希望检查它是否存在。要做到这一点，我们只需查找a[H(k1)]并查看是否存在任何值，即a[H(k1)] != nil。这显然是一个固定时间的查找。

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

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

为了使这更具体一点，假设你的钥匙是名字，你的价值观是居住的城市。现在比较一下“鲍勃琼斯在哈希表中吗？”“在散列表里有纽约人吗？”我们可以散列"Bob“，并查看相应的数组位置中是否有任何内容(因为"Bob”就是这样插入的)，但是我们没有类似的快速查找"New York“的方法。

我假设这就是你要问的，你把术语搞混了。如果这不是你想要的，请评论。

听起来你在寻找更详细的解释！

假设您已经了解到数组元素查找需要O(1)，也就是说，如果我已经知道我想在数组中查找第100个元素，那么它只需要O(1)，因为这是一个简单的内存地址查找(通过将100添加到第一个元素的地址)。

散列方法利用这种内存地址查找来实现O(1)平均时间。显然，这意味着您需要能够将查找键转换为内存地址。让我给出一个非常简单的例子，说明这是如何在哈希表中工作的(为了清楚起见，字典在引擎盖下实现了hashtable，所以当我提到hashtable时，同样的原则也适用于字典)。

简化的示例场景；我们需要根据客户的名字查找他们的邮件地址。为了简单起见，假设名称是唯一的，并且它们有普通的a到z字母。假设我们最初只为10个客户设计(即他们的名字和地址)。

现在让我们说，我们必须通过在哈希表中存储名称-地址对来解决这个问题，并且我们必须创建我们自己的散列函数！一个哈希函数，它以名称作为参数并将其转换为内存查找！

现在花点时间想想这里需要多少个数组？他们的类型是什么，他们的大小是什么？

我们肯定需要一个数组来存储邮件地址。尺寸应该是多少？嗯，我们需要存储10个邮件地址，所以大小必须是10！我们还需要第二个数组来存储第一个数组的元素索引！！换句话说，我们需要第二个数组来为我们的客户名称存储对邮件地址(来自第一个数组)的引用。这个数组的大小应该是多少？绝对大于10！但这真的取决于我们设计的哈希函数。为了简单起见，让我们创建一个散列函数，它只接受name参数的第一个字母，并将其转换为索引。也就是说，如果名称从A开始，那么它的哈希值是1，b是2，c是3.Z是26。因此，至少我们的查找数组大小必须为26 (您一定认为这是存储10个地址的大量空间的浪费！！但这可能是值得的，因为它将给我们提供性能)，让我们试着用一个例子来理解这一点。假设我们的第一个顾客名叫鲍勃。要存储Bob的地址，第一步是在邮件地址数组中找到第一个空元素。这是名字，所以整个邮件地址数组都是空的。我们可以将Bob的地址存储在索引0的邮件地址数组中。当我们存储这个地址时，我们也会在索引0处将它标记为Bob的地址。(我使用这个“标记”术语来解释查找和搜索)，然后我们找出名字Bob的哈希值。在这种情况下，应该是2！因此，在位置2的查找数组中，我们存储0。(即Bob的邮件地址索引)。现在假设我们的第二个客户是Hamish；我们将Hamish的邮件地址存储在邮件地址数组中的索引1(即第二个元素)；将其标记为Hamish的地址，然后查找Hamish的哈希值。由于Hamish从‘H’开始，值将为8。因此，在位置8的查找数组中，我们存储值1(即Hamish地址的索引)。我们可以对所有10个客户重复这一过程，并存储他们的地址。现在，当您想要查找Bob的地址时，只需遵循一个简单的两步过程，就可以非常快地查找它。步骤1-将名称Bob转换为哈希值；回答为2；继续检查邮件地址数组中的位置2；如果它被标记为Bob的地址，则返回位置2 !！对Hamish也是如此；H->给出8。继续从位置8查找地址；如果它被标记为Hamish的地址，则从位置8返回地址。这种机制称为“查找”。如果您没有创建第二个数组(查找数组)，那么您将只有邮件地址数组，您必须逐个查看每个地址，并检查它是否标记了您要查找的客户名称！现在，如果有两个客户的名字以同一个字母开头呢？这叫做哈希冲突，可以用不同的方法来处理。如果我们需要存储10000个名字呢？这意味着我们必须使用一个更好的散列函数，这样就可以减少哈希冲突。我在这里不涉及这两个术语，因为我认为这个问题只需要解释查找和搜索。

问得好！

假设

1. 我们要将strings映射到values。
2. O(1)中的hashFunction(string) => hashedIndex : int
3. valueArray : [any]存储value的
4. valueIndex : int是valueArray中的第一个空索引。
5. lookupArray : [int]将每个valueIndex存储在hashedIndex
6. 数组查找是O(1)。

// Setting a value

valueArray[valueIndex] = value 

hashedIndex = hashFunction(string)

lookupArray[hashedIndex] = valueIndex


// Looking up a value

hashedIndex = hashFunction(string) // O(1)

valueIndex = lookupArray[hashedIndex]; // O(1) array lookup

value = valueArray[valueIndex]; // O(1) array lookup

许多细节遗漏了清楚地回答你的问题。

希望这能帮上忙！