哈希表真的可以O（1）？
哈希表可以达到O（1）似乎是常识，但是这对我来说是没有意义的。 有人可以解释吗？ 这里有两个想到的情况：
A. 值是一个比散列表的大小小的int。 因此，这个值是它自己的哈希，所以没有哈希表。 但是，如果有的话，这将是O（1），仍然是低效的。
B. 你必须计算一个哈希值。 在这种情况下，查找数据大小的顺序是O（n）。 在O（n）工作之后，查找可能是O（1），但是在我眼中仍然是O（n）。
除非你有一个完美的散列表或一个大的散列表，否则每个存储桶可能有几个项目。 所以，无论如何它都会在某个点上进入一个小的线性search。
我认为散列表很棒，但是除非它是理论上的，否则我不会得到O（1）的称号。
维基百科关于散列表的文章始终引用常量查找时间，并完全忽略散列函数的成本。 这真的是一个公平的措施？
编辑：总结我学到的东西：
-
这在技术上是正确的，因为散列函数不需要使用密钥中的所有信息，因此可以是恒定的时间，并且因为足够大的表可以将冲突降低到接近恒定的时间。
-
在实践中是这样的，因为随着时间的推移，只要散列函数和表大小被select为使冲突最小化，即使这通常意味着不使用恒定时间散列函数，也可以实现。
这里有两个variables，m和n，其中m是input的长度，n是散列中项的数量。
O（1）查询性能声明至less有两个假设：
- 您的对象可以在O（1）时间进行比较。
- 将会有很less的哈希碰撞。
如果你的对象是可变大小，并且相等性检查需要查看所有位，则性能将变为O（m）。 哈希函数不一定是O（m） – 它可以是O（1）。 与encryption散列不同，用于字典的散列函数不必查看input中的每一位以计算散列。 实现可以只查看固定的位数。
对于足够多的项目，项目的数量将变得大于可能的散列数量，然后你将得到导致性能在O（1）以上的冲突，例如对于简单的链表遍历（或者O（n） * m）如果两个假设都是假的）。
实际上，尽pipeO（1）声称在技术上是错误的，但对于许多现实世界的情况，特别是在上述假设成立的情况下，情况大致如此。
您必须计算散列，因此查找数据大小的顺序是O（n）。 在O（n）工作之后，查找可能是O（1），但是在我眼中仍然是O（n）。
什么？ 散列单个元素需要一定的时间。 为什么会是其他？ 如果你插入了n元素，那么是的，你必须计算n散列值，并且需要线性时间…来查找一个元素，计算你要查找的单个散列值，然后find合适的存储桶接着就，随即。 您不要重新计算散列表中已经存在的所有内容的散列值。
除非你有一个完美的散列表或一个大的散列表，否则每个存储桶可能有几个项目，所以无论如何它都会在某个点上进入一个小的线性search。
不必要。 桶不一定必须是列表或数组，它们可以是任何容器types，例如平衡BST。 这意味着O(log n)最坏的情况。 但是这就是为什么select一个好的散列函数来避免把太多元素放到一个桶里是很重要的原因。 正如KennyTM所指出的那样，平均而言，即使偶尔需要挖掘桶，您仍然可以获得O(1)次。
哈希表的权衡当然是空间的复杂性。 你正在为时间交易空间，这似乎是计算科学中的常见情况。
你提到使用string作为您的其他评论之一的键。 你担心计算一个string的散列花费的时间，因为它包含几个字符？ 正如其他人指出的，你不一定需要查看所有的字符来计算散列，尽pipe如果你这样做可能会产生更好的散列。 在这种情况下，如果你的密钥中平均有m字符，并且你用它们来计算你的哈希值，那么我认为你是对的，查找会花费O(m) 。 如果m >> n那么你可能有问题。 在这种情况下，你可能会更好地使用BST。 或者select一个更便宜的散列函数。
哈希是固定大小 – 查找适当的哈希桶是固定成本操作。 这意味着它是O（1）。
计算散列并不一定是一个特别昂贵的操作 – 我们不是在说这里的密码散列函数。 但那是靠的。 哈希函数计算本身不依赖于元素的数量n ; 虽然它可能取决于元素中数据的大小，但这不是n所指的。 所以哈希计算不依赖于n ，也是O（1）。
只有在表中只有不变的密钥数量的情况下，哈希才是O（1），并进行了其他一些假设。 但在这种情况下，它有优势。
如果你的密钥有n位表示，你的散列函数可以使用这些位的1，2，… n。 思考使用1位的散列函数。 评估确实是O（1）。 但是，你只是把关键空间分成了两部分。所以你可以将多达2 ^（n-1）个键映射到同一个bin中。 使用BSTsearch这将需要n-1个步骤来find一个特定的键，如果几乎满了。
你可以扩展这个来看看如果你的散列函数使用K位，你的bin的大小是2 ^（nk）。
所以K比特哈希函数==>不超过2 ^ K个有效分区==>每个比特最多2 ^（nK）个n比特密钥==>（nK）个步骤（BST）来解决冲突。 实际上，大多数散列函数的“有效”要less得多，需要/使用多于K位来产生2 ^ k个bin。 所以即使这是乐观的。
您可以通过这种方式查看 – 在最坏的情况下，您需要n个步骤才能唯一地区分n位的一对密钥。 真的没有办法绕过这个信息理论的限制，哈希表或没有。
但是，这不是如何/何时使用散列表！
复杂性分析假定对于n位密钥，可以在表中具有O（2 ^ n）个密钥（例如，所有可能密钥的1/4）。 但是大多数情况下，如果不是所有的时候我们使用散列表，我们在表中只有一个固定数量的n位键。 如果你只想在表中有一个固定数量的键，比如说C是你的最大数，那么你就可以构成一个O（C）仓的哈希表，保证预期的不变碰撞（具有良好的散列函数）。 以及使用密钥中的n位的〜logC的散列函数。 那么每个查询都是O（logC）= O（1）。 这就是人们声称“哈希表访问是O（1）”/
这里有几个捕获 – 首先，说你不需要所有的位，可能只是一个计费技巧。 首先，你不能真正将密钥值传递给散列函数，因为这会在内存中移动n位，即O（n）。 所以你需要做一个参考传递。 但是你仍然需要把它存储在某个已经是O（n）操作的地方。 你只是不要记帐到哈希; 你的整体计算任务是无法避免的。 其次，你做散列，findbin，并且find了超过1个键; 你的成本取决于你的解决方法 – 如果你做基于比较（BST或列表），你将有O（N）操作（调用密钥是N位）。 如果你做第二个哈希，那么，如果第二个哈希有冲突，你也有同样的问题。 所以O（1）不是100％的保证，除非你没有碰撞（你可以通过使用一个有比键多的分区的表来提高机会，但是仍然）。
在这种情况下考虑替代scheme，例如BST。 有C键，所以平衡的BST将是O（logC）的深度，所以search需要O（logC）步骤。 然而，在这种情况下的比较将是一个O（n）操作…所以在这种情况下看起来哈希是一个更好的select。
