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.
On
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.
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.