How to implement a hash table of dynamic size?

Question

I know the basic principle of a hash table data structure. If I have a hash table of size N, I must equally distribute my data in these N-buckets.

But in fact, most languages ​​have built-in hash tables. When I use them, I do not need to know the size of the hash table in advance. I just put whatever I want into it. For example, in Ruby :

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

How can I do that?

Answer 1

See the “Dynamic Resizing” section of the hash table article on Wikipedia .

The usual approach is to use the same logic as the dynamic array : to have a certain number of buckets and when there are too many elements in the hash table, create a new hash table with a large size and move all the elements to the new hash table.

In addition, depending on the type of the hash table, this resizing may not be necessary for correctness (i.e., it will work even without resizing), but it is certainly necessary for performance.