double hashing with collision on first and second hash functions-java

Question

For double hashing, if there is a collision with the first hash function, you'd use the second hash function, but what if there is still a collision? For example, let's say a hash table is size 15 and the hash function is (key + 3) % 15 and the second hash function is ((key % 8) / 3) + 2. Let's say "insert 59" goes to index 2 by the first hash function but there already is a key there. The second hash function would bring it to 3 but let's say there already is a value there too. Where would 59 be inserted on the hash table and why? Thanks

I specifically want to use double hashing, not chained hashing or linear probing.

Answer 1

This is implementation specific, but typically you'd use a linked list or other flexible data structure to managed colliding data.

From the java.util.HashMap javadoc:

It uses a hash-bucket approach; that is, hash collisions are handled by linking the new node off of the pre-existing node (or list of nodes). In this manner, techniques such as linear probing (which can cause primary clustering) and rehashing (which does not fit very well with Java's method of precomputing hash codes) are avoided. Under ideal circumstances (no collisions), HashMap offers O(1) performance on most operations (containsValue() is, of course, O(n)). In the worst case (all keys map to the same hash code -- very unlikely), most operations are O(n).

Answer 2

It is not the way we calculate the second hash function, since for every probe(unavailability of slot) you need to have a new hash function and it is not feasible.

Generic Second Hash function would be of type,

H1(x) - first hash function, H2(x) - second hash function

First time we try for following slot - H1(x),

next probe would be - H1(x)+H2(x),

next probe H1(x)+2*H2(x) ........ H1(x)+n*H2(x)

Answer 3

The second hash function does not calculate the new index on its own, rather, we use a combination of both the functions using a collision number -- i. Say you have H1(k) and H2(k) then the combination would be

H = (H1(k) + i*H2(k))%n

And we keep incrementing i.