哈希表 : why buckets?

Question

据我所知，散列函数的目的是尽可能均匀地分发数据，当您发生冲突时，您有多种选择:

寻找下一个空槽

生成不同的散列并尝试将其粘贴到其他地方

把它放在一个溢出容器中(可以是一个列表、另一个哈希表或其他任何东西)

把它放在下一个空闲的桶槽

最后一个让我感到困扰，因为如果您要为每个地址创建一个包含 2 个插槽的哈希表，为什么不制作一个两倍大的哈希表呢？除非桶是动态分配的。在我的情况下，表的数据位于磁盘上，这意味着另一个磁盘访问+管理可变长度数据。在我看来，虽然水桶仍然是最受欢迎的选择，但为什么呢？我错过了什么？

Answer 1

从关于这个问题的评论中的讨论中可以明显看出，有许多不同的方法可以实现哈希表。每个都有自己的权衡。

您的问题是为什么要使用分桶系统(封闭寻址或链式散列)而不是将对象放入下一个空闲槽(线性探测)。您指出将存储桶存储在外部存储器中需要在内存中的另一个位置进行查找，如果您将内容存储在磁盘上，这不是一个好主意。这些都是合理的担忧。但是，请记住以下几点。

首先，如果您使用分桶系统(每个哈希表槽是一个桶，并且所有具有相同哈希码的对象都被扔进同一个桶)，与使用开放寻址的线性探测等系统相比，您有一个优势:您唯一需要担心的冲突是具有相同哈希码的对象。例如，假设您将三个元素插入哈希表，它们的哈希码分别为 1、1 和 2。在封闭寻址(存储桶)中，无论何时执行查找 1，您都必须检查两个对象哈希码 1，但是如果您查找对象 2，则根本不需要进行任何冲突解决。另一方面，如果您使用线性探测，则在查找三个元素中的任何一个时可能会发生冲突。假设对象 A 的哈希码为 1，对象 B 的哈希码为 2，对象 C 的哈希码也为 1。按 A、C、B 的顺序插入对象将得到以下表格:

[ A ] [ C ] [ B ] [   ] [   ]
  1     2     3

现在，执行查找 C 或 B 将要求您对表进行线性扫描，即使 B 不与对象 A 或 C 发生冲突。根据您的应用程序，这可能是一个真正的问题。

另一方面，如果您使用分桶，正如您所提到的，您需要进行某种外部存储器访问，这在主存储器中会有点慢(由于引用的局部性)和磁盘上的冰川。这是一个很好的论据，解释了为什么链式散列对于磁盘上的散列表不是一个好主意，而线性探测可能是一个合理的折衷方案。

希望这可以帮助!