Hash table deletion complexity

0
votes

What is the complexity of deletion in a hash table? It can vary based on how it is implemented. If it is implemented as a contiguous array, then do we compact the array on deletion (which makes it not O(1))?

If it is doubly linked list based, O(1) deletion is possible but how do we map the hash key to the linked list node in this case? If it is tree based, then it is understandably O(logN).

But deletion in C++ unordered_map and older implementation of HashMap in Java claims to be O(1). Can someone fill in the implementation gaps here?

Edit: Let's assume for simplicity sake, that there are no collisions.

2
javac++algorithmdata-structurestime-complexity
Where does Java's HashMap claim to have O(1) deletion time? - shmosel
It should be clear to you that deletion (as well as insertion) are O(1) operations, assuming there are no collisions. With regard to rearranging the underlying structure, even if that happens it might not occur after each operation. - Tim Biegeleisen
stackoverflow.com/questions/4577998/… - shmosel
shmosel: Edited the question. I am trying to understand the implementation for achieving O(1) when there are no collisions. - sarora
How can a hash table implementation not using array as underlying structure ? - DU Jiaen

2 Answers

0
votes

Removal of a {Key, Value} is not guaranteed to be constant time performance(i.e not O(1)).

In the documentation it is claimed that "provides constant-time performance for the basic operations, assuming the hash function disperses the elements properly among the buckets".

In case of collisions , constant time performance is not gaurenteed

0
votes

Why would you compact?

Your hash table starts as M empty buckets. If you ask what's in bucket 0, it tells you "nothing". You insert some stuff, and wind up with say N full buckets, and M-N empty buckets.

Object O happens to hash to bucket 12. To insert it, you place it in bucket 12. If you delete O, you simply replace bucket 12 with an empty value, the same as you started with. If you ask what's in bucket 12, it tells you "nothing".

You typically want to keep the array larger (by, say, a factor of 2) than the number of items inserted. I don't think I've seen many implementations in general that reclaim space at all - they typically only grow to use more, unless explicitly resized.

You can also have a combination (LinkedHashMap?) where you effectively have a doubly linked list for faster traversal of elements, but also pay the overhead of a hash map as above, in which case the bucket will contain a pointer to the linked list node.