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

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

o(1)查找性能声明至少作出了两个假设:

• 你的对象在o(1)时间内可以相等。
• 散列冲突很少。

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

对于足够多的项,项的数量将大于可能的散列的数量,然后您将获得导致性能高于o(1)的冲突,例如,对于简单的链表遍历(或o(n*m),如果两个假设都为假)。

实际上,虽然o(1)声明在技术上是错误的,但是 大约 适用于许多现实世界的情况,尤其是上述假设成立的情况。

必须计算散列,因此查找的数据大小的顺序为o(n)。在你做了o(n)项工作之后,查找可能是o(1),但在我看来,仍然是o(n)。

什么?散列单个元素需要恒定的时间。为什么会是别的?如果你要插入 n 元素,那么是的,你必须计算 n 散列,这需要线性时间…要查找一个元素,您需要计算所查找内容的一个散列,然后用它找到相应的桶。你不能计算已经在哈希表中的所有东西的哈希值。

而且除非你有一个完美的散列或一个大的散列表,否则每个bucket可能有几个条目,因此无论如何,它在某个点上都会转移到一个小的线性搜索中。

不一定。bucket不一定是列表或数组,它们可以是任何容器类型,比如平衡的bst。 O(log n) 最坏情况。但这就是为什么选择一个好的散列函数以避免在一个bucket中放入太多元素是很重要的。正如Kennytm指出的,平均来说,你还是会 O(1) 时间,即使有时你不得不挖出一个桶。

哈希表的取舍当然是空间复杂性。你在用空间换取时间,这似乎是计算机科学中的常见情况。

您提到在其他注释中使用字符串作为键。你担心计算一个字符串的散列所需的时间,因为它由几个字符组成?正如其他人再次指出的那样,您不必查看所有的字符来计算散列,尽管如果这样做,它可能会产生更好的散列。在这种情况下,如果平均有 m 你的钥匙上有字符,你用它们来计算你的散列,那么我想你是对的,查找需要 O(m) . 如果 m >> n 那你可能有问题。如果那样的话,你最好有个英国夏令时。或者选择一个更便宜的散列函数。

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

计算哈希不一定是一个特别昂贵的操作-我们这里不讨论加密哈希函数。但那是顺便说的。哈希函数计算本身不依赖于数字 n 元素;虽然它可能取决于元素中数据的大小,但这不是 n 是指。所以散列的计算不依赖于 n 也是o(1)。

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

如果密钥有N位表示,则哈希函数可以使用1、2、…N个。考虑使用1位的哈希函数。评价是肯定的。但你只是把密钥空间分割成2个。因此,您将多达2^(n-1)个键映射到同一个bin中。使用bst search这需要n-1个步骤来定位一个特定的密钥(如果几乎满了)。

您可以对此进行扩展,以查看如果哈希函数使用k位,则bin大小为2^(n-k)。

因此,k位散列函数==>不超过2^k个有效的bin==>每个bin最多2^(n-k)个n位键==>(n-k)个步骤(bst)来解决冲突。实际上,大多数散列函数的“效率”要低得多,并且需要/使用超过k位才能生成2^k个容器。所以即使这样也很乐观。

您可以这样查看它——您需要~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或list)的操作,您将执行o(n)操作(回调键为n位);如果您执行第二个散列,那么,如果第二个散列发生冲突,您将遇到相同的问题。所以O(1)不是100%保证的,除非你没有冲突(你可以通过一张比钥匙有更多箱子的桌子来提高机会,但仍然如此)。

在这种情况下,考虑另一种选择,例如bst。有c个键,所以平衡的bst将是o(logc)深度,所以搜索需要o(logc)步骤。然而,在这种情况下的比较将是O(N)操作…因此,在这种情况下,散列似乎是一个更好的选择。

有两种设置可以让您 O(1) 最坏的时候。

1. 如果您的设置是静态的,那么fks散列将得到最坏的情况 O(1) 保证。但正如你所指出的,你的设置不是静态的。
2. 如果使用杜鹃散列,那么查询和删除是 O(1) 最坏的情况,但插入只是 O(1) 预期。如果您对插入总数有一个上限,并将表大小设置为大约大25%,那么杜鹃散列就可以很好地工作。

抄袭 here

根据这里的讨论,如果x是bin表中元素的上限,那么一个更好的答案是o(log(x)),假设一个有效的bin查找实现。

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 元素散列到同一个bucket,您的算法将 o(n) 是时候遍历那个bucket中的链表了。不管我们尝试了多少次挑战,对手总是赢的,这就是你的算法有多糟糕,最坏的情况 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 碰撞 哈希模m ,并将其发送到步骤(3),在运行时交叉手指 H[r] 会是一样的 搞砸 他们选择了。

对对手来说,这是一个严肃的赌注,他精心制作的名单在下面相撞 搞砸 ,但将只是中任何其他哈希函数下的随机输入。 H . 如果他赢了这场赌局我们的运行时间将是最坏的情况 o(n) 像以前一样,但如果他输了,我们只是得到一个随机输入,取平均值 O(1) 时间。事实上,大多数时候对手都会输,他每一次都会赢一次 |H| 挑战,我们可以 H* 非常大。

将此结果与以前的算法(对手总是赢得挑战)进行对比。在这里手写一点,但是自从 大多数时候 对手会失败,这对于对手可以尝试的所有策略都是正确的,尽管最坏的情况是 o(n) , the 预期最坏情况 事实上 O(1) .

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