Как вы спроектируете структуру данных для быстрого поиска по ключу с помощью хэш-функции?

Для быстрого поиска по ключу с помощью хэш-функции обычно используется структура данных — хэш-таблица (hash table). Основные элементы проектирования:

1. Массив бакетов (корзин) — основной контейнер для хранения элементов.
2. Хэш-функция — преобразует ключ в индекс массива.
3. Обработка коллизий — когда два ключа дают одинаковый индекс.

Пример обработки коллизий:

• Цепочки (chaining): в каждой корзине хранится связный список элементов с одинаковым индексом.
• Открытая адресация (open addressing): при коллизии ищется следующая свободная ячейка.

Пример на C++ с использованием цепочек:

#include <vector>
#include <list>
#include <string>

class HashTable {
    static const int SIZE = 100;
    std::vector<std::list<std::pair<std::string, int>>> table;

    int hash(const std::string& key) {
        int hashVal = 0;
        for (char c : key) {
            hashVal = (hashVal * 31 + c) % SIZE;
        }
        return hashVal;
    }

public:
    HashTable() : table(SIZE) {}

    void insert(const std::string& key, int value) {
        int idx = hash(key);
        for (auto& kv : table[idx]) {
            if (kv.first == key) {
                kv.second = value; // обновление
                return;
            }
        }
        table[idx].emplace_back(key, value);
    }

    bool find(const std::string& key, int& value) {
        int idx = hash(key);
        for (auto& kv : table[idx]) {
            if (kv.first == key) {
                value = kv.second;
                return true;
            }
        }
        return false;
    }
};

Такой подход обеспечивает среднее время поиска близкое к O(1).