Структуры данных в C/C++

Хеш-таблица (hash table) в C и C++

В этом уроке вы посчитаете, сколько раз встречается каждое слово, с помощью написанной вручную хеш-таблицы на C и std::unordered_map в C++.

Введение

Хеш-таблица (hash table) с помощью хеш-функции (hash function) превращает каждый ключ в индекс ячейки хранения (bucket), поэтому поиск, вставка и удаление выполняются очень быстро. Когда два разных ключа попадают в одну ячейку, возникает коллизия, и таблица должна разрешать её цепочками (chaining) или открытой адресацией (open addressing).

Главное

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

Как это работает

Введите ключ и сохраните или найдите его. Хеш превращает ключ в номер корзины, поэтому программа сразу переходит к нужной корзине.

Примеры кода на C и C++

Запустить →

main.c

#include <stdio.h>
#include <string.h>

typedef struct Item {
    const char *key;
    int count;
    struct Item *next;
} Item;

unsigned hash(const char *text) {
    unsigned value = 5381;
    while (*text) {
        value = value * 33u ^ (unsigned char)*text++;
    }
    return value % 5;
}

int main(void) {
    const char *words[] = {"c", "cpp", "c"};
    Item items[2] = {{"c", 0, NULL}, {"cpp", 0, NULL}};
    Item *buckets[5] = {0};

    for (int index = 0; index < 2; ++index) {
        unsigned bucket = hash(items[index].key);
        items[index].next = buckets[bucket];
        buckets[bucket] = &items[index];
    }
    for (int index = 0; index < 3; ++index) {
        Item *item = buckets[hash(words[index])];
        for (; item; item = item->next) {
            if (strcmp(item->key, words[index]) == 0) {
                ++item->count;
                break;
            }
        }
    }
    printf("c=%d cpp=%d\n", items[0].count, items[1].count);
}

Результат выполнения

c=2 cpp=1

C++

Запустить →

main.cpp

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> counts;
    for (const std::string word : {"c", "cpp", "c"}) {
        ++counts[word];
    }
    std::cout << "c=" << counts["c"]
              << " cpp=" << counts["cpp"] << '\n';
}

Результат выполнения

c=2 cpp=1

Сравнение C и C++

Функция hash на C вычисляет значение по символам строки, а затем берёт остаток от деления на 5, чтобы выбрать один из 5 бакетов. Каждый бакет - связный список, поэтому слова с коллизией выстраиваются в цепочку в одном бакете. В примере на C используется лишь несколько фиксированных слов, чтобы сосредоточиться на механизме бакетов. В C++ std::unordered_map сам управляет узлами, растёт при необходимости и принимает в качестве ключа любую строку.

Данные (struct) и операции разделены, а память выделяется и освобождается вручную.

C++

Классы и контейнеры защищают целостность данных и сами управляют своими ресурсами.

Упражнения для практики

Запустите обе версии, а затем измените код, чтобы увидеть разницу в безопасности, которую даёт каждый язык.

Добавьте тесты для пустого состояния и момента, когда достигнута максимальная ёмкость.
Напишите освобождение памяти и убедитесь, что утечек нет.
Сравните сложность с аналогичным контейнером стандартной библиотеки.

Попрактикуйтесь на задаче

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

Все задачи