В unordered_set, который основан на хеш-таблице, самый худший случай поиска возникает, когда структура данных деградирует до такой степени, что время поиска становится линейным, то есть \(O(n)\), где \(n\) — количество элементов в контейнере. Это происходит по нескольким причинам:
🟠Плохая хеш-функция
Играет ключевую роль в распределении элементов по "ведрам" (buckets) в
unordered_set. Если хеш-функция плохо разрабатывается и генерирует одинаковые или близкие хеш-коды для большого количества ключей, элементы начинают накапливаться в очень небольшом числе ведер. Это приводит к тому, что большинство операций поиска, вставки и удаления начинают зависеть от числа элементов в самом длинном связном списке, а не от общего количества ведер, что сильно ухудшает производительность.🟠Высокая степень загрузки
Загрузка хеш-таблицы (
load factor) — это отношение количества элементов в хеш-таблице к количеству ведер. Когда load factor становится слишком высоким, вероятность коллизий увеличивается, что также приводит к увеличению длины цепочек в каждом ведре. Хотя unordered_set автоматически увеличивает количество ведер при увеличении количества элементов, в случаях с экстремально высоким load factor поиск может деградировать до линейного.🟠Неблагоприятная последовательность вставок
Вставляются данные, которые неудачно распределяются хеш-функцией, даже если сама функция в целом хороша, это может привести к временной деградации производительности. Например, последовательная вставка элементов с одинаковым хешем приведет к удлинению одной цепочки.
Ставь 👍 и забирай 📚 Базу знаний