🤔 В unordered_set поиск - константа?

std::unordered_set — это контейнер, который использует хеш-таблицу для хранения элементов. Это позволяет выполнять операции вставки, удаления и поиска с амортизированной константной временной сложностью \(O(1)\). Однако, важно понимать, что эта сложность — средняя, а не гарантированная в каждом конкретном случае.

🚩Принцип работы

Основан на механизме хеширования. Каждому элементу сопоставляется хеш-код, который определяет, в каком "ведре" (bucket) хеш-таблицы будет храниться элемент. Если хеш-функция хорошо распределяет значения, то доступ к элементу, его вставка или удаление могут выполняться за время \(O(1)\).

🚩Возможные сценарии сложности

🟠Лучший случай
Если хеш-функция равномерно распределяет элементы по всем "ведрам", то каждая операция (поиск, вставка, удаление) будет выполняться за амортизированное время \(O(1)\).
🟠Худший случай
В случае, когда многие или все элементы попадают в одно "ведро" (например, из-за плохой хеш-функции), операции с контейнером могут деградировать до \(O(n)\), где \(n\) — количество элементов в контейнере. В этом случае поведение контейнера будет похоже на список или массив, где каждый поиск требует линейного прохода по всем элементам.

🚩Реальные характеристики

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

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet;

    // Добавление элементов
    mySet.insert(1);
    mySet.insert(2);
    mySet.insert(3);

    // Поиск элемента
    if (mySet.find(2) != mySet.end()) {
        std::cout << "Element found" << std::endl;
    } else {
        std::cout << "Element not found" << std::endl;
    }

    return 0;
}

Ставь 👍 и забирай 📚 Базу знаний