如果项目是随机组织的，那么表格如何知道从哪里开始查找呢？
在一个非随机表格中，项目是根据某些特征进行组织的（例如姓名）。因此，如果表格需要查找有关“约翰”的任意信息，它可以从“J”桶开始查找。
然而，在通用哈希表中，项目是随机排列的。没有定义的特征。因此，要查找有关“约翰”的任意信息，表格不就必须查看每个桶吗？
这不是一种巨大的时间浪费吗？这就像在家里查找勺子时需要查看每个橱柜。
在通用哈希表中查找项目？
24
- fdh
2
关键在于理解随机化数据结构（或随机化算法）中的“随机化”部分 :) - Oerd
一个合适的散列函数应该生成确定性输入（也就是说，对于某个输入 x，每次在 x 上运行它时都会生成相同的哈希值 h）。这使得哈希表可以按照它们所做的那样运作，其中键实际上只是从输入生成的哈希值。 - wkl
3个回答
66
虽然之前的答案基本上是正确的，但它们没有直接涉及到通用哈希算法中的随机部分。通用哈希算法计算关键字的哈希值时不使用随机数。随机数仅在初始化哈希表时用于从哈希函数族中选择一个哈希函数。这可以防止拥有哈希函数详细信息的对手设计出最坏的关键字集。
换句话说，在哈希表的生命周期中，给定关键字的桶是一致的。但是，下一个实例（例如程序下次运行）可能会将同一个关键字放置在不同的桶中。
- Chris Thornhill
9
6谢谢！您做出了关键的澄清：“随机数仅在哈希表初始化时用于从哈希函数族中选择一个哈希函数。” - Yiling
8我读了Cormen-Leiserson-Rivest-Stein算法书中关于这个主题（通用哈希）的整章内容，但仍然让我感到困惑：如果每次插入新元素时都要滚动一个新的哈希函数，那么如何搜索键呢？
这个答案把一切都解释清楚了。谢谢！ - Croo
3这就是确切的答案，没有多余也没有少。 - Eric Z
6我也误读了通用哈希的描述。Cormen/Leiserson的书中指出：“在执行开始时，我们从一个经过精心设计的函数类中随机选择哈希函数。”（我强调）和“即使对于相同的输入，算法在每次执行时的行为也可能不同”（第265页）。我曾将“执行”解释为执行插入项的函数执行。现在清楚了，“执行”指的是应用程序的执行或哈希类的每个实例化。 - cod3monk3y
2我仍然想澄清一件事。这是否意味着在哈希表的初始化阶段选择的“哈希函数”从哈希函数族中用于哈希键的哈希表的生命周期，对吗？如果是这样，我不明白这个算法有什么随机性。在我看来，在选择了哈希函数之后，它的“随机性”等同于除法方法。 - Kin Cheung
显示剩余4条评论
6
哈希看起来随机，但它是确定性的，也就是说，特定的输入总是产生相同的哈希值。
因此，在想要在哈希表中插入项时，您需要首先为该输入生成哈希。然后，使用该哈希值索引到表中，并在表中的该位置插入您的项。在典型情况下，您有一个被视为键的部分，以及与其关联的一些更多信息（例如，您可以通过名称查找人员，并且每个名称都有关于该人员的信息）。
稍后，当您想要查找（与之关联的）特定键（在本例中为人员）的信息时，输入和哈希键以找到哈希表中正确的位置以查找该信息。
这确实跳过了一些关键细节，例如如何处理两个或更多输入恰好生成相同的散列值（除非您对可允许的输入施加一些限制，否则无法避免）。有各种处理此类情况的方法，例如仅顺序查看表以查找下一个空闲点，重新散列以在表中找到另一个点，或构建类似于散列到相同值的项目的链接列表。
无论如何，应该添加的是，确实存在使用哈希表的用例，使其最终看起来有点像你所推测的那样。例如，当您想要查看哈希表的所有内容（而不仅仅是一次查找一个项目）时，通常确实需要扫描整个表。即使您的哈希表几乎为空，您通常也必须从一端扫描到另一端，查找每个实际使用的条目。当您这样做时，会按照相当随机的顺序获取项目。
这指出了哈希表的另一个缺点-通常需要与单个原始记录进行精确匹配才能正常工作。例如，让我们考虑一些基于我的姓氏进行的查询。假设您对整个姓氏进行了索引，那么找到"Coffin"将很容易-但是至少在大多数普通哈希函数中，搜索以"Cof"开头的内容将明显变慢，就像"查找"Coffin"和"Demming"之间的所有名称"一样。
因此，您有一半的正确性-虽然哈希表通常非常适用于一些特定情况（主要是搜索精确匹配），但您概述的一般思路（浏览整个表以查找数据）几乎是某些其他目的唯一的选择，因此，如果您想支持除精确匹配外的任何内容，则可能更喜欢其他数据结构。
这主要是处理散列表的最常见用法/类型。可以创建哈希函数，至少在不同程度上弯曲（如果不是彻底破坏）这些规则。在大多数情况下，这些涉及一些妥协。例如，给定地理信息作为输入，可以通过简单地截断坐标（或其中一个坐标）来创建哈希（某种程度上），以获得更低精度的相同信息。这至少对信息进行了一定的组织，因此靠近的东西具有类似的哈希值，使查找相邻数据更容易。然而，这通常会导致更多的冲突（例如，您将获得许多项散列到一个值，以便大城市的市中心）。
具体来看通用哈希，它增加了一个额外的元素：不是单个哈希函数，而是一个哈希函数族，从中“随机”选择。当通用哈希用于实现哈希表时（并非总是如此 - 它通常用于诸如消息认证代码之类的东西），通常不会每次插入项目时随机选择哈希函数。相反，通常选择一个哈希，并继续使用它，直到遇到一些固定数量的冲突。然后随机选择另一个哈希函数。
例如，在Cuckoo散列中（可能是最常用的通用哈希），您将哈希键以查找位置。如果已经占用，您就会“清除”那里的现有项，并重新哈希以查找其替代位置。它被插入那里。如果该插槽已经被占用，它将“清除”该插槽中已经存在的项目，然后模式重复。
当您搜索项目时，您会对其进行哈希并查看该位置。如果为空，您立即知道您的项目不存在。如果该插槽已被占用，但不包含您的项目，则重新哈希以查找替代位置。在所使用的所有哈希函数中继续此模式（通常只有两个哈希函数，在Cuckoo哈希的情况下，但您可以明显地使用更多函数进行类似的算法）。
这可能会失败 - 进入无限循环或（几乎等效地）构建超过预设长度的链。在这种情况下，您重新开始，使用不同的哈希函数对表进行重建。
当使用开放式哈希（其中通用哈希是一种形式）时，删除往往是非常棘手的。特别是，我们必须确保在一个位置删除一个项目时，它不是在该位置发生碰撞的一系列项目的开头。在许多情况下，最有效的方法是为插槽添加第三个状态：如果从未被使用，则为空。如果当前已占用，则正在使用中。如果该处已删除物品，则已删除。这样当您搜索项目时，如果遇到“已删除”插槽，则继续搜索您的项目（而如果您到达从未使用过的插槽，则可以立即停止搜索-您的项目显然从未插入）。
因此，在想要在哈希表中插入项时，您需要首先为该输入生成哈希。然后，使用该哈希值索引到表中，并在表中的该位置插入您的项。在典型情况下，您有一个被视为键的部分，以及与其关联的一些更多信息（例如，您可以通过名称查找人员，并且每个名称都有关于该人员的信息）。
稍后，当您想要查找（与之关联的）特定键（在本例中为人员）的信息时，输入和哈希键以找到哈希表中正确的位置以查找该信息。
这确实跳过了一些关键细节，例如如何处理两个或更多输入恰好生成相同的散列值（除非您对可允许的输入施加一些限制，否则无法避免）。有各种处理此类情况的方法，例如仅顺序查看表以查找下一个空闲点，重新散列以在表中找到另一个点，或构建类似于散列到相同值的项目的链接列表。
无论如何，应该添加的是，确实存在使用哈希表的用例，使其最终看起来有点像你所推测的那样。例如，当您想要查看哈希表的所有内容（而不仅仅是一次查找一个项目）时，通常确实需要扫描整个表。即使您的哈希表几乎为空，您通常也必须从一端扫描到另一端，查找每个实际使用的条目。当您这样做时，会按照相当随机的顺序获取项目。
这指出了哈希表的另一个缺点-通常需要与单个原始记录进行精确匹配才能正常工作。例如，让我们考虑一些基于我的姓氏进行的查询。假设您对整个姓氏进行了索引，那么找到"Coffin"将很容易-但是至少在大多数普通哈希函数中，搜索以"Cof"开头的内容将明显变慢，就像"查找"Coffin"和"Demming"之间的所有名称"一样。
因此，您有一半的正确性-虽然哈希表通常非常适用于一些特定情况（主要是搜索精确匹配），但您概述的一般思路（浏览整个表以查找数据）几乎是某些其他目的唯一的选择，因此，如果您想支持除精确匹配外的任何内容，则可能更喜欢其他数据结构。
这主要是处理散列表的最常见用法/类型。可以创建哈希函数，至少在不同程度上弯曲（如果不是彻底破坏）这些规则。在大多数情况下，这些涉及一些妥协。例如，给定地理信息作为输入，可以通过简单地截断坐标（或其中一个坐标）来创建哈希（某种程度上），以获得更低精度的相同信息。这至少对信息进行了一定的组织，因此靠近的东西具有类似的哈希值，使查找相邻数据更容易。然而，这通常会导致更多的冲突（例如，您将获得许多项散列到一个值，以便大城市的市中心）。
具体来看通用哈希，它增加了一个额外的元素：不是单个哈希函数，而是一个哈希函数族，从中“随机”选择。当通用哈希用于实现哈希表时（并非总是如此 - 它通常用于诸如消息认证代码之类的东西），通常不会每次插入项目时随机选择哈希函数。相反，通常选择一个哈希，并继续使用它，直到遇到一些固定数量的冲突。然后随机选择另一个哈希函数。
例如，在Cuckoo散列中（可能是最常用的通用哈希），您将哈希键以查找位置。如果已经占用，您就会“清除”那里的现有项，并重新哈希以查找其替代位置。它被插入那里。如果该插槽已经被占用，它将“清除”该插槽中已经存在的项目，然后模式重复。
当您搜索项目时，您会对其进行哈希并查看该位置。如果为空，您立即知道您的项目不存在。如果该插槽已被占用，但不包含您的项目，则重新哈希以查找替代位置。在所使用的所有哈希函数中继续此模式（通常只有两个哈希函数，在Cuckoo哈希的情况下，但您可以明显地使用更多函数进行类似的算法）。
这可能会失败 - 进入无限循环或（几乎等效地）构建超过预设长度的链。在这种情况下，您重新开始，使用不同的哈希函数对表进行重建。
当使用开放式哈希（其中通用哈希是一种形式）时，删除往往是非常棘手的。特别是，我们必须确保在一个位置删除一个项目时，它不是在该位置发生碰撞的一系列项目的开头。在许多情况下，最有效的方法是为插槽添加第三个状态：如果从未被使用，则为空。如果当前已占用，则正在使用中。如果该处已删除物品，则已删除。这样当您搜索项目时，如果遇到“已删除”插槽，则继续搜索您的项目（而如果您到达从未使用过的插槽，则可以立即停止搜索-您的项目显然从未插入）。
- Jerry Coffin
1
哈希表不是随机组织的，而是按照哈希值进行组织。通过哈希值搜索表以检索正确的哈希组。
- rossum
2
我知道，但哈希值是随机的，不是吗？就是指分配给每个信息片段的值。例如，如果约翰被分配了哈希值2，而乔治被分配了哈希值5，如果表格要查找乔治，那么它不得不搜索第5个和第3个桶吗？哈希值的分配是随机的，那么表格怎么可能知道需要搜索的信息的哈希值呢？ - fdh
3计算哈希值。如果你想查找George，那么重新计算哈希值，得到5。然后直接跳转到第5个桶。本质上，你是将哈希值作为索引进入哈希表。一个好的哈希方法会随机地分散输入到可用的桶中，使得所有的桶大致相同大小。这并不意味着哈希值是随机分配的。可以参考http://isthe.com/chongo/tech/comp/fnv/，了解如何计算哈希值的例子，例如FNV哈希。 - rossum
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接