Какая сложность вставки в хеш-таблице?

Какая сложность вставки в хеш-таблице

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

Временная сложность

Best Case: O(1)

Вставка выполняется за константное время, когда:

• Хеш-функция возвращает индекс в таблице, где ячейка пуста
• Нет коллизий (столкновений)

// Идеальная вставка
unsigned int hash = hashFunction(key);
unsigned int index = hash % capacity;
if (table[index] == nullptr) {  // ячейка свободна
    table[index] = new Node(key, value);
}

Average Case: O(1)

При хорошей хеш-функции и достаточном пространстве (коэффициент загрузки α < 0.75):

Sредняя длина цепочки = α = n / m
где n = количество элементов
     m = размер таблицы

Если α ≈ 0.5, то средняя длина цепочки = 0.5, вставка O(1 + 0.5) = O(1)

Worst Case: O(n)

Вставка может стать линейной, если:

• Плохая хеш-функция — все элементы хешируются в один индекс
• Таблица переполнена — коэффициент загрузки слишком высокий (α > 3)
• Много коллизий — цепочка содержит все элементы

// Плохой случай: все элементы в одной цепочке
for (auto item : chain) {  // итерация по всем n элементам
    if (item->key == key) {
        // найти место вставки
    }
}

Методы разрешения коллизий

1. Chaining (Цепочки)

Отдельное связывание — коллизии хранятся в списке:

template<typename K, typename V>
class HashTableChaining {
private:
    struct Node {
        K key;
        V value;
        Node* next;
    };
    
    std::vector<Node*> table;
    size_t size;
    
public:
    void insert(const K& key, const V& value) {
        unsigned int index = hash(key) % table.size();
        
        Node* node = table[index];
        while (node) {
            if (node->key == key) {
                node->value = value;  // update
                return;
            }
            node = node->next;
        }
        
        // Вставка в начало списка: O(1)
        Node* newNode = new Node{key, value, table[index]};
        table[index] = newNode;
        size++;
    }
};

Сложность для chaining:

• Best/Average: O(1)
• Worst: O(n) при плохой хеш-функции
• Память: O(n + m) для n элементов и m ячеек

2. Open Addressing (Открытая адресация)

Линейный поиск — если ячейка занята, ищем следующую:

void insert(const K& key, const V& value) {
    unsigned int index = hash(key) % table.size();
    unsigned int attempts = 0;
    
    while (table[index].occupied && attempts < table.size()) {
        index = (index + 1) % table.size();  // linear probing
        attempts++;
    }
    
    if (attempts < table.size()) {
        table[index] = {key, value, true};
    } else {
        // таблица полна, нужен rehash
        rehash();
    }
}

Варианты:

• Linear probing: index = (h + i) mod m
• Quadratic probing: index = (h + i²) mod m
• Double hashing: index = (h1 + i*h2) mod m

Сложность:

• Best: O(1)
• Average: O(1 / (1 - α)) где α = коэффициент загрузки
• Worst: O(n) если α → 1

Практические рекомендации

Поддержание O(1) в среднем случае:

class DynamicHashTable {
private:
    static constexpr float MAX_LOAD_FACTOR = 0.75;
    
    void maybeRehash() {
        float loadFactor = static_cast<float>(size) / capacity;
        if (loadFactor > MAX_LOAD_FACTOR) {
            rehash(capacity * 2);
        }
    }
    
public:
    void insert(const K& key, const V& value) {
        // вставка
        size++;
        maybeRehash();
    }
};

Хорошая хеш-функция должна:

• Быстро вычисляться — O(1) сама по себе
• Равномерно распределять — минимизировать коллизии
• Независимой от входных данных — не иметь паттернов

// Плохо: возвращает одно и то же для близких ключей
size_t hash(int key) { return key % 10; }

// Хорошо: использует криптографическую функцию
size_t hash(const std::string& key) {
    size_t h = 0;
    for (char c : key) {
        h = h * 31 + static_cast<unsigned char>(c);
    }
    return h;
}

Сравнение со встроенными реализациями

// std::unordered_map в C++ гарантирует O(1) в среднем
std::unordered_map<int, std::string> map;
map[1] = "value";  // O(1) в среднем

// std::map работает с красно-чёрным деревом
std::map<int, std::string> orderedMap;
orderedMap[1] = "value";  // O(log n)

Ключевые выводы

• Амортизированная сложность O(1) достижима при правильной реализации
• Коэффициент загрузки критичен — поддерживай α < 0.75
• Хеш-функция может испортить всё — выбирай проверенные алгоритмы
• Rehashing необходим при переполнении, но амортизируется на O(1) за операцию
• Worst case O(n) возможен, но на практике крайне редок при хорошей реализации