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!