Как определишь, куда поставить новый элемент хэш-таблицы?

Размещение элементов в хэш-таблице

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

1. Вычисление хэш-функции

Первый шаг — применить хэш-функцию к ключу элемента.

size_t hash_value = hash_function(key);

Хэш-функция должна быть:

• Детерминированной: одинаковый ключ всегда даёт одинаковый хэш
• Быстрой: вычисляется за O(1) (или O(k) где k — длина ключа)
• Хорошо распределённой: минимум коллизий
• Равномерной: значения распределены равномерно по всему диапазону

// Примеры хэш-функций

// Для целых чисел
size_t hash_int(int key) {
    return key ^ (key >> 16);  // XOR с битовым сдвигом
}

// Для строк (DJB2 алгоритм)
size_t hash_string(const std::string& key) {
    size_t hash = 5381;
    for (char c : key) {
        hash = ((hash << 5) + hash) + c;  // hash*33 + c
    }
    return hash;
}

// Для указателей (просто кастуем)
size_t hash_pointer(const void* ptr) {
    return reinterpret_cast<size_t>(ptr) >> 3;  // Сдвиг на выравнивание
}

C++17+ предоставляет std::hash<T> для встроенных типов:

std::hash<std::string> hasher;
size_t hash_value = hasher("key");

2. Нормализация индекса (модульное приведение)

Полученный хэш обычно огромный (size_t может быть 64-битным). Нужно привести его к диапазону таблицы:

size_t table_size = 100;  // Размер таблицы
size_t index = hash_value % table_size;  // Получаем индекс 0..99

Важно: размер таблицы должен быть:

• Простым числом (если используем модульное приведение) — для лучшего распределения
• Степенью двойки (если используем битовую маску) — для производительности

// Рекомендуемые размеры таблиц:
std::vector<int> table_sizes = {
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29,  // Простые числа
    53, 97, 193, 389, 769, 1543, 3079,
    6151, 12289, 24593, 49157, 98317
};

// Или степени двойки:
// 16, 32, 64, 128, 256, 512, 1024, 2048, 4096

3. Обработка коллизий

Если индекс уже занят — применяем стратегию разрешения коллизий.

Chaining (Раздельные цепочки)

template<typename K, typename V>
struct Entry {
    K key;
    V value;
    Entry* next;  // Указатель на следующий элемент в цепочке
};

void insert_chaining(const K& key, const V& value) {
    size_t index = hash_function(key) % table_size;
    
    // Если позиция пустая, создаём новую цепочку
    if (table[index] == nullptr) {
        table[index] = new Entry{key, value, nullptr};
    } else {
        // Проходим по цепочке, ищем перезапись или конец
        Entry* current = table[index];
        while (current != nullptr) {
            if (current->key == key) {
                current->value = value;  // Обновление
                return;
            }
            if (current->next == nullptr) {
                // Добавляем в конец цепочки
                current->next = new Entry{key, value, nullptr};
                return;
            }
            current = current->next;
        }
    }
}

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

Linear Probing — линейный поиск следующей свободной позиции

void insert_linear_probing(const K& key, const V& value) {
    size_t index = hash_function(key) % table_size;
    size_t original_index = index;
    
    // Ищем свободную позицию
    while (table[index].is_occupied) {
        if (table[index].key == key) {
            table[index].value = value;  // Обновление
            return;
        }
        index = (index + 1) % table_size;  // Следующая позиция
        
        // Проверка на переполнение
        if (index == original_index) {
            throw std::overflow_error("Hash table full");
        }
    }
    
    // Вставляем в найденную свободную позицию
    table[index] = {key, value, true};
}

Quadratic Probing — квадратичные интервалы (1, 4, 9, 16...)

void insert_quadratic_probing(const K& key, const V& value) {
    size_t original_index = hash_function(key) % table_size;
    size_t index = original_index;
    
    for (size_t i = 1; i < table_size; i++) {
        index = (original_index + i * i) % table_size;
        
        if (!table[index].is_occupied) {
            table[index] = {key, value, true};
            return;
        }
        if (table[index].key == key) {
            table[index].value = value;
            return;
        }
    }
    
    throw std::overflow_error("Hash table full");
}

Double Hashing — вторая функция определяет шаг

size_t hash_function2(const K& key) const {
    return 7 - (std::hash<K>{}(key) % 7);  // Вторая хэш-функция
}

void insert_double_hashing(const K& key, const V& value) {
    size_t index = hash_function(key) % table_size;
    size_t step = hash_function2(key);
    size_t original_index = index;
    
    for (size_t i = 0; i < table_size; i++) {
        if (!table[index].is_occupied) {
            table[index] = {key, value, true};
            return;
        }
        if (table[index].key == key) {
            table[index].value = value;
            return;
        }
        
        index = (index + step) % table_size;
    }
    
    throw std::overflow_error("Hash table full");
}

4. Перехэширование (Rehashing)

Когда коэффициент заполнения α = n/m (элементы/размер) превышает порог (обычно 0.75), таблица расширяется и все элементы перемещаются.

void rehash() {
    size_t old_size = table_size;
    std::vector<Entry> old_table = table;
    
    // Увеличиваем размер (обычно в 2 раза, но в простое число)
    table_size = next_prime(old_size * 2);
    table.clear();
    table.resize(table_size);
    
    // Переиндексируем все элементы
    for (const auto& entry : old_table) {
        if (entry.is_occupied) {
            insert(entry.key, entry.value);  // Новая позиция
        }
    }
}

size_t next_prime(size_t n) {
    while (!is_prime(n)) n++;
    return n;
}

bool is_prime(size_t n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (size_t i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

5. Полная реализация вставки

template<typename K, typename V>
class HashTable {
private:
    std::vector<Entry<K, V>> table;
    size_t size = 0;
    size_t capacity = 16;
    static constexpr double LOAD_FACTOR_THRESHOLD = 0.75;
    
public:
    void insert(const K& key, const V& value) {
        // Проверяем нужно ли перехэширование
        if ((size + 1.0) / capacity > LOAD_FACTOR_THRESHOLD) {
            rehash();
        }
        
        size_t index = hash_function(key) % capacity;
        
        // Ищем позицию (с обработкой коллизий)
        while (table[index].is_occupied && table[index].key != key) {
            index = (index + 1) % capacity;  // Linear probing
        }
        
        if (!table[index].is_occupied) {
            size++;
        }
        
        table[index] = {key, value, true};
    }
    
private:
    void rehash() {
        std::vector<Entry<K, V>> old_table = table;
        capacity = next_prime(capacity * 2);
        table.assign(capacity, Entry<K, V>{});
        size = 0;
        
        for (const auto& entry : old_table) {
            if (entry.is_occupied) {
                insert(entry.key, entry.value);
            }
        }
    }
};

Итог: Алгоритм размещения элемента

1. Вычислить хэш: hash_value = hash_function(key)
2. Привести к диапазону: index = hash_value % table_size
3. Проверить позицию:
   • Если свободна → вставить
   • Если занята → применить стратегию коллизии (chaining или open addressing)
4. Проверить load factor: если α > 0.75 → перехэшировать
5. Обновить счётчик размера: size++

С++17 std::unordered_map использует chaining и автоматически управляет rehashing. Выбор между chaining и open addressing зависит от профиля использования: chaining проще и быстрее для удаления, open addressing экономит память.