Question: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:01020I 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 + 0startOfHashTable + 10startOfHashTable + 20The 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 = 010 % 3 = 120 % 3 = 2This 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?
How are hash table's values stored physically in memory?
data structures;hash tables;memory allocation