К настоящему времени многие из вас, должно быть, слышали о HashDoS. Исследователи, которые нашли это, заявляют в their video, что наихудшая сложность Hastable - O(n^2). Как это может быть?HashDoS: как может худший случай сложности Hashtable быть O (n^2)?
Вопрос сформулирован неверным образом. Исследователи не утверждают, что «наихудшая сложность Hashtables - O (n^2)».
What they claim заключается в том, что «[...] сложность вставки n элементов в таблицу [...] переходит к O (n^2)». Таким образом, сложность одной операции O (n). Что имеет смысл: если все ключи имеют один и тот же хеш, то все они входят в одно и то же ведро, которое является просто массивом или связанным списком, поэтому его нужно искать линейно.
Таким образом, это утверждение просто подчеркивает важность использования хорошей хэш-функции. Хорошая хеш-функция имеет больше шансов достичь амортизированного времени O (1), чем более слабая хеш-функция; для первого, только для очень немногих входов хэш-таблица достигает наихудшего случая O (n). –
@PeterO. На самом деле это не поможет. Злоумышленник заранее знает, какие данные отправлять для генерации коллизий - так как они имеют доступ к указанным хэш-функциям/библиотекам - и отправляет данные, которые создают такие коллизии (в этом случае в качестве ключей для параметров POST). Рандомизированная хэш-реализация не позволяет злоумышленнику предварительно вычислить этот список сталкивающихся ключей, а ограничение количества разрешенных ключей уменьшает крайний «n^2». –
@MikeNakis: В этом случае проблема заключается в том, что никакая хэш-функция не может решить: хеш-коллизии неизбежны для любого хэш-кода конечной длины. –
Возможный дубликат [Временная сложность таблицы хэшей] (http://stackoverflow.com/questions/3949217/time-complexity-of-hash-table) –
Я не думаю, что это дубликат. Вопрос о O (n^2), который не рассматривался в предыдущем вопросе. –
Это не дубликат, это просто случай, когда кто-то не читает/не понимает материал, о котором они спрашивают. Майк правилен ниже - это O (n) для вставки любого элемента и O (n^2) для вставки * набора из n элементов * (если вы создаете коллизии). Это именно то, что они заявляют и имеют на своих слайдах. –