data-structures - 如何实现动态大小的哈希表？

Question

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

但实际上，大多数语言都有其内置的哈希表类型。当我使用它们时，我不需要事先知道哈希表的大小。我只是把我想要的东西放进去。例如，在 Ruby :

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

它怎么能做到这一点？

Answer 1

见 the Dynamic resizing section of the Hash table article on Wikipedia .

通常的做法是使用与 a dynamic array 相同的逻辑。 : 有一定数量的bucket，当哈希表中的项目太多时，创建一个更大的新哈希表，并将所有项目移动到新的哈希表中。

此外，根据哈希表的类型，这种调整大小可能不是正确性所必需的(即，即使没有调整大小，它仍然可以工作)，但对于性能来说肯定是必要的。