Timeline for Time complexity of delete and insert operations in a hash table
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 6 at 12:27 | comment | added | gnasher729 | 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. | |
| Jun 5 at 14:10 | answer | added | ratchet freak | timeline score: 2 | |
| Jun 5 at 13:56 | comment | added | Slaycapь | 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. | |
| Jun 5 at 13:45 | comment | added | codeR | 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. | |
| Jun 5 at 13:39 | history | asked | Slaycapь | CC BY-SA 4.0 |