可以哈希表确实是O（1）？可以哈希表确实是O（1）？(Can hash tables really

这似乎是常识，哈希表可以达到O（1），但从未对我有意义。 可有人请解释一下吗？ 下面是浮现在脑海中有两种情况：

答值是一个int比哈希表的大小较小。 因此，该值是其自身的哈希值，所以没有哈希表。 但是，如果有，那将是O（1），并且仍然是低效的。

B. 你要计算值的散列。 在这种情况下，该命令是针对数据的大小为O（n）中进行查找。 查找可能是O（1）你做Ô后（n）的工作，但仍然出来为O（N）在我的眼前。

除非你有一个完美的哈希值或大的哈希表中，有每桶大概几个项目。 因此，它的不满转化在某一点小线性搜索反正。

我认为哈希表是真棒，但除非它只是应该是理论上我没有得到O（1）指定。

维基百科的哈希表的文章始终引用常量查找时间，完全忽略了散列函数的成本。 那真的是一个公平的措施？

---

编辑：要总结一下我的经验：

• 因为哈希函数不需要使用钥匙的所有信息，因此可能会受到一定的时间，因为一个足够大的表可以带来碰撞到附近固定的时间这在技术上是正确的。

• 因为随着时间的推移，它就可以工作了，只要散列函数和表的大小进行选择，以尽量减少冲突，尽管这通常意味着不使用恒定时间哈希函数，是在实践中正确的。

Answer 1:

你有两个变量在这里，m和n，m是输入的长度，n是哈希的项目数。

的O（1）查找性能要求使得至少两个假设：

• 你的对象可以是平等的O（1）时间进行比较。
• 很少会有哈希冲突。

如果你的对象是可变大小和平等的检查需要看所有位则性能将成为O（M）。 散列函数然而，这并不必须是O（M） - 它可以是O（1）。 不同的加密散列，用于在字典中使用的哈希函数不必看输入的每一位，以计算哈希值。 实现随意看只有一个固定的比特数。

对于足够多的项目的项目数会比可能哈希值的数量更大，那么你会得到碰撞导致性能升破O（1），例如O（n）的一个简单的链表遍历（或者为O（n * M）如果两个假设都是假的）。

但在实践中的O（1）要求，同时在技术上假的，是许多现实世界的情况近似正确的，特别是那些在上述假设成立的情况。

Answer 2:

你必须计算散列，所以该命令是用于数据的大小为O（n）中进行查找。 查找可能是O（1）你做Ô后（n）的工作，但仍然出来为O（N）在我的眼前。

什么？ 哈希单个元件需要一定的时间。 为什么它会是什么吗？ 如果要插入n元素，那么，你必须计算n哈希值，而这需要线性时间......看的元素，你计算的，你要寻找的一个散列，然后找到相应的桶接着就，随即。 你不重新计算一切的已经在哈希表中的哈希值。

除非你有一个完美的散列或一个大哈希表有可能是每桶几个项目，因此它的不满转化在某一点小线性搜索反正。

不必要。 该桶不一定必须是列表或数组，它们可以是任何容器类型，如平衡BST。 这意味着O(log n)最坏情况。 但是，这就是为什么要选择一个好的哈希函数，以避免把太多的元素融入其中桶是非常重要的。 作为KennyTM指出，平均而言，你仍然会得到O(1)时间，即使偶尔你必须通过一个斗挖。

关闭哈希表的行业当然是空间复杂度。 你的时间，这似乎是在计算机科学通常情况下交易的空间。

---

你提到使用字符串作为您的其他意见一个键。 你担心所花费的时间来计算字符串的哈希量，因为它由几个字符的？ 至于别人再次指出，你不一定需要看所有的字符来计算哈希，但如果你做了可能会产生更好的哈希值。 在这种情况下，如果平均有m在你的关键字符，并且使用所有这些来计算您的哈希值，那么我想你是对的，查找将采取O(m) 如果m >> n ，那么你可能有问题。 你可能会与在该情况下，BST更好。 或者选择更便宜的散列函数。

Answer 3:

散列是固定的大小 - 查找相应的哈希桶是一个固定的成本操作。 这意味着，它是O（1）。

计算散列不必是一个特别昂贵的操作 - 我们不是在这里谈论加密散列函数。 但是，这是靠了靠。 散列函数计算本身不依赖于元件的数量n; 虽然它可能依赖于数据的大小中的元素，这是不是指的是什么ñ。 这样的哈希的计算不依赖于n和也是O（1）。

Answer 4:

散列是O（1）仅当仅存在恒定数目的在表中的键和其他一些假设制成。 但是，在这种情况下，它有优势。

如果您的密钥具有n位表示，你的哈希函数可以用1，2，...这些n个位。 大约使用1位散列函数的思考。 评价为O（1）确定。 但是，你只分割密钥空间为2。因此要映射多达2 ^（N-1）键到同一箱。 使用BST搜索最多需要n-1个步骤，如果快满找到一个特定的键。

您可以扩展此看到，如果你的哈希函数使用k位的块大小2 ^（NK）。

所以K位散列函数==>不超过2-1K-有效仓==>达到2 ^（NK）n位每个仓==>（NK）步骤（BST）解决冲突密钥。 实际上大多数的散列函数是少得多的“有效”和需要/使用比K比特多，以产生2 ^ķ箱。 因此，即使这是乐观的。

你可以这样看 - 你需要能够唯一地分辨出对n位的密钥在最坏的情况下〜n步。 实在是没有办法来解决这个问题的信息理论极限，哈希表或没有。

然而，这并不是如何/当你使用哈希表！

复杂性分析假设为n位的密钥，你可以有O（2 ^ n）的表中的键（例如，所有可能的密钥的1/4）。 但是，如果不是所有的，我们使用哈希表的时候，我们只有在表中的n位密钥的常数。 如果你只想在表中键的常数，说C是你的最大数，那么你可以形成O（C）仓的哈希表中，保证预期不断的碰撞（具有良好的哈希函数）; 并使用该密钥的n位〜logC的哈希函数。 然后每个查询是O（logC）= O（1）。 这是人们如何要求“哈希表的访问是O（1）” /

有一对夫妇渔获物在这里 - 第一，说你并不需要所有的位可能只是一个记账的把戏。 首先，你不能真正传递键值哈希函数，因为那将是在为O（n）内存移动n位。 所以，你需要做的如引用传递。 但你仍然需要已经存储在某个地方这是一个O（n）的操作; 你只是没有它法案散列; 你总计算任务无法回避这一点。 其次，你做的散列，找到垃圾桶，发现超过1个键; 您的费用取决于你的解析方法 - 如果你这样做基于（BST或列表）相比较，您将有O（n）的操作（调键是n位）; 如果你这样做第二散，好了，你有同样的问题，如果第二散有冲突。 所以，O（1）是不是100％的保证，除非你有没有冲突（你可以通过具有比键位的二进制位表改善的机会，但仍然）。

考虑替代方案，如BST，在这种情况下。 有是C键，因此平衡BST将是O（logC）中的深度，这样一个搜索需要O（logC）步骤。 然而，在这种情况下，比较是一个O（n）的操作......所以才出现散列在这种情况下一个更好的选择。

Answer 5:

TL; DR：哈希表保证O(1)预计最坏情况下的时间，如果你从散列函数的通用家族挑选你的散列函数均匀随机。 预计最坏的情况是不一样的平均情况。

免责声明：我没有正式地证明哈希表是O(1)对于看看从coursera [视频1 ]。 我还没有讨论哈希表的摊销方面。 正交约散列和碰撞的讨论。

我看到混乱的一个令人惊讶的大量围绕这个话题在其他的答案和评论，并会尝试纠正其中的一些在这漫长的答案。

推理最坏的情况下

有不同类型的最坏情况分析的。 大多数的答案迄今在这里所做的分析并不是最糟糕的情况，而是平均情况 [ 2 ]。 一般情况下，分析更趋于实用。 也许你的算法有一个坏的最坏情况下的输入，但实际工作以及其他所有可能的输入。 底线是你的运行取决于你正在运行的数据集 。

考虑以下伪代码get哈希表的方法。 在这里我假设我们通过链接处理碰撞，所以表的每个条目的链接列表(key,value)对。 我们还假设的桶数m是固定的，但是O(n)其中n是在输入的元素数。

function get(a: Table with m buckets, k: Key being looked up)
  bucket <- compute hash(k) modulo m
  for each (key,value) in a[bucket]
    return value if k == key
  return not_found

至于其他的答案已经指出的那样，这个运行在平均O(1)和最坏情况下O(n) 我们可以通过挑战做出证明的一点草图在这里。 我们面临的挑战去如下：

（1）你给你的哈希表算法的对手。

（2）攻击者可以学习它，只要他想要做准备。

（3）最后的对手给你的尺寸的输入n为你在你的表中插入。

现在的问题是：如何快速是对对手输入您的哈希表？

从步骤（1）对手知道你的哈希函数; 在步骤（2）对手可以手艺的列表n与相同的元件hash modulo m ，通过例如随机计算一串要素的哈希; 然后在（3），他们可以给你的列表。 但是，你瞧，因为所有n元素散列到同一个桶，你的算法需要O(n)时间来遍历在桶中的链接列表。 不管我们有多少次重试的挑战，对手总是赢，这就是你的算法是多么糟糕，最坏的情况下O(n)

为什么散列是O（1）？

什么在前面的挑战，把我们关是对手知道我们的哈希函数非常好，可以用这些知识来工艺的最坏可能的输入。 如果不是经常使用一个固定的散列函数，我们实际上有一组散列函数， H ，该算法可以随机在运行时选择？ 如果你很好奇， H被称为散列函数的通用家族 [ 3 ]。 好吧，让我们尝试加入一些随机性这一点。

首先假设我们的哈希表还包括种子r和r被分配到在施工时间的随机数。 我们为它分配一次，然后它固定为哈希表实例。 现在，让我们重新审视我们的伪代码。

function get(a: Table with m buckets and seed r, k: Key being looked up)
  rHash <- H[r]
  bucket <- compute rHash(k) modulo m
  for each (key,value) in a[bucket]
    return value if k == key
  return not_found

如果我们尝试挑战一个更多的时间：从步骤（1）对手就可以知道我们已经在所有的散列函数H ，但现在我们使用的特定散列函数取决于r 值r是私有的我们的结构中，对手在运行时不能检查它，也没有提前预测，所以他不能编造一个列表，总是对我们有害的。 让我们假设，在步骤（2）的对手选择一个函数hash在H随机的，他然后工艺品的列表n下碰撞hash modulo m ，并发送对于步骤（3）中，交叉指在运行时H[r]将相同hash他们选择。

这是对手，他精心制作下发生碰撞列表中的严重赌hash ，但也只是下任何其他哈希函数随机输入H 。 如果他赢了这个赌我们的运行时间将是最坏的情况下O(n)像以前一样，但如果随后他失去了好，我们只是被赋予一个随机输入这需要平均O(1)时间。 事实上次数最多的对手会输，他只赢得一次|H| 挑战，我们可以使|H| 是非常大的。

这一结果与前面的算法，其中的对手总是赢得了挑战。 这里Handwaving了一点，但因为大多数时候 ，对手会失败，这是所有可能的战略对手可以尝试真实的，它遵循的是，虽然最坏的情况是O(n) 预期最坏的情况下 ，其实是O(1) 。

---

再次，这是不是一个正式的证明。 我们从这个预期的最坏情况分析中得到的保证是，我们的运行时间现在是独立于任何特定的输入 。 这是一个真正的随机保障，而不是平均情况分析，我们表现出了积极的对手很容易坏手艺投入。

Answer 6:

有两种设置下，你可以得到O（1）最坏情况下的时间。

1. 如果你的设置是静态的，那么FKS哈希将让你最坏情况O（1）保证。 但正如你指出，你的设置也不是一成不变的。
2. 如果您使用的杜鹃散列，然后查询和删除是O（1）最坏的情况，但插入只有（1）预期O操作 。 杜鹃散列工作得很好，如果你有一个上限值，上插入的总数，并设置表的大小要大25％左右。

从复制在这里

Answer 7:

它似乎基于这里的讨论，如果X是（＃箱中的表/＃元素）的上限，那么一个更好的答案是O（日志（X））假设一个有效的实施斌查找。

文章来源: Can hash tables really be O(1)?