logo标签列表

为什么通过键访问字典元素的时间复杂度是O(1)，即使哈希函数不是O(1)？

c#dictionaryhashtablebig-o
82

我知道你可以通过键来访问你的集合。然而，哈希函数本身在幕后执行了许多操作，是吗？

假设你有一个非常有效的好哈希函数，它仍然可能需要执行许多操作。

这可否解释一下？

41
O符号是用于度量不同输入下复杂度的增长。它与操作数量无关。例如：当有1个值时，需要x秒，当有n个值时，大约需要x*n秒=> O(n)。其中x可能是多个操作的组合。 - Khanh TO
34
数据结构本身并没有O符号的复杂度，对它们进行的操作才有。 - user6144226
3
我们正在谈论哪个操作？ - Patrick Hofman
1
OP明确表示，按键访问是所讨论的操作。 - Steve Wakeford
1
“很多操作”和O(1)是完全兼容的 - O(1)或常数时间意味着，随着元素数量趋近于无穷大，存在某个有限常数来限制执行时间。该常数可以是任意大的 - 使用保证在一年内完成的哈希函数也不会阻止系统成为O(1)。 - Peteris
显示剩余5条评论
9个回答
148

O(1) 并不意味着瞬间完成。 O(1) 意味着在数据规模变化的情况下仍然保持常数级别的复杂度。哈希函数需要一定的时间，但这段时间不会随着集合大小的增加而变长。

1
但是编写一个受集合大小影响的哈希函数是可能的。虽然这样做很愚蠢、很勉强，但你确实可以这么做。搜索哈希集合的前提是计算哈希值是O(1)的，这几乎总是成立的，但不是必须的。 - Servy
@Servy 甚至不一定是那么愚蠢和人为的。一个自定义列表实现想要允许持有相等项的两个列表比较为相等本身，可以重写 GetHashCode() 方法以某种方式组合项的哈希码。如果我要实现这样一个类，对于初始实现，我会完全按照这种方式实现 GetHashCode()。当然，我以后也会进行更改。 - user743382
1
@hvd 那将是一个O（m）哈希，其中m是内部集合的大小。它仍然与外部集合的大小（实际哈希结构）无关。你需要让集合中的项目查看他们当前所在的所有相同哈希集合中的项目，这样这些项目才能具有O（n）（或任何n的函数）作为它们的哈希码。那将是相当愚蠢和牵强的。 - Servy
1
@Servy 哦，你是这个意思。是的，那样做很愚蠢。 :) 我想不出任何可能的情况，你会想要那样做。 - user743382
请记住，对于哈希作为字典键的情况，它需要是_稳定的_，即在对象添加到字典后不会更改。因此，它仅通过对对象的某些不可变部分进行哈希运算才能正常工作。否则，您将会破坏大多数字典实现的契约。同时也要记住，至少对于Java而言，契约是如果a.equals(b)则hash(a)==hash(b)。将集合作为哈希函数的一部分将导致整个字典停止工作，如果这导致集合更改，则哈希值也会更改。 - Martin C.
显示剩余6条评论
122

HashFunc本身在幕后执行了很多操作。

这是确实的。然而，这些操作的数量取决于密钥的大小，而不是它被插入的哈希表的大小：计算哈希函数的操作数量对于在有十个或一万个条目的表中的密钥来说是相同的。

这就是为什么调用哈希函数通常被认为是O(1)的原因。对于固定大小的键（整数值和固定长度字符串），这种方法效果良好。对于变长键，它也提供了一个可行的上限。

尽管如此，哈希表的访问时间通常是O(k)，其中k是哈希密钥的上限。

8
请注意，除非至少有一个项目由至少 log(n) 个比特表示，否则无法拥有 n 个不同项的哈希表。 - Owen
遗憾的是，如果您不限制输入的位数，所有操作都是指数级的。但这并不是一个非常有趣或有用的结果，对吧？ - Joker_vD
1
@Owen：在内存哈希表中，无法拥有比可以唯一分配的键更多的项，并使其适合指针大小的变量。 - Joshua
这些操作的数量取决于密钥的大小和被哈希数据的大小。 - Eric J.
k 不需要是一个上限。查找时间与键的大小成线性关系，因此它确实是 O(k)，其中 k 是键的大小。如果将 k 理解为上限，则实际上是 O(1)。 - usr
16
这意味着无论你的集合有多大，检索其中任何一个成员所需的时间几乎相同。换句话说，具有5个成员的字典可能需要大约0.002毫秒来访问其中一个成员，而具有25个成员的字典应该需要类似的时间。Big O意味着算法复杂度与集合大小成比例，而不是实际执行的语句或函数。
1
但是，如果您的哈希函数非常糟糕，可能会在桶中得到大量的值，因此O(1)将不再成立。 - klappvisor
4
@klappvisor，并非所有带有函数的东西都是不好的。它可能是由于输入数据被精心制作而导致的。这就是为什么此处的O(1)是平摊复杂度，而不是“真正”的复杂度。 - n0rd
这并不意味着每个成员都需要相同的时间，它只是（粗略地）意味着访问时间的上限不会随着集合大小的增加而增长。考虑哈希表如何处理消除冲突。同样地，查找二叉搜索树中的项是O(log2 n)，因为最坏情况下是log2 N，但是靠近根部的项所需的时间比叶子项少。 - fluffy
@n0rd，这并不是“摊销”O(1)的确切含义。实际上，“摊销”O(1)是为了解决大约1/N的添加操作（如果您正在向集合中添加元素）需要重新分配新的后备数组的情况，这是一个O(N)操作，因此您可以在O(N)时间内执行N个添加操作，从而获得一个摊销O(1)的添加操作，而单个添加操作实际上也是O(N)（当未摊销时）。这是一种独立的渐近复杂度说明，它假设哈希值已经足够好地分布。 - Servy
13
如果使用HashMap实现字典/映射，它的最佳情况时间复杂度为O(1)，因为在最佳情况下，只需要计算键元素的哈希码即可检索，如果没有键冲突。
如果有很多键冲突或者哈希函数非常糟糕，则哈希映射的最坏情况运行时复杂度可能为O(n)，因为此时它会退化为扫描包含数据的整个数组的线性扫描。
另外，O(1)并不意味着瞬间完成，而是指具有常数量级。因此，选择正确的字典实现也可能取决于集合中元素的数量，因为如果条目很少，函数的常数成本非常高，这将更糟糕。
这就是为什么针对不同的场景和数据量，字典/映射的实现方式都不一样。对于Java来说，有多种不同的实现方式，而C++使用红黑树等方法。你可以根据数据的数量以及它们的最佳/平均/最坏情况运行效率来选择合适的实现方式。
1
不一定非得这样，例如Java 8的HashMap在检测到多个冲突时会采用平衡树。 - acelent
@acelent可能是正确的，但这不再是经典的哈希映射。有许多不同的地图/字典实现，正好适用于这种情况。我已经修改了答案以指出这一点。 - Martin C.
7
从理论上讲，它仍然是O(n)，因为在最坏的情况下，您的所有数据可能具有相同的散列值并被捆绑在一起，在这种情况下，您必须线性地遍历所有数据。
3
请参考帖子What does "O(1) access time" mean?。
只要对于集合中的每个元素，访问它们所需的时间相同（恒定），哈希函数中的操作次数就无关紧要。例如，在包含2个元素的集合中访问一个元素需要0.001毫秒，但在包含20亿个元素的集合中访问一个元素也需要0.001毫秒。尽管哈希函数可能包含数百个if语句和多个计算。
6
固定的时间量，不是线性的。 - Kusalananda
一个哈希函数需要包含更多的“if语句和多个计算”才能产生足够长的哈希值来唯一标识20亿个元素，而不是200个元素吗？ - Damian Yerrick
1

来自文档：

通过使用其键检索值非常快，接近O(1)，因为T:System.Collections.Generic.Dictionary`2类实现为哈希表。

因此它可以是O(1)，但可能会更慢。 在这里，您可以找到关于哈希表性能的另一个线程：哈希表-为什么比数组更快？

1
一旦您考虑到越来越大的字典占用更多内存，深入缓存层次结构并最终到达磁盘上的缓慢交换空间，很难争辩它真正是O(1)。随着字典变得越来越大，字典的性能会变得越来越慢，可能会给出O(log N)的时间复杂度。不相信？请自行尝试使用1、100、1000、10000等字典元素，直到100亿，并测量在实践中查找元素所需的时间。
但是，如果您做出简化假设，即您系统中的所有内存都是随机访问内存，并且可以在恒定时间内访问，则可以声称该字典为O(1)。尽管这种假设在带有磁盘交换空间的任何机器上都不是真实的，并且在各种CPU缓存级别下仍然非常值得商榷，但这种假设很常见。
你说得没错，但是当我们谈论算法复杂度时，假设硬件完美是有意义的。关键是定义算法的特征，而不是不同的现实硬件实现。此外，如果数据足够大，算法的复杂度才是最重要的：它是否为O(1)、O(logN)、O(n)或O(n^2)等。 - Tero Lahtinen
1
还有一个问题是在使用更大的字典时会出现哈希键冲突的情况。一旦你的字典足够大，大多数新条目都会与现有条目发生冲突，导致通过每个哈希桶进行线性搜索，最终成为O(n)。除非你让哈希键随着大小的增加而变长...但这样你也没有O(1)了。我同意在实践中你可以将其视为常数时间，但对于某些小到足以近似为粗略估计而不是任何大小的正式证明的东西，我更愿意远离正式的O-符号。 - Ed Avis
0

我们知道哈希函数通过键访问值需要O(1)的时间...所以这并不意味着只需一步即可获取该值，它意味着常数时间“t”，其中“t”不取决于数据结构的大小（例如：Python字典()）。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接