Сложность выполнения хеш-таблицы (вставка, поиск и удаление)
Почему я продолжаю видеть различные сложности времени выполнения для этих функций в хэш-таблице?
В вики поиск и удаление - это O(n) (я думал, что целью хеш-таблиц является постоянный поиск, поэтому какой смысл искать, если O(n)).
В некоторых заметках курса, сделанных некоторое время назад, я вижу широкий спектр сложностей, зависящих от определенных деталей, включая одну со всеми O(1). Зачем использовать любую другую реализацию, если я могу получить все O(1)?
Если я использую стандартные хеш-таблицы на языке, таком как C++ или Java, чего я могу ожидать от сложности времени?
5 ответов
Хеш-таблицы O(1) средняя и амортизированная сложность случая, однако она страдает от O(n) сложность временинаихудшего случая. [И я думаю, что это то, где твое замешательство]
Хэш-таблицы страдают от O(n) наихудшая временная сложность по двум причинам:
- Если в один и тот же ключ хэшировано слишком много элементов: поиск внутри этого ключа может занять
O(n)время. - Как только хэш-таблица прошла баланс нагрузки - она должна перефразировать [создать новую таблицу большего размера и заново вставить каждый элемент в таблицу].
Тем не менее, как говорят, O(1) средний и амортизированный случай, потому что:
- Очень редко многие элементы будут хэшироваться на одну и ту же клавишу [если вы выбрали хорошую хэш-функцию и у вас не слишком большой баланс нагрузки.
- Операция перефразировки, которая
O(n)может самое большее случиться послеn/2опс, которые все предполагаютсяO(1)Таким образом, когда вы суммируете среднее время за операцию, вы получите:(n*O(1) + O(n)) / n) = O(1)
Обратите внимание, что из-за проблемы перефразирования - приложения реального времени и приложения, которым требуется низкая задержка, - не должны использовать хеш-таблицу в качестве своей структуры данных.
РЕДАКТИРОВАТЬ: Еще одна проблема с хэш-таблицами: кеш
Другая проблема, из-за которой вы можете увидеть потерю производительности в больших хеш-таблицах, связана с производительностью кэша. Хеш-таблицы страдают от плохой производительности кеша и, следовательно, для большой коллекции - время доступа может занять больше времени, так как вам нужно перезагрузить соответствующую часть таблицы из памяти обратно в кеш.
В идеале хеш-таблица O(1), Проблема в том, что два ключа не равны, но они дают одинаковый хэш.
Например, представьте, что строки "это были лучшие времена, когда это были худшие времена", а "Зеленые яйца и ветчина" дали хэш-значение 123,
Когда первая строка вставлена, она помещается в область 123. Когда вторая строка вставлена, она увидит, что значение для группы уже существует 123, Затем он сравнил бы новое значение с существующим значением и увидел бы, что они не равны. В этом случае для этого ключа создается массив или связанный список. На этом этапе получение этого значения становится O(n) поскольку хеш-таблица должна перебирать каждое значение в этом сегменте, чтобы найти желаемое.
По этой причине при использовании хеш-таблицы важно использовать ключ с действительно хорошей хеш-функцией, которая одновременно быстра и не приводит к дублированию значений для разных объектов.
Есть смысл?
Некоторые хеш-таблицы ( хеширование кукушки) имеют гарантированный поиск O(1)
Возможно, вы смотрели на космическую сложность? Это O (n). Другие сложности, как и ожидалось, в записи хеш-таблицы. Сложность поиска приближается к O (1) с увеличением количества сегментов. Если в худшем случае у вас есть только одна корзина в хеш-таблице, то сложность поиска составляет O (n).
Изменить в ответ на комментарий Я не думаю, что это правильно, чтобы сказать O (1) является средним случаем. Это действительно (как говорит страница википедии) O (1 + n / k), где K - размер хеш-таблицы. Если K достаточно велико, то результатом будет O (1). Но предположим, что K равно 10, а N равно 100. В этом случае в каждом сегменте будет в среднем 10 записей, поэтому время поиска определенно не равно O(1); это линейный поиск до 10 записей.
Зависит от того, как вы реализуете хеширование, в худшем случае оно может перейти к O(n), в лучшем случае это 0(1) (обычно вы можете достичь, если ваш DS не так уж велик)