How are hash table's values stored physically in memory?

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:

• 0

• 10

• 20

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?

The entries of a hash table are stored in an array. However, you have misunderstood the application of the modulo operator to the hash values. If the hash table is stored in an array of size $n$, then the hash function is computed modulo $n$, regardless of how many items are currently stored in the table. So, in your example, if you were storing the items in an array of size 6, the three items with hash values 0, 10 and 20 would be stored at locations 0, 4 and 2, respectively. If you added a fourth element with hash value, say, 31, that would be stored at location 1, without needing to move any of the first three items. If your hash table was becoming full and you wanted to move it into a bigger array, then you would need to recalculate the locations of all the items in the table and move them appropriately.

StackExchange Computer Science Q#39862, answer score: 16