如何实现动态大小的哈希表？ [英] How to implement a dynamic-size hash table?

问题描述

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

但实际上，在哈希表类型。当我使用它们时，我不需要事先知道散列表的大小。我只是把任何我想要的东西。例如，在 Ruby 中：

  h = {} 
 10000000.times {| i | h [i] = rand（10000）} 
  

如何做？

解决方案

请参阅 <维基百科的哈希表文章中的em>动态调整大小部分。

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

另外，根据哈希表的类型，这个调整大小可能没有必要进行正确性（即使没有调整大小）仍然可以工作），但是这一定是必须的。

I know the basic principle of the hash table data structure. If I have a hash table of size N, I have to distribute my data into these N buckets as evenly as possible.

But in reality, most languages have their built-in hash table types. When I use them, I don't need to know the size of hash table beforehand. I just put anything I want into it. For example, in Ruby:

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

How can it do this?

解决方案

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

The usual approach is to use the same logic as a dynamic array: have some number of buckets and when there is too much items in the hash table, create a new hash table with a larger size and move all the items to the new hash table.

Also, depending on the type of hash table, this resizing might not be necessary for correctness (i.e. it would still work even without resizing), but it is certainly necessary for performance.

这篇关于如何实现动态大小的哈希表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！