How are hash table's values stored in memory such that space if efficiently used and values don't have to be relocated often?
My current understanding (could be wrong):
Let's say I have 3 objects stored in a hash table. Their hash functions generate these values:
I would presume that the pointers of these objects would not be stored at the following memory addresses because there would be huge gaps between them:
- startOfHashTable + 0
- startOfHashTable + 10
- startOfHashTable + 20
The Wikipedia article on hash tables says that the "index" is computed as such:
hash = hashfunc(key) index = hash % array_size
So in my example, the indices would be:
- 0 % 3 = 0
- 10 % 3 = 1
- 20 % 3 = 2
This gets rid of the huge gaps that I mentioned before. Even with this modulo scheme, there's problems when you add more objects to the hash table. If I add a fourth object to the hash table, I would need to apply % 4 to get the index. Wouldn't that invalidate all the % 3's that I did in the past? Would all those previous % 3's need to be relocated to the % 4 locations?