How do I determine when a Hashtable with double hashing is full?

Question

I am implementing a Hashtable that uses double hashing. However, I have a problem with my insert(element) method. It basically does the following right now:

1. Check if the calculated position in the array is empty. If so, insert the element and we are finished
2. If the position is blocked by another element, we calculate the new hashvalue and start over at 1. (recursion).

The problem is that this algorithm never detects when the hashtable is full. I could keep track of the number of visited positions and compare that number with the size of the array to fix this problem.

However, is there a neater way to do this. Like, is it possible to deduce from the depth of my double hashing that the array has to be full (mathematically)?

Answer 1

I imagine that you should already be keeping track of the number of elements in the table for use with any size() function, so you could compare the number of elements to the number of buckets to ascertain table fullness. If you are not keeping track of the size, then you should simply start doing so by incrementing and decrementing a counter on your insert and remove operations.

Keeping track of the size is something almost all hash table implementations do in order to avoid O(n) cost for size() calls.

The above is assuming that you are not allowing multiple elements per bucket as per standard hash tables (which seems to be the case per your description).