When provided with a second collision case, how is this resolved?
I.E:
Let's say we have an array of numbers:
[22, 1, 13, 11, 24, -1, -1, -1, -1, -1, -1]
Where -1 indicates empty in the array....
if we were to attempt to insert 33 using
h1(key) = key % 11
h2(key) = 7 - (key % 7)
Passing in 33 would give 2, where the array location 2 is already occupied (with 13). How do we handle this collision case? Do we pass the returned mod value into h2 again? Do we replace the value @ that array value? (I suspect the latter is not the case.)
Edit: Added parenthesis to h2
With double hashing, you compute the position as:
pos = (h1 + i * h2) mod table_size
The trick here is to increment i until an empty position in the hash table is found. Therefore the computation is not only done once, but multiple times until a slot has been found. See the Wikipedia article for details.
There are other forms of open addressing similar to double hashing that are very efficient too, for example cuckoo hashing and robin-hood hashing.