如何实现一个动态大小的哈希表？

Question

我了解哈希表数据结构的基本原理。如果我有一个大小为N的哈希表，我必须尽可能均匀地将我的数据分配到这些N个桶中。

但实际上，大多数编程语言都具有内置的哈希表类型。当我使用它们时，我无需预先知道哈希表的大小。我可以随意将任何东西放入其中。例如，在Ruby中：

h = {}
10000000.times{ |i| h[i]=rand(10000) }

它如何实现这个功能？

- Lai Yu-Hsuan

Answer 1

请查看Wikipedia上关于哈希表的动态调整部分。通常的做法是使用与动态数组相同的逻辑：拥有一定数量的桶，当哈希表中的项太多时，创建一个具有更大大小的新哈希表，并将所有项移动到新哈希表中。此外，根据哈希表的类型，这种调整可能不是必需的（即使不进行调整，它仍然可以正常工作），但对于性能来说绝对是必要的。

- svick

---

一种不错的重哈希方法是将表格大小加倍，当您搜索一个值时，可以对其键进行哈希处理，并在哈希表中执行取模搜索，从 hash % current_size 开始，然后再依次为 hash % current_size/2，以此类推。 当您找到该值时，可以重新哈希它。这样，您就可以进行懒惰重哈希而不会失去太多性能，因为常访问的值会自动被重哈希。 - Not_a_Golfer

@DvirVolk，懒惰的重排很好。您已经知道最顶层哈希表中的条目，并知道从较低的哈希表中插入的位置。但是，您可能会遇到某些条目将持有整个空桶表的情况。我理解维基百科上的“增量调整大小”是权衡速度和数据大小的解决方案（最终您将拥有2 * N个桶，其中N是最顶层哈希表的大小）。将大小加倍对于“复制所有条目”非常有用，因为您必须将单个桶分成两个或将两个桶合并为一个（无需重新计算哈希），并重用旧桶的链接列表。 - ony

@Not_a_Golfer 我刚想到了这个想法，但我正在努力寻找关于这种技术的理论分析，你知道吗？ - Asad-ullah Khan