Сложность вставки строк в set и плохой hash
За сколько вставить n различных строк длины k в Python set? Что изменится, если hash для всех объектов возвращает одно и то же значение?
Ответить самому
Сначала сформулируйте ответ как на собеседовании, затем откройте разбор и оцените себя.
Короткий ответ
Обычно получается O(n * k): hash строки считается по символам, а вставка в hash table амортизированно O(1). При константном hash серия вставок деградирует к квадратичной.
Полный разбор
Для обычных строк Python должен вычислить hash по символам, поэтому первая вставка строки длины k включает O(k) на хеширование. Сама операция set.add в среднем амортизированно O(1), если hash хорошо распределяет элементы.
Если сделать hash константным, все элементы попадают в один кластер коллизий. Тогда при вставке нового элемента нужно проверять уже лежащие элементы с тем же hash, и суммарно по n вставкам получается квадратичная деградация. Для строк и пользовательских объектов при коллизиях также важна стоимость equality-сравнений.