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

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

1. Вычисление первичного индекса:

• Сначала вычисляется хэш-код ключа с помощью хэш-функции.
• Затем этот хэш отображается на диапазон индексов таблицы, обычно с помощью операции взятия остатка от деления (%).

2. Разрешение коллизий (если ячейка занята): Существует несколько основных методов:

• Метод цепочек (Separate Chaining): Каждая ячейка содержит связный список (или другой контейнер). Новый элемент добавляется в список соответствующей ячейки.
• Открытая адресация (Open Addressing): Ищется следующая свободная ячейка внутри самой таблицы по определенному алгоритму.

Пример реализации на C++ с линейным пробированием (открытая адресация):

template<typename K, typename V>
class HashTable {
    struct Entry {
        K key;
        V value;
        bool occupied = false;
        bool deleted = false; // Флаг для ленивого удаления (tombstone)
    };

    std::vector<Entry> table;
    size_t size = 0;
    const float loadFactorThreshold = 0.7;

    size_t hash(const K& key) const {
        return std::hash<K>{}(key);
    }

    size_t probe(size_t index, size_t attempt) const {
        // Линейное пробирование: index = (hash + i) % capacity
        return (index + attempt) % table.capacity();
    }

public:
    bool insert(const K& key, const V& value) {
        // Проверка необходимости рехеширования
        if (static_cast<float>(size) / table.capacity() > loadFactorThreshold) {
            rehash();
        }

        size_t h = hash(key);
        for (size_t i = 0; i < table.capacity(); ++i) {
            size_t idx = probe(h, i);
            if (!table[idx].occupied || table[idx].deleted) {
                // Нашли свободную ячейку или "могилу"
                table[idx] = {key, value, true, false};
                ++size;
                return true;
            }
            if (table[idx].occupied && table[idx].key == key) {
                // Ключ уже существует, обновляем значение
                table[idx].value = value;
                return false;
            }
            // Коллизия: продолжаем пробирование
        }
        // Таблица переполнена (должно быть предотвращено рехешированием)
        return false;
    }
};

Критерии выбора метода:

• Цепочки проще реализовать, стабильнее при высокой нагрузке, но требуют дополнительной памяти на указатели.
• Открытая адресация лучше использует кэш процессора, но требует тщательного контроля коэффициента загрузки и сложнее при удалении элементов (нужны "могилки").
• В стандартной библиотеке C++ (std::unordered_map) обычно используется метод цепочек.