I am currently studying hashtables and whilst the concept of chaining makes perfect sense, as does why searching is O(n) and also inserting (at head) is O(1), I dont understand why deleting an item is also O(1), hopefully someone can help me understand.

I am referring to text such as this:

In the worst-case scenario, all of the keys hash to the same array slot, so Search takes O(n), while Insert and Delete still take O(1).

The reason I don't understand is that if in the example above, all keys hash to the same slot, adding a new item that also hashes to the same slot and is inserted at head is O(1), equally searching for an item is O(n) as it could be the last item in the linked list, to me it seems that deleting an item should also be O(n) as when the value is hashed it leads to the linked list but the list still needs to be searched to find the value to delete?

Any help appreciated!

  • $\begingroup$ Does this answer your question? stackoverflow.com/a/20514554/8065149 $\endgroup$
    – cjnash
    Dec 16 '20 at 18:45
  • $\begingroup$ When discussing hash tables, complexity is always average case. Under perfect hashing, the expected running time is $O(1)$. $\endgroup$ Dec 16 '20 at 18:45
  • $\begingroup$ @YuvalFilmus correct. It is also worth pointing out that search is also O(1) for average cases too. $\endgroup$
    – cjnash
    Dec 16 '20 at 18:48
  • $\begingroup$ Yes that post explains it, "This reasoning breaks down if the hash function does not distribute the keys evenly. This leads to a situation where you get a lot of hash collisions. Indeed, the worst-case behaviour is when all keys have the same hash value, and they all end up on a single hash chain with all N entries. In that case, deletion involves searching a chain with N entries ... and that makes it O(N)." $\endgroup$
    – pac234
    Dec 16 '20 at 20:03
  • 1
    $\begingroup$ I have also found this comment in an exercise in the CLRS book "(Don’t forget that DELETE takes as an argument a pointer to an object to be deleted, not a key.)" which explains why delete is O(1). $\endgroup$
    – pac234
    Dec 16 '20 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.