首页 文章

哈希表真的可以是O(1)吗?

提问于
浏览
95

哈希表可以实现O(1)似乎是常识,但这对我来说从来没有意义 . 有人可以解释一下吗?以下是两种情况:

A. The value is an int smaller than the size of the hash table. 因此,该值是它自己的哈希值,因此没有哈希表 . 但如果有,那将是O(1)并且仍然是低效的 .

B. You have to calculate a hash of the value. 在这种情况下,查找数据大小的顺序为O(n) . 在你做O(n)工作之后,查找可能是O(1),但在我眼中仍然是O(n) .

除非你有一个完美的哈希表或一个大的哈希表,否则每个桶可能有几个项目 . 因此,无论如何,它在某个时刻转变为一个小的线性搜索 .

我认为哈希表很棒,但我没有得到O(1)的名称,除非它只是理论上的 .

维基百科的article for hash tables始终引用常量查找时间并完全忽略哈希函数的成本 . 这真是一个公平的衡量标准吗?


Edit: 总结我学到的东西:

  • 技术上是正确的,因为哈希函数不需要使用密钥中的所有信息,因此可以是恒定时间,并且因为足够大的表可以将冲突降低到接近恒定的时间 .

  • 在实践中确实如此,因为随着时间的推移,只要选择散列函数和表大小以最小化冲突,它就会成功,即使这通常意味着不使用常量时间散列函数 .

7 回答

  • 4

    这里有两个变量,m和n,其中m是输入的长度,n是散列中的项目数 .

    O(1)查找性能声明至少做出两个假设:

    • 在O(1)时间内,您的对象可以相等 .

    • 哈希冲突很少 .

    如果您的对象是可变大小并且相等检查需要查看所有位,那么性能将变为O(m) . 然而,散列函数不必是O(m) - 它可以是O(1) . 与加密散列不同,在字典中使用的散列函数不必查看输入中的每个位以计算散列 . 实现可以自由查看固定数量的位 .

    对于足够多的项目,项目的数量将大于可能的哈希值,然后您将获得冲突,导致性能上升到O(1)以上,例如对于简单的链表遍历(或O(n)的O(n) * m)如果两个假设都是假的) .

    在实践中,尽管O(1)声称在技术上是错误的,但对于许多现实世界的情况,特别是那些上述假设成立的情况,情况大致如此 .

  • 0

    您必须计算哈希值,因此查找数据大小的顺序为O(n) . 在你做O(n)工作之后,查找可能是O(1),但在我眼中仍然是O(n) .

    什么?散列单个元素需要恒定的时间 . 为什么会是其他什么?如果你要插入 n 元素,那么是的,你必须计算 n 哈希值,这需要线性时间......看一个元素,你计算一个哈希值,你重新计算所有的哈希值已经在哈希表中 .

    除非你有一个完美的哈希表或一个大的哈希表,否则每个桶可能有几个项目,所以无论如何它会在某个时刻转换为一个小的线性搜索 .

    不必要 . 存储桶不一定必须是列表或数组,它们可以是任何容器类型,例如 balancer 的BST . 这意味着 O(log n) 最坏的情况 . 但这就是为什么选择一个良好的散列函数以避免将太多元素放入一个桶中的重要性 . 正如KennyTM指出的那样,平均而言,即使偶尔你需要挖掘一个桶,你仍然会得到 O(1) 的时间 .

    哈希表的权衡当然是空间复杂性 . 你是时间交易空间,这似乎是计算科学的常见情况 .


    您提到在其他一条评论中使用字符串作为键 . 你需要查看所有字符来计算哈希值,尽管如果你这样做可能会产生更好的哈希值 . 在这种情况下,如果您的密钥中平均有 m 个字符,并且您使用了所有字符来计算哈希值,那么我认为您是对的,查找将采用 O(m) . 如果 m >> n 那么您可能会遇到问题 . 在这种情况下,你可能会更好地使用BST . 或者选择更便宜的散列函数 .

  • 0

    哈希是固定大小 - 查找适当的哈希桶是固定成本操作 . 这意味着它是O(1) .

    计算哈希值不一定是特别昂贵的操作 - 我们're not talking cryptographic hash functions here. But that' by by . 哈希函数计算本身不依赖于元素的数量n;虽然它可能取决于元素中数据的大小,但这并不是n所指的 . 因此,散列的计算不依赖于n,也是O(1) .

  • 2

    只有在表中只有一定数量的键并且进行了一些其他假设时,散列才是O(1) . 但在这种情况下它有优势 .

    如果您的密钥具有n位表示,则您的散列函数可以使用这些位的1,2,... n . 考虑使用1位的哈希函数 . 评估肯定是O(1) . 但是您只是将密钥空间划分为2.因此,您将多达2 ^(n-1)个密钥映射到同一个bin中 . 使用BST搜索,如果几乎已满,则需要n-1步才能找到特定的密钥 .

    您可以扩展它以查看如果您的散列函数使用K位,则您的bin大小为2 ^(n-k) .

    所以K位散列函数==>不超过2 ^ K个有效位==>每个bin最多2 ^(n-K)个n位密钥==>(n-K)步骤(BST)来解决冲突 . 实际上,大多数散列函数都不那么“有效”,需要/使用多于K位来产生2 ^ k个二进制位 . 所以即使这是乐观的 .

    您可以这样查看 - 在最坏的情况下,您需要步骤才能唯一地区分n位的一对密钥 . 实际上没有办法解决这个信息理论限制,哈希表与否 .

    但是,这不是你何时/何时使用哈希表!

    复杂性分析假设对于n位密钥,表中可以有O(2 ^ n)个密钥(例如,所有可能密钥的1/4) . 但是大多数情况下,如果不是所有时间我们都使用哈希表,我们在表中只有一个恒定数量的n位密钥 . 如果你只想在表中使用一定数量的键,比如说C是你的最大数,那么就可以形成一个O(C)二进制的哈希表,它保证了预期的持续冲突(具有良好的哈希函数);以及使用密钥中n位的~logC的散列函数 . 然后每个查询都是O(logC)= O(1) . 这是人们声称“哈希表访问是O(1)”/

    这里有几个捕获 - 首先,说你不需要所有的位可能只是一个计费技巧 . 首先,你不能真正将键值传递给散列函数,因为这将在内存中移动n位(O(n)) . 所以你需要做,例如参考传递 . 但你仍然需要将它存储在已经是O(n)操作的地方;你只是不向哈希收费;你的整体计算任务无法避免这种情况 . 其次,你进行散列,找到bin,找到1个以上的键;你的成本取决于你的解决方法 - 如果你做基于比较(BST或List),你将有O(n)操作(调用键是n位);如果你做第二个哈希,那么,如果第二个哈希发生冲突,你会遇到同样的问题 . 所以O(1)不是100%保证,除非你没有碰撞(你可以通过拥有一个比键更多的箱子,但仍然可以提高机会) .

    考虑替代方案,例如BST,在这种情况下 . 有C键,所以 balancer 的BST深度为O(logC),因此搜索需要O(logC)步骤 . 然而,在这种情况下的比较将是O(n)操作...因此在这种情况下看起来散列是更好的选择 .

  • 1

    TL; DR:如果从一个通用的哈希函数族中随机选择哈希函数,则哈希表保证 O(1) 预期的最坏情况时间 . 预期的最坏情况与普通情况不同 .

    Disclaimer: 我没有正式证明哈希表是 O(1) ,因为它从coursera [1]看一下这个视频 . 我也不讨论哈希表的摊销方面 . 这与关于散列和碰撞的讨论是正交的 .

    我在其他答案和评论中看到了关于这个主题的令人惊讶的混乱,并将在这个长期答案中尝试纠正其中的一些 .

    关于最坏情况的推理

    有不同类型的最坏情况分析 . 到目前为止,大多数答案在这里做出的分析不是最坏的情况,而是平均情况[2] . Average case 分析往往更实用 . 也许你的算法有一个糟糕的最坏情况输入,但实际上适用于所有其他可能的输入 . 底线是您的运行时取决于您正在运行的数据集 .

    考虑以下哈希表的 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 的输入,供你插入你的 table .

    问题是:你的哈希表在对手输入上的速度有多快?

    从步骤(1)开始,对手知道你的哈希函数;在步骤(2)期间,对手可以使用相同的 hash modulo m 来制作 n 元素的列表 . 随机计算一堆元素的哈希值;然后在(3)他们可以给你那个清单 . 但是,请注意,由于所有 n 元素都散列到同一个存储桶,因此您的算法将花费 O(n) 时间来遍历该存储桶中的链接列表 . 无论我们多少次重新尝试挑战,对手总会获胜,这就是你的算法有多糟糕,最糟糕的情况 O(n) .

    为什么哈希是O(1)?

    在之前的挑战中让我们失望的是对手非常了解我们的哈希函数,并且可以利用这些知识来制作最糟糕的输入 . 如果不是总是使用一个固定的哈希函数,我们实际上有一组哈希函数, H ,算法可以在运行时随机选择?如果你很好奇, H 被称为 universal family of hash functions [3] . 好吧,让我们尝试为此添加一些随机性 .

    首先假设我们的哈希表还包括种子 r ,并且 r 在构造时被分配给随机数 . 我们分配一次,然后's fixed for that hash table instance. Now let'重新审视我们的伪代码 .

    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)中,对手随机选择 H 中的一个函数 hash ,然后在 hash modulo m 下制作一个 n 碰撞列表,并将其发送给步骤(3),在运行时 H[r] 的交叉指针将是相同的 hash 他们选择了 .

    对于对手而言,这是一个严肃的赌注,他制作的列表在 hash 下发生碰撞,但在 H 中只是随机输入的任何其他散列函数 . 如果他赢了这个赌注我们的运行时间将是最糟糕的情况 O(n) ,就像之前一样,但是如果他失败那么我们只是被给予一个随机输入,平均 O(1) 时间 . 事实上大多数时候对手都会失败,他每次挑战都只赢一次,我们可以让他们变得非常大 .

    将此结果与之前的算法进行对比,其中对手总是赢得挑战 . 在这里稍微动手,但是由于对手大多数时候都会失败,对手可以尝试的所有可能策略都是如此,因此尽管最坏的情况是 O(n)expected worst case 实际上是 O(1) .


    同样,这不是一个正式的证据 . 我们从这个预期的最坏情况分析得到的保证是我们的运行时间现在独立于任何特定输入 . 这是一个真正随机的保证,而不是平均案例分析,我们展示了一个有动力的对手可以很容易地制造糟糕的输入 .

  • 53

    有两种设置可以获得O(1)最坏情况时间 .

    • 如果您的设置是静态的,那么FKS哈希将为您提供最坏情况的O(1)保证 . 但正如您所指出的,您的设置不是静态的 .

    • 如果使用Cuckoo散列,则查询和删除是O(1)最坏情况,但插入只是预期的O(1) . 如果你有一个插入总数的上限,并且将表格大小设置为大约25%,那么Cuckoo散列效果很好 .

    复制自here

  • 19

    看来基于这里的讨论,如果X是(表格中的元素数量/#箱子数量)的上限,那么更好的答案是O(log(X)),假设有效实现bin查找 .

相关问题