How to use hash tables when amount of slots is unknown?

Question

How do I use hash tables & chaining when the amount of slots required is yet unknown at usage? In other words I need to use the hash table before all keys and values for it are defined, how do I do this? I can't seem to figure it out since I assumed I'd need to know the amount of slots required in order to make a hash function to map the keys to those slots, but maybe I did not quite get the idea right of a hash table.

If anyone could help me out it'd be much appreciated!

Best regards, Skyfe.

Answer 1

One way to do so is simply adopt the idea of amortized dynamic arrays.

You decide on a few factors, say - an initial size, a maximal load, and a growth factor. As an example, you could use initial size = 100, maximal load = 0.5, and growth factor = 2.

If enough items are inserted, at some point you'll have more than 50 = 100 * 0.5 items. At this point you allocate an array of size 200 = initial size * growth factor = 100 * 2, redistribute the items, and erase the old array. Etc.

Two notes:

• In practice, you wouldn't want to mulitply exactly by a given growth factor, as you probably want the array length to be prime. So you multiply by the factor, find the nearest larger prime (which you should precompute).

• Shrinking is the same, but you should use different factors for hysteresis. See the above link.

Answer 2

This is similar to what you want: How to implement a dynamic-size hash table?

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.