Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list

Question

Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list. Assume that one slot can store a flag and either one element plus a pointer or two pointers. All dictionary and free-list operations should run in O(1) expected time. Does the free list need to be doubly linked, or does a singly linked free list suffice?

Please tell me if my understanding is correct: each slot in T[0,1,2….m-1] is storing (1) a flag (2) an element (3) 2 pointers

So, instead of the slot T(h(k)) being a pointer to a list, it is able to save one element and then that element points to a list

There is also a “free list”

There is only one flag for each slot T[0,1,2….m-1]

To insert an element ‘x’ we will first check T[h(x.key)] to see if it is free. If it is free then we insert T[h(x.key)] and change the flag = 1
If it was not free, then there is a list, so we insert it at the beginning of the list
To delete we will check x.prev and x.next to see if they are NULL. So when we delete the element ‘x’ we will be left with an empty list at that slot. So we insert T[h(x.key)] into the free list and update the flag to 0 and then delete the element x from the list its stores in

What I don’t understand is the functionality of maintaining a free list?
Is there a single free list for the whole hash table or does each slot have its own free list?
Also why insert the element to be deleted into the free list and then delete it? Why don’t just delete it without using the intermediate free list?

I am unable to visualize the use of the free list as mentioned in the question.

Answer 1

Practical implementations that I have seen worked like this:

1. In a hash table, a slot is either used (contains a hash value and a value), has been never used, or has been used and emptied, and we need to distinguish this. With no additional space if at all possible.

2. If the values are pointers, and neither “all bits zero” nor “all bits one” are valid pointers, then we store “all bits zero” or “all bits one” as data to mark a “never used” or “not used anymore” slot.

3. If (2) doesn’t work: There are many more possible hash values than slots. Therefore most hash values never happen. We pick two random hash values which we store as the hash value to represent “empty” and “not used anymore” slots. As long as these are not used, fine. If they are used, we pick two different random hash values and modify the table accordingly (number of slots used should be less than the square root of possible hash values).

I’ve never seen a “free list” being used, because the hash value determines where an entry needs to be stored. Everyone just uses an array.