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

Ответ 1

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

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

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

Однако он считается O(1) средним и амортизированным, потому что:

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

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

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

Ответ 2

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

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

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

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

Имеют смысл?

Ответ 3

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

Ответ 4

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

Ответ 5

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

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