Let's take a hash table where the collision problem is solved using a linked list. As we know, in the worst case, due to collisions, searching for an element in the hash table takes O(n). But why does deleting and inserting an element also take O(n)? We use a linked list where these operations are performed in O(1).
3
-
$\begingroup$ Since lookups may take $O(n)$ time, deletions also take the same time. Whereas, insertion time depends on your implementation. It can be $O(1)$ if you always insert it in the head. $\endgroup$– codeRCommented Jun 5 at 13:45
-
$\begingroup$ This does make sense, but then why do the delete and insert operations into the linked list take O(1)? I previously wondered if deleting and inserting in a linked list takes O(n) and found this answer. $\endgroup$– SlaycapьCommented Jun 5 at 13:56
-
$\begingroup$ You never, ever use a hash table with so many collisions that insert/lookup/delete take more than constant time. If you have more than one collision on average you resize the hash table. $\endgroup$– gnasher729Commented Jun 6 at 12:27
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Deleting is obvious, you need to find the element to delete, that's a lookup. but once you have the element you can delete it in O(1).
Part of inserting an element into a hash table tends to include seeing if it already exists and then not inserting. So you are paying the cost of the search as well. Unless you allow duplicate elements where you can simply insert a node at the head once you have looked up the correct linked list.
answered Jun 5 at 14:10