HashDoS: how can worst case complexity of Hashtabl

问题:

By now many of you must have heard about HashDoS. The researchers who found this, claim in their video that the worst case complexity of Hastable is O(n^2). How can this be?

回答1:

The question is worded in an incorrect way. The researchers do not claim that "the worst case complexity of Hashtables is O(n^2)".

What they claim is that "The [...] complexity of inserting n elements into the table [...] goes to O(n^2)." So, the complexity of a single operation is O(n). Which makes sense: if all keys have the same hash, then they all go into the same bucket, which is just an array or a linked list, so it needs to be searched linearly.