Сложность выполнения хеш-таблицы (вставка, поиск и удаление)

Question

Почему я продолжаю видеть различные сложности времени выполнения для этих функций в хэш-таблице?

В вики поиск и удаление - это O (n) (я думал, что целью хеш-таблиц является постоянный поиск, поэтому какой смысл искать, если O (n)).

В некоторых заметках курса, сделанных некоторое время назад, я вижу широкий спектр сложностей, зависящих от определенных деталей, включая одну со всеми O (1).Зачем использовать любую другую реализацию, если я могу получить все O (1)?

Если я использую стандартные хеш-таблицы на языке, таком как C ++ или Java, как я могу ожидать сложности времени?

Answer 1

Хеш-таблицы имеют среднюю O(1) и амортизированную сложность случая, однако она страдает от O(n) наихудшего случая сложности времени,[И я думаю, что именно здесь ваша путаница]

Хеш-таблицы страдают от O(n) наихудшей сложности по времени по двум причинам:

1. Если слишком много элементов было хешировано в один и тот жеключ: поиск в этом ключе может занять O(n) раз.
2. Как только хеш-таблица прошла свой баланс нагрузки - она ​​должна перефразировать [создать новую таблицу большего размера и заново вставитькаждый элемент таблицы].

Тем не менее, говорят, что это O(1) средний и амортизированный регистр, потому что:

1. Очень редко многие элементы хэшируются на один и тот же ключ [есливы выбрали хорошую хэш-функцию, и у вас не слишком большой баланс нагрузки.
2. Операция перефразирования, равная O(n), в лучшем случае может произойти после n/2 операций, которые все предполагаются O(1)Таким образом, при суммировании среднего времени на операцию вы получаете: (n*O(1) + O(n)) / n) = O(1)

Примечание из-за проблемы с перефразировкой - приложения и приложения реального времени, которым требуется низкая задержка - должныне использовать хеш-таблицу в качестве структуры данных.

РЕДАКТИРОВАТЬ: Еще одна проблема с хеш-таблицами: кэш
Еще одна проблема, которая может привести к снижению производительности вБольшие хеш-таблицы обусловлены производительностью кеша. Хеш-таблицы страдают от плохой производительности кеша , и, следовательно, для большой коллекции - время доступа может занять больше времени, так как вам необходимо перезагрузить соответствующую часть таблицы из памяти обратно в кеш.

Answer 2

В идеале, хеш-таблица O(1).Проблема в том, что если два ключа не равны, но они приводят к одному и тому же хешу.

Например, представьте строки "это были лучшие времена, это были худшие времена" и «Зеленые яйца и ветчина» оба привели к значению хеша 123.

Когда вставлена ​​первая строка, она помещается в сегмент 123. Когда вставляется вторая строка,было бы видеть, что значение уже существует для сегмента 123.Затем он сравнил бы новое значение с существующим значением и увидел бы, что они не равны.В этом случае для этого ключа создается массив или связанный список.На этом этапе извлечение этого значения становится O(n), поскольку хеш-таблица должна перебирать каждое значение в этом сегменте, чтобы найти желаемое.

По этой причине при использовании хеш-таблицы важно использоватьключ с действительно хорошей хэш-функцией, которая работает быстро и не всегда приводит к дублированию значений для различных объектов.

Имеет смысл?

Answer 3

Некоторые хеш-таблицы ( хеширование кукушки ) имеют гарантированный O (1) поиск

Answer 4

Возможно, вы смотрели на космическую сложность? Это O (n). Остальные сложности, как и ожидалось, в записи хеш-таблицы . Сложность поиска приближается к O (1) с увеличением количества сегментов. Если в худшем случае у вас есть только одна корзина в хеш-таблице, то сложность поиска составляет O (n).

Редактировать в ответ на комментарий Не думаю, что правильно говорить, что O (1) - это средний случай. Это действительно (как говорит страница википедии) O (1 + n / k), где K - размер хеш-таблицы. Если K достаточно велико, то результатом будет O (1). Но предположим, что K равно 10, а N равно 100. В этом случае в каждом сегменте будет в среднем 10 записей, поэтому время поиска определенно не равно O (1); это линейный поиск до 10 записей.

Answer 5

Зависит от того, как вы реализуете хэширование, в худшем случае оно может перейти к O (n), в лучшем случае, это 0 (1) (как правило, вы можете достичь, если ваш DS не такой большой, легко)