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

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

1. Коллизии хэшей — это когда два или более элемента принимают один и тот же хэш. Это может вызвать наихудшие операции O(n).

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

   Это не обязательно связанный список, но в большинстве реализаций это делается именно так.

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

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

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

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

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

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