有哪些算法可用于调整哈希表的大小？

Question

我已经在C语言中实现了自己的哈希表函数，但目前它不支持调整大小。 我想知道除了创建一个新的空哈希表并将所有内容移动到那里的暴力方式之外还存在哪些算法？

- Blagovest Buyukliev

Answer 1

有增量调整大小的功能。

来自维基百科：

增量调整大小

一些哈希表实现，特别是在实时系统中，不能承担一次性扩大哈希表的代价，因为它可能会中断时间关键操作。如果无法避免动态调整大小，则解决方案是逐步执行调整大小：

在调整大小期间，分配新哈希表，但保持旧表不变。 在每个查找或删除操作中，检查两个表。 仅在新表中执行插入操作。 每次插入时，从旧表中移动r个元素到新表中。 当旧表中的所有元素都被删除时，释放它。

为确保在需要扩大新表之前完全复制旧表，必须在调整大小期间将表的大小至少增加（r + 1）/ r倍。

因此，这并不是将所有元素从旧表移动到新表的聪明方法（如果有的话，我还没有看到）；相反，它通过允许逐步迁移来减轻调整大小的负担。

- danben

Answer 2

维基百科在这个主题上有一些智慧的话语。

此外，这不是一个解决方案，但可以作为其中的一部分——如果您正在使用Windows，则可以使用VirtualAlloc函数族，它允许您保留地址空间而不实际提交内存页面。也就是说，在门外汉的术语中，您会做类似于“malloc”的事情，并告诉它“保留1000MB，但仅使前10个可用”。因此，如果您写入超过10MB，您将获得通常的崩溃。但是当扩展时间到来时，您只需说“好的，请在第一个之后再给我10MB”。下一个10MB将在第一个10MB直接后面的地址处提供。这就像调整数组大小一样。实际使用的RAM将仅为所需的数量，但是预先保留了内存地址，以便其他内存分配操作不使用它们。

- Vilx-

---

这是一个相当聪明的调整数组大小的方法 - 如果你拥有可用的地址空间（x64），它非常适用 - 但对于哈希表而言，它无法奏效，你仍然需要重新计算哈希值（而且在原地进行此操作更加复杂）。 - Eloff

@Eloff - 好的，正如我所说 - 它本身并不是解决方案，只是其中的一部分。而且你不必保留太多额外的地址空间，只需要一些合理的数量即可。这并不是万能药，它只是使调整大小操作更快速。 - Vilx-

我现在明白你的意图了，但它是否能真正加快调整大小速度还是存在疑虑的。这里的主要开销不是内存分配，那只占很小一部分。所有的时间都花费在软页错误上，将新内存带入进程地址空间中（通常发生在内存分配器清零内存时），以及重新哈希和重新插入哈希表中所有元素所需的成本上。但对于动态数组来说，你不需要复制任何东西，并且你可以逐个支付软页错误（每次增加一页）现在这太棒了！ - Eloff

我可能对细微故障不太确定。但无论如何，提交和清零内存的成本是分配内存的主要成本部分。 - Eloff

@Eloff - 可能吧。但如果是这样的话，我很难看到虚拟内存分配器的这个特性还有其他可能的应用场景。 - Vilx-

Answer 3

通常的逃避方法是让客户端代码猜测最佳的桶数。这个方法可行，因为客户端通常可以合理猜测表中最终有多少元素。如果你想自动完成，则必须首先声明一个用于桶大小的质数数组。当看到某个桶的负载因子过高时，选择数组中的下一个质数，在新建桶列表并将元素从旧桶移动到新表之前，重新创建桶列表。

- Hans Passant