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

Question

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

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

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

它怎么能这样做？

Answer 1

请参阅Wikipedia 上哈希表文章的动态调整大小部分。

通常的方法是使用与动态数组相同的逻辑：拥有一定数量的桶，当哈希表中的项目太多时，创建一个更大大小的新哈希表，并将所有项目移动到新哈希表中。

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