Hash Tables: Open Addressing and Removing Items

Question

I am trying to understand open addressing in hash tables, but there is one question that has not been answered in my literature. This applies to the removal of elements in such a hash table if quadratic sounding is used. Then the deleted item is replaced by the sentinel item. The get () operation then knows that it needs to go further, and the add () method will overwrite the first sentinel point found. But what happens if I want to add an element with a key that is already in the hash table, but behind the sentry in the test path? Instead of overwriting the value of the instance with the same key that is already in the table, the add () method will overwrite the watch. And then we have several elements with the same key in the hash table. I see this as a problem, as it costs memory, and also, since deleting an item from the hash table just removes the first one, so the item can still be found in the table (i.e., it is not deleted).

Thus, it seems that it is necessary to search the entire research path for the key of the element that needs to be inserted before replacing the sentinel element. Am I missing something? How is this problem handled in practice?

Answer 1

But what happens if I want to add an element with a key that is already in the hash table, but behind the sentry in the test path? Instead of overwriting the value of an instance with the same key that is already in the table, the add () method overwrites the sentinel.

add() should check every element after the watch (s) in the research path until it finds an empty element, as you indicated below. If he could not find a new element in the research path and there are sentinel elements on it, he can use the first sentinel slot to store the new element.

There is a hash table implementation at http://www.algolist.net/Data_structures/Hash_table/Open_addressing (HashMap.java). Its put() method does just that. (Collision resolution is linear sensing in the reference fragment, but I do not consider this an important difference from the point of view of the algorithm.)

After many deletion operations, the table may have too many sentinel elements. A solution for this would be to rebuild the hash table from time to time (i.e. rephrase everything) (depending on the number of elements and the number of sentinel elements). This operation will eliminate the elements of the sentinel device.

Another approach is to exclude the checkpoint element (DELETED) from the exploration path when you delete the element. In practice, in this case you have no controls in the table; There are only FREE and OCCUPIED slots. It can be expensive.

So, it seems that you need to look all the way to research for the key element that you need to insert before replacing the sentry element.

Yes it is. You must search until you find an empty item.

How is this problem handled in practice?

I don’t know too much about realistic hash table implementations in real life. I believe many of them are available on the Internet in open source projects. I just checked the Hashtable and HashMap classes in Java. Both use chaining instead of open addressing.

Answer 2

Sorry for the late answer, but Java has an example of an open-address hash table: java.util.IdentityHashMap .

Alternatively, you can use the GNU Trove Project . His maps are all public address hash tables, as described on the page.