Хеш-таблица и C++2006.04.2025 09:16

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

Не будем тянуть, перейдем к реализации хеш-мапы с использованием «приколюх» из C++20!

1. Первое, что мне приглянулось — это концепты.

С их помощью мы будем валидировать типы.

Можем проверить, вызвана ли хеш-функция для ключа и поддерживает ли компаратор прозрачное сравнение:

#include 

template 
concept ValidHasher = requires(Hash h, Key k) {
    { h(k) } -> std::convertible_to;
};

template 
concept TransparentEqual = requires(Equal eq, Key k, const char* s) {
    { eq(k, k) } -> std::convertible_to;
    { eq(k, s) } -> std::convertible_to; // Прозрачность
};

В первом случае проверяем хеш-функцию с помощью concept.
Вот очень интересная статья по концептам от Яндекс практикума.

Во втором случае проверяем прозрачность компаратора
Вот статья про компараторы: Подводные камни компараторов в С++,

2. Обновлённый шаблон класса с requires

Для простоты понимания были вырезаны всякие разные сложные буквосочетания из опенсорсной реализации STL, что бы было понятно и читаемо:

template <
    typename Key,
    typename Value,
    typename Hash = std::hash,
    typename KeyEqual = std::equal_to<>,
    typename Allocator = std::allocator>
> requires ValidHasher && 
          TransparentEqual
class hash_map {
    // остальное как и должно быть...
};

Что же нам это дает?

• Если передать невалидный хеш или компаратор — ошибка будет на этапе компиляции.

• Нормальные сообщения об ошибках.

Круто-же да?

едем дальше, 3. if constexpr

Для оптимизации (да, приколюха из C++17, но все таки хочу добавить это)

template 
void insert(K&& key, Value&& value) {
    if constexpr (std::is_trivially_copyable_v) {
        // Быстрая вставка для простых типов (int, double и т.д.)
        buckets.emplace_back(std::forward(key), std::forward(value));
    } else {
        // Медленная, но безопасная для сложных типов
        buckets.emplace_back(std::piecewise_construct,
                           std::forward_as_tuple(std::forward(key)),
                           std::forward_as_tuple(std::forward(value)));
    }
}

Этот простой пример демонстрирует работу с разной логикой для trivially-copyable типов.
Здесь мне нечего добавить, идем дальше!

4. std: remove_cvref_t — «Чистим» типы от мусора

Убираем const,  volatile и ссылки (&,  &&) из типа:

template 
void insert(K&& key) {
    using CleanKey = std::remove_cvref_t; // Удалили const, &, volatile
    static_assert(std::is_same_v, "Должен быть std::string!");
    // ...
}

Тебе принесли const pizza&, но ты не можешь это скушать, распаковываем с помощью std::remove_cvref_tи ты можешь наслаждаться своей pizzaбезо всяких непонятных оберток.

5. Ranges — «Ленивые» диапазоны

Можно ознакомиться в статье про них!
Мы сможем работать с коллекциями (как vector, list) через »ленивые» операции.
Можем вставлять кучу элементов сразу из любого диапазона (даже из файла или бесконечного генератора!)

hash_map map;

// Вставляем элементы из vector (обычный способ)
std::vector> data = {{"a", 1}, {"b", 2}};
map.insert_range(data);

// Или даже из файла (если data — ленивый range)
auto data_from_file = read_file_lines("data.txt") | std::views::transform(parse_line);
map.insert_range(data_from_file);

Ну, а что, зачем нам бесконечные for'ы? Получаем вполне интересную русскую рулетку с сюрпризами в каждом заряде!

6. consteval — «Вычисли это на этапе компиляции!»

Если вкратце, то функция, помеченная как consteval,  обязана выполняться на этапе компиляции.

Возникает вопрос — а зачем мне это в хеш-мапе?

Ответ: если есть хеш-функция, которая всегда возвращает одно и то же для одних и тех же ключей, её можно вычислить заранее.
Вспоминаю всякие коды Хаффмана и сразу понимаю, что вещь то интересная, примечательная.

struct MagicHasher {
    consteval size_t operator()(const std::string& s) const {
        return s.size() * 100; // вычисляется при компиляции
    }
};

hash_map map;
map["hello"] = 42; // Хеш для "hello" вычислен при компиляции

Считай, что у тебя завтра контрольная по интегралам, а ты вместо заучивания табличных или их ручного выведения, просто выписываешь их себе в шпору и довольный идешь на экзамен надеясь не спалиться!)

7. std: span — «Безопасный указатель на массив»

std::span — это »обёртка» над массивом или vector, которая знает его размер и не даёт выйти за границы.
Нам это нужно, что бы безопасно передавать подмассивы данных из коллекций (да, например vector):

void add_from_span(std::span> data) {
    for (const auto& [key, value] : data) {
        insert(key, value);
    }
}

std::vector> big_data(1000);
// Добавим только первые 10 элементов
map.add_from_span(std::span{big_data.data(), 10});

Выглядит сносно, правда?! Главное, что мы можем применить это на практике (и, конечно, не только в нашей хеш-мапе). С такой реализацией не нужно передавать пару указатель + размер с риском вылететь за границы.

Делаем код оптимизированнее и безопаснее с C++20, продолжаем!

8. Корутины — «Ленивая загрузка значений»

Вот познавательная статья про корутины.
Теперь можем «подгружать» данные по мере обращения к ним!

#include 

template 
struct LazyValue {
    struct promise_type { /*...*/ }; // Опустим реализацию
    std::coroutine_handle handle;

    Value operator()() {
        if (!handle.done()) handle.resume();
        return handle.promise().value;
    }
};

hash_map> lazy_map;
lazy_map["some_data"] = load_data_from_internet(); 
// Загрузится только при вызове lazy_map["some_data"]()

Представь, что заказал проект на C++, а его начнут делать только когда ты им позвонишь перед дедлайном. круто-же, нет?

9. [[no_unique_address]] — «Сжимаем пустые объекты»

Если есть пустые объекты (например, аллокатор без состояния), компилятор может их оптимизировать.
Так мы уменьшаем размер класса, если Hash или KeyEqual — пустые.

template 
class hash_map {
    Hash hash_fn;
    KeyEqual key_eq;
    [[no_unique_address]] Allocator alloc; // Может исчезнуть, если пустой
};

Это можно сравнить с утилизацией коробок из под пиццы для хранения в холодильнике, зачем они там нужны?

Например, стандартные хеш-функции (std::hash) для примитивов (int,  char*) часто не содержат состояния, а так же кастомные хешеры без паролей (например, возвращается key % 10)

Так же это могут быть компараторы, стандартные компараторы (std::equal_to<>,  std::less<>) почти всегда пустые. Ну и так же пользовательские, которые не имеют состояния (например всякие сравниватели строчек)).

Наконец аллокаторы. В стандартном std::allocator все методы статические (он не содержит полей). И, конечно, пользовательские аллокаторы без состояния.

Объект можно проверить ну «пустоту» с помощью std::is_empty:

static_assert(std::is_empty_v, "хешер пустой");
static_assert(std::is_empty_v, "компаратор пустой");
static_assert(std::is_empty_v>, "аллокатор пустой");

Важно понимать, что [[no_unique_address]] не сработает, если объект — часть наследника (это связано с выравниванием), или если где-то берется адрес
этого объекта &hash_fn, тогда компилятор будет считать адрес »важным» и у нас ничего не выйдет. Кстати это используют и в STL.

10. std: atomic_ref — «Потокобезопасность без мьютексов»

выкладка из cppreference.
будем поддерживать атомарные операции над объектами (если поддерживается платформой). Можно сделать lock-free версию для определённых операций:

#include 

template 
class thread_safe_hash_map {
    std::vector, std::atomic>> data;
    
    void insert(Key key, Value value) {
        std::atomic_ref(key).store(key);
    }
};

Конечно, здесь я уже разошелся, но я думаю было достаточно наглядно и правдоподобно, как по мне. Надеюсь вам понравилась статья, я очень старался над ее написанием.
Хочу оставить пожелание всем начинающим программистам: пишите код хорошо, пишите его с кайфом! :-)

Буду рад конструктивной дискуссии в комментариях, увидимся в следующей статье!