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

Question

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

在非随机表中,项目根据某些特征进行组织.(即姓名).因此,如果表需要查找有关"John"的任意信息,它可以开始查看"J"桶.

但是,在通用哈希表中,项目是随机排列的.没有明确的特征.因此,为了找到关于"约翰"的任意信息,表格是否必须查看每个桶？

这不是浪费时间吗？这就像透过你家里的每个柜子找到一把勺子.

Answer 1

虽然先前的答案基本上是正确的,但它们并不直接解决通用散列算法的随机部分.在计算密钥的散列时,通用散列算法不使用随机性.随机数仅在哈希表的初始化期间使用,以从一系列哈希函数中选择哈希函数.这可以防止能够访问散列函数细节的对手设计最坏情况的密钥集.

换句话说,在哈希表的生存期内,给定密钥的桶是一致的.但是,不同的实例(例如下次程序运行时)可能会将相同的密钥放在不同的存储桶中.

Answer 2

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

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

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

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

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

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

因此，您说对了一半——虽然哈希表在某些特定情况下通常非常快（主要是搜索完全匹配），但您概述的总体思路（扫描整个表以查找数据） ) 几乎是可用于其他目的的唯一选择，因此如果您想支持除精确匹配之外的任何内容，则可能更喜欢不同的数据结构。

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

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

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

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

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

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