哈希表：为什么需要桶？

Question

据我所知，哈希函数的目的是尽可能均匀地分布数据。当发生冲突时，你有几个选择：

1. 查找下一个空槽
2. 生成另一个哈希值并将其放置在其他位置
3. 将其放入溢出容器（可以是列表、另一个哈希表或其他任何东西）
4. 将其放入下一个可用的桶槽中

最后一种方法让我感到困扰，因为如果你要创建一个每个地址都有两个插槽的哈希表，为什么不直接创建一个两倍大小的哈希表呢？除非桶是动态分配的。就我而言，我的情况是表上的数据位于磁盘上，这意味着需要另一个磁盘访问+管理可变长度数据。然而，似乎桶仍然是最受青睐的选项，为什么会这样？我错过了什么吗？

- Jake Freelander

---

“不过在我看来，桶仍然是最受青睐的选择。”为什么呢？第一个选项被称为线性哈希，它是最简单的选项（有点出人意料），在大多数情况下仍然是最有效的。 - leventov

“1. 寻找下一个空槽”和“4. 将其放入下一个空闲的桶槽”有何不同？您所使用的术语是否固定了每个桶中的“槽数量”？当您说“每个地址有2个槽”时，是指每个桶吗？“桶是动态分配的”-您是否再次引用“3.”-因为动态桶听起来像是列表/向量。 - Tony Delroy

无论如何，对于磁盘表来说，加载磁盘区域是昂贵的，因此最好在转向另一个磁盘区域之前使用任何空闲桶。我不建议每个桶使用多个“插槽” - 只需尝试另一个桶即可。一个好主意是使用“位移列表”，跳过一定数量的桶（在已加载的磁盘区域内进行几次重试，然后进行暴力搜索，然后移动到另一个磁盘区域或重新散列）。位移列表应避免其总和重复的运行：例如1 3 6是可以的（3-1！= 6-3，n *（3-1）！= 6-1），然后11就不好了：6-1 == 11-6，13可以... - Tony Delroy

@TonyD的第一条评论：由于在＃4中，您将针对每个哈希预分配多个kvps空间，因此它与其他情况不同。是的，是的。不，我的意思是，如果为节省内存而动态分配存储桶，则存储桶对我来说才有意义，是的。 第二条评论：是的，那基本上结束了＃2的讨论。而且，是的，那听起来是个好主意。 - Jake Freelander

@KarliRaudsepp: 每个哈希值有多个预分配空间的想法并不实用...考虑到额外的内存使用，最好让哈希在所有可用内存上展开，这样一开始就会有更少的碰撞，然后使用任何链式/重新散列/位移列表技术来处理冲突。 - Tony Delroy

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不发生冲突。根据您的应用程序，这可能是一个真正的问题。

另一方面，如果您使用桶，就像您提到的那样，您需要进行某种外部内存访问，在主存储器中速度会比较慢（由于引用局部性），并且在磁盘上速度很慢。这是一个相当好的论据，说明使用链式哈希在磁盘上不是一个好主意，而线性探测可能是一个合理的折衷方案。

希望这可以帮助您！

- templatetypedef