Хеш-таблицы

Тема: Hash Tables (Ассоциативные массивы)

Идея

Идея ассоциативных массивов — привязка элементов массива к любому ключу, не обязательно именно индексу. Например — хранение элементов по строковому ключу. Это достижимо путем трансформации ключа в число (функия hash), после чего использование данного числа как индекс в массиве (после операции модуль / остаток от деления).

Поскольку (в случае использования неидеальной функции hash, что истино в большинстве случаев), несколько разных ключей могут преобразоваться в тот же индекс, необходимо реализовать один из подходов борьбы с этой проблемой. Популярные подходы — связные списки для ячеек с проверкой ключа, использование самого массива как ячейки для списка. Называется эта проблема коллизия.

Например, если функция hash — порядок первой буквы ключа в алфавите — ключи “abc” и “abd” дадут 0 как результат функции hash, после модуля выйдет тоже 0, и попадут элементы по индексу 0 в массиве.

Подход со связным списком

Этот подход применяется чаще всего на практике. Каждая ячейка будет началом динамически выделенного в памяти списка, где каждый нод содержит ключ (для проверки при коллизии), и само значение, хранимое в массиве.

Идея проиллюстрирована в следующем куске кода:

struct BucketNode
{
    T value;
    std::string_view key;
    BucketNode* next;
};

using HashFunc = size_t(*)(std::string_view key);

struct HashTable
{
    std::span<BucketNode*> buckets;
    HashFunc hashFunc;
};

size_t computeIndex(HashTable* table, std::string_view key)
{
    size_t hash = table->hashFunc(key);
    size_t index = hash % table->buckets.size();
    return index;
}

T* find(HashTable* table, std::string_view key)
{
    size_t index = computeIndex(table, key);
    BucketNode* currentNode = table->buckets[index];
    while (currentNode != nullptr)
    {
        if (currentNode->key == key)
        {
            return &currentNode->value;
        }
        currentNode = currentNode->next;
    }
    return nullptr;
}

Полноценно выполните в коде этот подход:

• Функция add, которая выделяет новый нод для элемента с заданным ключем. Должна возвращать адрес value из нового нода, чтобы можно было туда перекопировать значение;
• Функция createHashTable, которая создает ассициативные массив с заданным capacity (количество bucket-ов) и возвращает созданный ассоциативный массив;
• Функция remove, которая удаляет значение по ключу (то есть, стирает нод из его bucket-а);
• Функция удаления free, которая стирает из динамической памяти сами ноды, и динамически выделенный массив (если таковой используется);
• Продемонстрируйте использование.

Можете сделать размер массива bucket-ов фиксированным (с заданным при создании параметром capacity, или используя std::array с максимальным размером).

Встроенный список

Другой подход — вписывание значения при коллизии не в связный список в ее ячейке, а выбор следующей доступной ячейки. Этот подход проще предыдущего, но ограничивает максимальное количество элементов в списке количеством ячеек, и в среднем удлиняет поиск нужной ячейки.

struct Bucket
{
    bool occupied;
    std::string_view key;
    T value;
};

struct HashTable
{
    std::span<Bucket> buckets;
    HashFunc hashFunc;
};

T* find(HashTable* table, std::string_view key)
{
    size_t index = computeIndex(table, key);
    const size_t startIndex = index;
    while (true)
    {
        Bucket* bucket = &table->buckets[index];
        if (bucket->occupied == false)
        {
            return nullptr;
        }
        if (bucket->key == key)
        {
            return &bucket->value;
        }

        index++;
        // Wrap around the edge.
        index = index % table->buckets.size();

        // Traversed the whole array, didn't find the bucket.
        if (index == startIndex)
        {
            return nullptr;
        }
    }
}

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

Выполните тот же интерфейс что дан в предыдущем пункте. Корректный remove сделать гораздо сложнее, поэтому можете пропустить его.

Анализ

Объясните от чего зависит сложность алгоритма добавления и поиска в ассоциативном массиве.

Объясните почему, для идеальной функции hash, поиск стабильно выполняется за фиксированное количество операций.

Объясните как сильно ухудшается скорость поиска, если использовать худшую функцию hash (которая всегда возвращает 0).

Объясните как количество ячеек влияет на сложность.

Дополнительно — resizing (Продвинутый уровень, дополнительно)

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