dra*_*ard 102 language-agnostic algorithm performance big-o hashtable
哈希表可以实现O(1)似乎是常识,但这对我来说从来没有意义.有人可以解释一下吗？以下是两种情况:
答: 该值是一个小于哈希表大小的int.因此,该值是它自己的哈希值,因此没有哈希表.但如果有,那将是O(1)并且仍然是低效的.
B. 您必须计算值的哈希值.在这种情况下,查找数据大小的顺序为O(n).在你做O(n)工作之后,查找可能是O(1),但在我眼中仍然是O(n).
除非你有一个完美的哈希表或一个大的哈希表,否则每个桶可能有几个项目.因此,无论如何,它在某个时刻转变为一个小的线性搜索.
我认为哈希表很棒,但我没有得到O(1)的名称,除非它只是理论上的.
维基百科关于哈希表的文章始终引用常量查找时间并完全忽略哈希函数的成本.这真是一个公平的衡量标准吗？
编辑:总结我学到的东西:
这在技术上是正确的,因为哈希函数不需要使用密钥中的所有信息,因此可以是恒定时间,并且因为足够大的表可以将冲突降低到接近恒定的时间.
在实践中确实如此,因为随着时间的推移,只要选择散列函数和表大小来最小化冲突,即使这通常意味着不使用常量时间散列函数,它也只会有效.
Mar*_*ers 59
这里有两个变量,m和n,其中m是输入的长度,n是散列中的项目数.
O(1)查找性能声明至少做出两个假设:
如果您的对象是可变大小并且相等检查需要查看所有位,那么性能将变为O(m).然而,散列函数不必是O(m) - 它可以是O(1).与加密散列不同,在字典中使用的散列函数不必查看输入中的每个位以计算散列.实现可以自由查看固定数量的位.
对于足够多的项目,项目数量将大于可能的哈希值,然后您将获得冲突,导致性能上升到O(1)以上,例如O(n)表示简单的链表遍历(或O(n)*m)如果两个假设都是假的).
实际上,虽然O(1)声称在技术上是错误的,但对于许多现实世界的情况,尤其是上述假设所持有的情况,情况大致如此.
mpe*_*pen 20
您必须计算哈希值,因此查找数据大小的顺序为O(n).在你做O(n)工作之后,查找可能是O(1),但在我眼中仍然是O(n).
什么？散列单个元素需要恒定的时间.为什么会是其他什么？如果你要插入n元素,那么是的,你必须计算n哈希值,并且需要线性时间......看一个元素,你计算一个你正在寻找的哈希值,然后用它找到合适的桶.您不会重新计算散列表中已有的所有内容的哈希值.
除非你有一个完美的哈希表或一个大的哈希表,否则每个桶可能有几个项目,所以无论如何它都会转换成一个小的线性搜索.
不必要.存储桶不一定必须是列表或数组,它们可以是任何容器类型,例如平衡的BST.这意味着O(log n)最坏的情况.但这就是为什么选择一个良好的散列函数以避免将太多元素放入一个桶中的重要性.正如KennyTM指出的那样,平均而言,你仍然会有O(1)时间,即使偶尔你需要挖掘一个桶.
哈希表的权衡当然是空间复杂性.你是时间交易空间,这似乎是计算科学的常见情况.
您提到在其他一条评论中使用字符串作为键.你关心计算字符串散列所需的时间,因为它包含几个字符？正如其他人再次指出的那样,你不一定需要查看所有字符来计算哈希值,尽管如果你这样做可能会产生更好的哈希值.在这种情况下,如果m您的密钥中存在平均字符,并且您使用它们来计算哈希值,那么我认为您是正确的,查找将采用O(m).如果m >> n那时你可能有问题.在这种情况下,你可能会更好地使用BST.或者选择更便宜的散列函数.
哈希值是固定大小的——查找适当的哈希桶是一个固定成本的操作。这意味着它是 O(1)。
计算哈希值不一定是一个特别昂贵的操作 - 我们这里讨论的不是加密哈希函数。但这是顺便说一下。哈希函数计算本身不依赖于元素的数量n；虽然它可能取决于元素中数据的大小，但这不是n所指的。所以哈希的计算不依赖于n，也是O(1)。
TL-DR；通常hash()是密钥长度O(m)在哪里m
我的三分钱。
24 年前，当 Sun 发布 jdk 1.2 时，他们修复了 String.hashCode() 中的一个错误，因此自 jdk1.2 以来不再仅基于字符串的某些部分计算哈希，而是读取字符串的每个字符。这一改变是有意而为之的，而且 IHMO 非常明智。
在大多数语言中，内置哈希的工作原理类似。它处理整个对象来计算哈希，因为键通常很小，而冲突可能会导致严重的问题。
有很多理论论据证实和否认 O(1) 哈希查找成本。其中很多都是合理且有教育意义的。
让我们跳过理论并做一些实验：
import timeit
samples = [tuple("LetsHaveSomeFun!")] # better see for tuples
# samples = ["LetsHaveSomeFun!"] # hash for string is much faster. Increase sample size to see
for _ in range(25 if isinstance(samples[0], str) else 20):
samples.append(samples[-1] * 2)
empty = {}
for i, s in enumerate(samples):
t = timeit.timeit(lambda: s in empty, number=2000)
print(f"{i}. For element of length {len(s)} it took {t:0.3f} time to lookup in empty hashmap")
当我运行它时，我得到：
0. For element of length 16 it took 0.000 time to lookup in empty hashmap
1. For element of length 32 it took 0.000 time to lookup in empty hashmap
2. For element of length 64 it took 0.001 time to lookup in empty hashmap
3. For element of length 128 it took 0.001 time to lookup in empty hashmap
4. For element of length 256 it took 0.002 time to lookup in empty hashmap
5. For element of length 512 it took 0.003 time to lookup in empty hashmap
6. For element of length 1024 it took 0.006 time to lookup in empty hashmap
7. For element of length 2048 it took 0.012 time to lookup in empty hashmap
8. For element of length 4096 it took 0.025 time to lookup in empty hashmap
9. For element of length 8192 it took 0.048 time to lookup in empty hashmap
10. For element of length 16384 it took 0.094 time to lookup in empty hashmap
11. For element of length 32768 it took 0.184 time to lookup in empty hashmap
12. For element of length 65536 it took 0.368 time to lookup in empty hashmap
13. For element of length 131072 it took 0.743 time to lookup in empty hashmap
14. For element of length 262144 it took 1.490 time to lookup in empty hashmap
15. For element of length 524288 it took 2.900 time to lookup in empty hashmap
16. For element of length 1048576 it took 5.872 time to lookup in empty hashmap
17. For element of length 2097152 it took 12.003 time to lookup in empty hashmap
18. For element of length 4194304 it took 25.176 time to lookup in empty hashmap
19. For element of length 8388608 it took 50.399 time to lookup in empty hashmap
20. For element of length 16777216 it took 99.281 time to lookup in empty hashmap
显然，哈希值的复杂度为 O(m)，其中 m 是密钥的长度。
你可以对其他主流语言进行类似的实验，我希望你能得到类似的结果。
小智 5
仅当表中只有恒定数量的键并且做出一些其他假设时，散列才是 O(1)。但在这种情况下它有优势。
如果您的密钥具有 n 位表示形式，则您的哈希函数可以使用这些位中的 1, 2, ... n。考虑使用 1 位的哈希函数。评估肯定是 O(1)。但是您仅将密钥空间划分为 2 个。因此您将多达 2^(n-1) 个密钥映射到同一个 bin 中。使用 BST 搜索，如果几乎已满，则需要最多 n-1 步才能找到特定键。
您可以扩展它，看看如果您的散列函数使用 K 位，则您的 bin 大小为 2^(nk)。
所以 K 位哈希函数 ==> 不超过 2^K 个有效 bin ==> 每个 bin 最多 2^(nK) 个 n 位密钥 ==> (nK) 个步骤 (BST) 来解决冲突。实际上，大多数哈希函数的“效率”要低得多，并且需要/使用超过 K 位来生成 2^k 个 bin。所以即使这样也是乐观的。
你可以这样看——在最坏的情况下，你将需要 ~n 个步骤才能唯一区分一对 n 位的密钥。无论是否有哈希表，确实没有办法绕过这个信息论限制。
但是，这不是您使用哈希表的方式/时间！
复杂性分析假设对于 n 位密钥，表中可能有 O(2^n) 个密钥（例如，所有可能密钥的 1/4）。但大多数（如果不是全部）我们使用哈希表时，表中只有固定数量的 n 位键。如果你只想表中的键数量恒定，假设 C 是你的最大数量，那么你可以形成一个 O(C) 个 bin 的哈希表，这保证了预期的恒定冲突（使用良好的哈希函数）；以及使用密钥中 n 位的 ~logC 的哈希函数。那么每个查询都是 O(logC) = O(1)。这就是人们所说的“哈希表访问是 O(1)”/
这里有几个问题——首先，说你不需要所有的部分可能只是一个计费技巧。首先，您无法真正将键值传递给哈希函数，因为这将在内存中移动 n 位，即 O(n)。所以你需要做例如参考传递。但你仍然需要将它存储在某个地方，这是一个 O(n) 操作；你只是不将其计入哈希值；您的整体计算任务无法避免这一点。其次，你进行散列，找到 bin，并找到超过 1 个键；你的成本取决于你的解析方法——如果你基于比较（BST 或列表），你将有 O(n) 操作（召回密钥是 n 位）；如果你进行第二次哈希，那么，如果第二次哈希发生冲突，你也会遇到同样的问题。因此，O(1) 并不能 100% 保证，除非没有碰撞（您可以通过拥有一个比键更多的 bin 的表来提高机会，但仍然如此）。
在这种情况下，请考虑替代方案，例如 BST。有 C 个键，因此平衡 BST 的深度为 O(logC)，因此搜索需要 O(logC) 步骤。然而，这种情况下的比较将是一个 O(n) 操作……所以在这种情况下散列似乎是更好的选择。
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)。
在之前的挑战中，让我们失败的是对手非常了解我们的哈希函数，并且可以利用这些知识来制作最糟糕的输入。如果我们不是总是使用一个固定的哈希函数，而是实际上有一组哈希函数 ，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|非常大。
将此结果与之前的算法进行对比，在之前的算法中，对手总是赢得挑战。这里有点挥手，但由于大多数时候对手都会失败，而且对手可以尝试的所有可能策略都是如此，因此尽管最坏情况是O(n)，但预期的最坏情况实际上是O(1)。
再次强调，这不是一个正式的证明。我们从这个预期的最坏情况分析中得到的保证是我们的运行时间现在独立于任何特定的输入。这是一个真正的随机保证，与一般案例分析相反，在一般案例分析中，我们表明，有动机的对手可以轻松地制作出错误的输入。