Что происходит при добавлении элементов в хэш-таблицу?

Что происходит при добавлении элементов в хэш-таблицу?

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

Процесс добавления элемента

1. Хеширование ключа: Ключ преобразуется в хеш-код с помощью хеш-функции.

2. Вычисление индекса: Hash code преобразуется в индекс таблицы: index = hash(key) % table_size

3. Поиск позиции: Проверяется, занята ли ячейка в таблице.

4. Обработка коллизий: Если ячейка занята — применяется метод разрешения коллизий (цепочки, открытая адресация).

5. Добавление элемента: Элемент добавляется в таблицу.

6. Увеличение счётчика: Размер таблицы увеличивается на 1.

7. Проверка коэффициента загрузки: Если load_factor > max_load_factor, происходит rehashing.

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

Chaining (Цепочки):

// Каждая ячейка содержит список элементов
[Bucket 0] -> (key1, val1) -> (key2, val2) -> NULL
[Bucket 1] -> (key3, val3) -> NULL
[Bucket 2] -> NULL

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

// При коллизии ищется следующая свободная ячейка
Linear Probing: index = (hash(key) + i) % table_size
Quadratic Probing: index = (hash(key) + i^2) % table_size
Double Hashing: index = (hash1(key) + i * hash2(key)) % table_size

std::unordered_map в C++

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> map;
    
    map["apple"] = 5;
    map.insert({"banana", 3});
    
    std::cout << "Bucket count: " << map.bucket_count() << std::endl;
    std::cout << "Load factor: " << map.load_factor() << std::endl;
    std::cout << "Max load factor: " << map.max_load_factor() << std::endl;
    
    return 0;
}

Rehashing (Переразмещение)

Когда load_factor превышает max_load_factor:

void rehash() {
    int new_size = find_next_prime(current_size * 2);
    HashTable* new_table = new HashTable(new_size);
    
    for (int i = 0; i < current_size; i++) {
        for (auto& entry : buckets[i]) {
            int new_hash = hash(entry.key) % new_size;
            new_table->buckets[new_hash].push_back(entry);
        }
    }
    
    delete[] buckets;
    buckets = new_table->buckets;
    current_size = new_size;
}

Сложность операций

Практический пример

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> map;
    
    std::cout << "Initial: Buckets " << map.bucket_count() << std::endl;
    
    for (int i = 0; i < 100; i++) {
        map[i] = "Value " + std::to_string(i);
        
        if (i % 10 == 0) {
            std::cout << "After " << i << " elements: " 
                      << map.bucket_count() << " buckets" << std::endl;
        }
    }
    
    return 0;
}

Оптимизация при добавлении

std::unordered_map<int, int> map;
map.reserve(1000);  // Резервируем место

for (int i = 0; i < 1000; i++) {
    map[i] = i * 2;
}

map.max_load_factor(0.5);  // Rehash при load_factor > 0.5

Особенности реализаций

Chaining:

• Плюсы: простота, ленивое удаление
• Минусы: больше памяти

Open Addressing:

• Плюсы: компактнее, лучше кэширование
• Минусы: сложнее удаление

Рекомендации

• Используйте reserve() для известного размера
• Выбирайте хорошую хеш-функцию
• Контролируйте max_load_factor()
• Анализируйте распределение хешей