old*_*959 3 algorithm hash hashmap
从技术上讲,根据我在这里读到的帖子,哈希表在最坏的情况下确实是O(n)时间查找.但我不知道内部机制如何保证它平均为O(1)时间.
我的理解是,给定n个元素,理想情况是有n个桶,这导致O(1)空间.这就是我被困住的地方.假设我想查找一个键是否在字典中,这肯定需要O(n)时间.那么,当我想通过使用其键的哈希值来搜索元素是否在哈希表中时,为什么会有所不同呢？简而言之,使用原始键值进行搜索会得到O(n)时间,但使用哈希值时会得到O(1)时间.这是为什么？
难道我还不需要逐个查找哈希值来查看哪一个匹配？为什么哈希让我立即知道要检索哪个元素或者是否存在这样的元素？
听起来您正在寻找更详细的解释！
我假设您已经了解数组元素查找需要 O(1) 即如果我已经知道我想查找数组中的第 100 个元素那么它只需要我 O(1) 因为这是一个简单的内存地址查找（通过添加100 到第一个元素的地址）。
散列方法利用这种内存地址查找来实现 O(1) 平均时间。现在显然这意味着您需要能够将查找键转换为内存地址。让我给你一个非常简单的例子，说明它在哈希表中是如何工作的（为了清楚起见，字典在底层实现了哈希表，所以当我提到 hashtable 时，完全相同的原则也适用于字典）。
简化的示例场景；我们需要通过名字查找客户的邮寄地址。为简单起见，假设名称将是唯一的，并且它们具有正常的 a 到 z 字母。假设最初我们仅针对 10 个客户（即他们的姓名和地址）进行设计。
现在让我们说我们必须通过在哈希表中存储名称地址对来解决这个问题，我们必须创建我们自己的哈希函数！！！一个将名称作为参数并将其转换为内存查找的哈希函数！！
现在花点时间想想这里需要多少个数组？它们的类型是什么，它们的大小是多少？
我们肯定需要一个数组来存储邮寄地址。尺寸应该是多少？好吧，我们需要存储 10 个邮寄地址，因此大小必须为 10！我们还需要第二个数组来存储第一个数组的元素索引！！或者换句话说，我们需要第二个数组来存储对客户姓名的邮寄地址（来自第一个数组）的引用。这个数组的大小应该是多少？绝对大于10！但这真的归结为我们设计的哈希函数。为简单起见，让我们创建一个散列函数，它只取 name 参数的第一个字母并将其转换为索引。即如果名称从 A 开始，那么它的哈希值为 1，对于 b，它是 2，对于 c，它是 3...对于 z，它是 26。所以至少我们的查找数组大小必须是 26（你一定认为这是存储10个地址的大量空间的浪费！！但它可能是值得的，因为它会给我们带来性能）让我们试着用一个例子来理解这一点。假设我们的第一个客户名称是 Bob。为 Bob 存储地址的第一步是找到邮寄地址数组中的第一个空元素。这是第一个名字，所以整个邮寄地址数组都是空的。我们可以将 Bob 的地址存储在邮寄地址数组的索引零处。当我们存储这个地址时，我们还会在索引 0 处将它标记为 Bob 的地址。（我使用这个“标记”术语来解释查找与搜索）然后我们找出名称 Bob 的哈希值。在这种情况下，它将是 2！因此，在位置 2 的查找数组中，我们存储 0。（即 Bob 邮寄地址的索引）。现在假设我们的第二个客户是 Hamish；我们将 Hamish 的邮寄地址存储在邮寄地址数组的索引 1（即第二个元素）处；将其标记为Hamish的地址，然后我们找出Hamish的哈希值。由于Hamish 从'H' 开始，值将是8。所以在位置8 的查找数组中，我们存储值1（即Hamish 地址的索引）。我们可以对所有 10 个客户重复此过程并存储他们的地址。现在，当您想查找 Bob 的地址时，只需按照简单的两步程序即可快速查找。步骤 1- 将名称 Bob 转换为 hashvalue ；答案是2；继续检查邮寄地址数组中的位置 2；如果它被标记为 Bob 的地址，则返回位置 2 !! 哈米什也是如此；H-> 给出 8。继续从位置 8 查找地址；如果它被标记为 Hamish 的地址，则从位置 8 返回地址。这种机制称为“查找”。如果您没有创建第二个数组（查找数组），那么您将只有邮寄地址数组，并且您必须一个一个地检查每个地址并检查它是否标有您要查找的客户名称或不是！。现在，如果有两个客户名称以相同的字母开头怎么办？这就是所谓的哈希冲突，可以用不同的方法来处理。如果我们需要存储 10000 个名字怎么办？这意味着我们必须使用更好的哈希函数来减少哈希冲突。我没有在这里介绍这两个术语，因为我相信这个问题只需要解释查找与搜索。如果有两个客户名称以相同的字母开头怎么办？这就是所谓的哈希冲突，可以用不同的方法来处理。如果我们需要存储 10000 个名字怎么办？这意味着我们必须使用更好的哈希函数来减少哈希冲突。我没有在这里介绍这两个术语，因为我相信这个问题只需要解释查找与搜索。如果有两个客户名称以相同的字母开头怎么办？这就是所谓的哈希冲突，可以用不同的方法来处理。如果我们需要存储 10000 个名字怎么办？这意味着我们必须使用更好的哈希函数来减少哈希冲突。我没有在这里介绍这两个术语，因为我相信这个问题只需要解释查找与搜索。
我认为你会混淆术语,并且通过考虑桶来使问题复杂化.
让我们设想一个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"的插入方式),但我们没有类似的快速方式来查找"纽约".
我假设这是你要问的,你有点混淆术语.如果这不是你想要的,请评论.