I am trying to implement a hash table for string keys as part of a university project. I was able to make a basic, working implementation without major issues. I am now trying to optimize the thing to go closer to a O(1) expected lookup / insert time.
I was reading up on hash functions and in particular, the MAD method for hashcode compression. From my understanding, the MAD methods needs parameters (namely a multiplier a, a prime p and and offset O):
index = ((a * i + o ) % p ) % N
, where i is the hashcode and N is the size of the underlying array to store the data. It is noted everywhere that p must be bigger than N, which seems natural if we want to insert the data uniformly.
Now, my misunderstanding comes from hash tables for which we do not know the numbers of keys that will be inserted ahead of time, and have no fixed capacity. Is MAD still a viable technique? From my understanding, the parameters need to be tuned to ensure an even distribution of the keys across the whole array.
A lot of hash map literature I could get my hands on also seems to imply that the maps are of fixed sizes. I am trying to figure out the same things for the table size (a lot of people talk about a prime-sized table, which seems unrealistic for resizable hash tables).