c - 扩展哈希表而不重新哈希？

Question

我正在寻找一个不需要rehash 来扩展和收缩的哈希表 数据结构？Rehash 是一项耗费 CPU 的工作。我想知道是否有可能以一种完全不需要重新哈希的方式设计哈希表数据结构？您以前听说过这样的数据结构吗？

Answer 1

does not require rehash for expansion and shrink? Rehash is a CPU consuming effort. I was wondering if it is possible to design hash table data structure in a way that does not require rehash at all? Have you heard about such a data structure before?

这取决于你所说的“rehash”:

• 如果您的意思是表级重新散列不应在调整大小时将散列函数重新应用于每个键，那么对于大多数库来说这很容易:例如将 key 及其原始(预模表大小)真实散列值包装在一起 la struct X { size_t hash_; Key key_ };，为哈希表库提供返回 hash_ 的哈希函数，以及比较 key_ 的比较函数(取决于 的复杂性code>key_比较，可以使用hash_进行优化，例如lhs.hash_ == rhs.hash_ && lhs.key_ == rhs.key_).

  • 如果 key 散列特别耗时(例如，较长 key 的加密强度)，这将最有帮助。对于非常简单的散列(例如 int 的直通)，它会减慢你的速度并浪费内存。

• 如果您指的是增加或减少内存存储以及重新索引所有存储值的表级操作，那么是的 - 它可以避免 - 但要这样做，您必须从根本上改变哈希表的工作方式，和正常的性能配置文件。下面讨论。

仅作为一个示例，您可以通过让自定义哈希表 (C) 具有一个 H** p 来利用更典型的哈希表实现(我们称它为 H)——最大为初始大小limit - 将使 p[0] 成为 H 的唯一实例，并简单地传递操作/结果。如果表超出该范围，您将保持 p[0] 引用现有 H，同时创建第二个 H 哈希表以供 p[1] 跟踪。然后事情开始变得冒险:

• 要在 C 中搜索或删除，您的实现需要先搜索 p[1]，然后搜索 p[0] 并报告来自其中任何一个的任何匹配项

• 要在 C 中插入一个新值，您的实现必须确认它不在 p[0] 中，然后插入到 p[1]

  • 对于每个 insert(甚至可能用于其他操作)，它可以选择性地将任何匹配项 - 或任意 p[0] 条目 - 迁移到 p [1] 如此逐渐 p[0] 清空；您可以轻松保证 p[0] 在 p[1] 填满之前为空(因此需要更大的表)。当 p[0] 为空时，您可能需要 p[0] = p[1]; p[1] = NULL; 保持简单的心智模型 - 很多选项。

一些现有的哈希表实现在遍历元素时非常有效(例如 GNU C++ std::unordered_set)，因为有一个包含所有值的单链表，而哈希表实际上只是指向链表的指针集合(用 C++ 的说法，迭代器)。这可能意味着，如果您的唯一/较大哈希表的利用率低于某个阈值(例如 10% 负载因子)，您知道您可以非常有效地将剩余元素迁移到较小的表。

一些哈希表使用这些技巧来避免在重新哈希过程中突然产生沉重的成本，而是将痛苦更均匀地分散到许多后续操作中，避免可能令人讨厌的延迟峰值。

一些实现选项只对一个开放的或一个封闭的哈希实现有意义，或者只有当键和/或值是小的或大的时候才有用，这取决于表是否嵌入他们或指向他们。了解它的最佳方式是编写代码....