What is the worst case for hash tables?

Question

Python

Hey!
They write that for hash tables, the worst case for lookups, insertions, and deletions is O(n). What is this worst case? Rebuilding a table index?

Answer 1

Do you have an example? This is when all elements have the same hash - it is impossible to find the desired element only by the hash and you have to search manually. Those. the table roughly speaking becomes an ordinary array.

Answer 2

In collisions (hash matches), the elements are usually added to a linked list. Searching this linked list is O(n).