algorithm - 在通用哈希表中查找项目？

Question

如果项目是随机组织的，表格如何知道从哪里开始查找？

在非随机表中，项目是根据某些特征组织的。（即名称）。因此，如果该表需要查找有关“John”的一些任意信息，它可以开始在“J”存储桶中查找。

但是，在通用哈希表中，项目是随机排列的。没有明确的特征。因此，要找到一些关于“John”的任意信息，表格不是必须查看每个存储桶吗？

这不是非常浪费时间吗？这就像在你家的每个橱柜中寻找一把勺子一样。

Answer 1

虽然前面的答案基本上是正确的，但它们并没有直接解决通用散列算法的随机部分。通用散列算法在计算密钥的散列时不使用随机性。随机数仅在哈希表初始化期间用于从哈希函数族中选择哈希函数。这可以防止可以访问散列函数详细信息的对手设计最坏情况的密钥集。

换句话说，在哈希表的生命周期内，给定键的桶是一致的。但是，不同的实例（例如下次程序运行时）可能会将相同的密钥放在不同的存储桶中。

Answer 2

散列看起来或多或少是随机的，但它是确定性的——也就是说，特定的输入总是产生相同的散列值。

基于此，当您想在哈希表中插入一个项目时，您首先要为该输入生成哈希。然后，您使用它来索引表，并将您的项目插入表中的该位置。在典型情况下，您有一个部分被视为键，并且您有一些与此相关的更多信息（例如，您可能能够按姓名查找人员，并且每个姓名都有关于该人的信息）。

稍后，当您想要查找（相关的信息）特定键（在本例中为人）时，您输入并散列该键以在散列表中找到正确的位置来查找该信息。

这确实跳过了一些关键细节，例如您如何处理发生相同哈希值的两个或多个输入（这是不可避免的，除非您对允许的输入设置一些限制）。有多种方法可以处理此问题，例如仅按顺序查看表以找到下一个空闲位置，重新散列以在表中找到另一个位置，或者构建类似哈希到相同值的项目的链接列表。

无论如何，可能应该补充一点，在某些用例中，哈希表确实有点像您所推测的那样。仅举一个例子，当您想查看哈希表的所有内容（而不是一次仅查找一项）时，您通常确实会扫描整个表。即使您的哈希表几乎是空的，您通常也必须从一端扫描到另一端，寻找实际使用的每个条目。当你这样做时，你会以相当随机的顺序获得项目。

这指出了哈希表的另一个缺点——您通常需要与单个原始记录进行精确匹配才能使它们正常工作。例如，让我们考虑一些基于我姓氏的查询。假设您对整个姓氏进行了索引，找到“棺材”将是微不足道的——但至少对于大多数普通的哈希函数，搜索“以“Cof”开头的东西会慢得多，就像“找到所有的名字一样”在“棺材”和“戴明”之间。

因此，您有一半是正确的-虽然哈希表对于一些特定情况（主要是搜索完全匹配）通常非常快，但您概述的一般想法（扫描整个表以查找数据) 几乎是可用于其他目的的唯一选择，因此如果您想支持除完全匹配之外的任何内容，则可能需要使用不同的数据结构。

这主要处理哈希表的最典型用途/类型。可以创建至少在不同程度上弯曲（如果不是彻底破坏）这些规则的哈希函数。在大多数情况下，这些都涉及一些妥协。例如，给定地理信息作为输入，您可以通过简单地截断坐标（或其中一个坐标）来创建一个哈希（排序），以便以较低的精度获得相同的信息。这至少在一定程度上组织了信息，因此靠近的事物最终具有相似的哈希值，从而更容易找到相邻数据。然而，这通常会导致更多的冲突（例如，对于大城市的市中心，您会得到很多散列到相同值的项目）。

具体来看通用散列，这为难题增加了一个额外的元素：您拥有一系列散列函数，而不是单个散列函数，您可以从中“随机”选择。当使用通用哈希来实现哈希表时（并非总是如此——它也经常用于消息身份验证代码之类的事情），您通常不会在每次插入项目时随机选择哈希函数。相反，您通常会选择一个哈希，并继续使用它，直到遇到一些固定数量的冲突。然后你随机选择另一个哈希函数。

例如，在 Cuckoo 散列（可能是最常用的通用散列）中，您对密钥进行散列以查找位置。如果它已经被占用，你“踢出”那里的现有项目，并重新散列它以找到它的替代位置。它被插入那里。如果该插槽已被占用，它会“踢出”该插槽中已经存在的项目，并重复该模式。

当您搜索一个项目时，您对其进行哈希处理并查看该位置。如果那是空的，您会立即知道您的项目不存在。如果该插槽已被占用，但不包含您的项目，则您重新散列以找到备用位置。对尽可能多的散列函数继续这种模式（在布谷鸟散列的情况下通常只有两个，但您显然可以使用具有更多函数的其他类似算法）。

这可能会失败——进入一个无限循环，或者（几乎等同地）构建一个超过某个预设长度的链。在这种情况下，您重新开始，使用一对不同的哈希函数重新构建表。

当使用开放散列（其中通用散列是一种形式）时，删除往往是不平凡的。特别是，我们必须确保当我们在一个位置移除一个项目时，它不是在该位置发生碰撞的一系列项目的开始。在许多情况下，简单地为插槽添加第三个状态是最有效的：如果它从未被占用，则它只是空的。如果它当前被占用，则它正在使用中。如果一个项目在那里被删除，它就会被删除。这样，当您在搜索一个项目时，如果您遇到“已删除”的插槽，您会继续搜索您的项目（然而，如果您到达一个从未使用过的插槽，您可以立即停止搜索——您的项目清楚从未插入）。

Answer 3

哈希表不是随机组织的。它是按哈希值组织的。通过哈希值搜索该表以检索正确的哈希组。