2

假设有一个哈希函数。它存储“n”个键值对。如果我需要特定键的值，哈希函数会遍历所有键以找到我们正在寻找其值的键。如果是，那么复杂性是 O(1) 怎么来的？哈希如何查找键？

4

3 回答 3

3

不，这不是哈希表的工作方式。哈希表本质上是一个数组，将值存储在与其键的哈希相对应的索引处。所以，假设我想将一个字符串映射"abc"到另一个字符串"xyz"，并假设"abc"哈希为 42。我要做的是转到表的索引 42 并将字符串放在"xyz"那里。现在，如果稍后我想找到与 string 关联的值"abc"，我会再次对其进行散列并转到相应的索引 (42)，在"xyz"那里找到。这总体上是一个 O(1) 操作。总之：

将“abc”映射到“xyz”...

1.哈希（“abc”）= 42

2. 放入“xyz”表：

 ---+------------------------------------------------+---
... | | | "xyz" | | | ...
 ---+------------------------------------------------+---
       40 41 42 43 44

之后...

1.查询“abc”

2.哈希（“abc”）= 42

3.查看索引42，找到值“xyz”

为了描述哈希表的工作原理，我稍微简化了一点，我敦促您阅读哈希表Wikipedia 文章以获得更深入的描述。另请注意，很多时候您会看到哈希表实现为链表数组，以解决两个键哈希到相同数字的情况（所谓的哈希冲突）。使用普通数组将无法处理这种情况，因为我们无法在同一位置存储多个值。例如，这就是 Java 如何实现HashMap.

例如，以上面的例子为例，假设我们也想映射"123"到"pqr"，并假设它"123" 也散列到 42。最终结果看起来像这样：

       40 41 42 43 44
 ---+------------------------------------------------+---
... | | | + | | | ...
 ---+-----------------|-----------------+---
                      |
              +---------------+
              | "ABC" | "xyz" |
              +---------------+
                      |
              +---------------+
              | “123” | "pqr" |
              +---------------+

请注意，我们知道必须将键与值一起显式存储。现在，如果我们想用 key 进行查询，"123"我们会去它的哈希位置 (42) 并遍历在那里找到的链表，直到找到一个带有 key 的链表"123"。然后我们将返回相应的值，"pqr"。

此时你可能有两个问题：

  • 该函数如何hash()在 O(1) 中运行？
  • 如果我们需要遍历一个链表，整个操作怎么可能是O(1)呢？

至于第一个问题，在谈论哈希表的复杂性时，通常不会考虑哈希过程（虽然实际上可能不是恒定时间操作），仅仅是因为与其他方法相比，它被认为不是很耗时后续流程。事实上，在许多情况下，散列实际上是恒定的。例如，由于字符串在许多语言中是不可变的，因此它们的哈希值通常只计算一次然后缓存，导致在第一次哈希操作后进行恒定时间哈希。

至于第二个问题，当我们有一个好的散列函数和一个合理大小的表时，形成的链表应该很短（长度大概不超过3）。因此，遍历过程被认为是常数时间。

于 2013-10-06T12:27:14.640 回答
1

名称中的“哈希”是一个函数，它基本上将键转换为该键的（理想情况下）唯一索引。在实践中，每个哈希都是一个“桶”，它可能包含多个值，以允许冲突。

另见http://en.wikipedia.org/wiki/Hash_function

于 2013-10-06T12:27:18.003 回答
0

虽然早期的两个答案都是正确的（我都投了赞成票），但我想增加一些见解。

首先，哈希表是一种抽象数据类型，这意味着可以在特定实现中使用许多数据结构和检索算法。数组、二叉搜索树、字典等只是一些可能实现的示例。

其次，重要的一点是访问键值的平均情况检索是常数时间，即 O(1)，而不是最坏情况。

因此，密钥映射到一个理想的唯一存储位置。但是，在实际场景中总是可能发生冲突，并且通过以某种方式存储这些多个值来处理冲突（例如维护链接列表、树或另一个二级哈希）。

关键是，对于一个好的散列函数，与正常的常数时间索引访问相比，冲突是非常罕见的。因此，短语平均案例。

在哈希函数的最坏情况下，根据键检索值永远不会是 O(1)。它可以是 log(n) 甚至比这更糟。但它的发生频率是如此之小，对于每个好的散列函数，平均情况复杂度仍然保持在 O(1) 即恒定时间。

于 2013-10-06T13:07:50.543 回答