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

Question

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

Я не понимаю, почему сложность перефразирования hastable может быть квадратичной в худшем случае:

http://www.cplusplus.com/reference/unordered_set/unordered_multiset/reserve/

Любая помощь будет оценена!

Спасибо

5

hash stl hashset unordered-set

Источник

user2420472 10 авг '13 в 18:01

1 ответ

Решение

Другие вопросы по тегам hash stl hashset unordered-set

user1711796 10 авг '13 в 18:55 2013-08-10 18:55 · Accepted Answer · 2013-08-10 18:55

Просто некоторые основы:

Хеш-коллизии - это когда два или более элемента принимают один и тот же хеш. Это может вызвать наихудший случай O(n) операции.
Я не буду вдаваться в подробности, так как можно найти много объяснений этому. В основном все элементы могут иметь одинаковый хеш, поэтому у вас будет один большой связанный список с этим хешем, содержащий все ваши элементы (и, конечно, поиск по связанному списку O(n)).
Это не обязательно должен быть связанный список, но большинство реализаций делают это таким образом.
Перефразировка создает новую хеш-таблицу с требуемым размером и в основном выполняет вставку для каждого элемента в старой таблице (возможно, есть немного лучший способ, но я уверен, что большинство реализаций не справляются с асимптотической сложностью наихудшего случая простые вставки).

В дополнение к вышесказанному, все сводится к этому утверждению: ( отсюда¹)

Элементы с эквивалентными значениями группируются в одном сегменте и таким образом, что итератор (см. Equal_range) может выполнять итерации по всем из них.

Таким образом, все элементы с эквивалентными значениями должны быть сгруппированы вместе. Чтобы это сохранить, при выполнении вставки сначала необходимо проверить, существуют ли другие элементы с таким же значением. Рассмотрим случай, когда все значения принимают один и тот же хеш. В этом случае вам придется просмотреть вышеупомянутый связанный список для этих элементов. Так n вставки, просматривая 0, затем 1, затем 2тогда... потом n-1 элементы, которая является 0+1+2+...+n-1 знак равно n*(n-1)/2 знак равно O(n²),

Не могли бы вы оптимизировать это для O(n)? Для меня имеет смысл, что вы можете это сделать, но даже если это так, это не означает, что все реализации должны делать это таким образом. При использовании хеш-таблиц обычно предполагается, что коллизий не будет слишком много (даже если это предположение наивно), что позволит избежать сложности в наихудшем случае, уменьшив тем самым необходимость в дополнительной сложности, чтобы перефразировать не нужно O(n²),

1: Для всех возможных ненавистников, извините за цитирование CPlusPlus вместо CPPReference (для всех остальных - CPlusPlus, как известно, ошибается), но я не смог найти эту информацию там (так что, конечно, это может быть неправильно, но я надеюсь, что это не так, и это имеет смысл в этом случае).