HashDoS: как сложность Hashtable в худшем случае может быть O (n ^ 2)?

Question

К настоящему времени многие из вас уже слышали о HashDoS .Исследователи, обнаружившие это, утверждают в их видео , что сложность Hastable в худшем случае составляет O(n^2).Как это может быть?

Answer 1

Вопрос сформулирован неверно.Исследователи не утверждают, что «сложность Hashtables в наихудшем случае равна O (n ^ 2)».

Они утверждают, что заключается в том, что «сложность [...] вставки nэлементы в таблицу [...] переходят в O (n ^ 2). "Таким образом, сложность одной операции составляет O (n).Что имеет смысл: если все ключи имеют одинаковый хеш, то все они входят в один и тот же сегмент, который является просто массивом или связанным списком, поэтому его необходимо искать линейно.