В мире программирования хэш-таблицы и хэш-множества являются одними из наиболее используемых структур данных. Они позволяют быстро хранить и искать данные, что делает их незаменимыми во многих приложениях. Но как можно еще больше повысить их производительность? Ответ на этот вопрос дает Hopscotch хеширование - эффективный метод реализации хэш-таблиц, который был впервые представлен в 2014 году исследователями из компании IBM.

Что такое Hopscotch хеширование?

Hopscotch хеширование - это разновидность открытой адресации в хэш-таблицах. Оно сочетает в себе преимущества традиционной открытой адресации и метода линейного зондирования. Hopscotch хеширование работает путем хранения ключей в небольшом, заранее определенном диапазоне ячеек, называемом "окрестностью" (neighborhood). Это позволяет значительно уменьшить количество проб при поиске ключа.

Основные понятия

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

Преимущества Hopscotch хеширования

Hopscotch хеширование имеет ряд преимуществ перед традиционными методами хеширования:

  • Высокая производительность: Hopscotch хеширование обеспечивает высокую скорость поиска ключей.
  • Низкая задержка: Hopscotch хеширование имеет низкую задержку при поиске ключей.
  • Хорошая локальность кэша: Hopscotch хеширование обеспечивает хорошую локальность кэша, что улучшает производительность.

Реализация хэш-таблицы на основе Hopscotch хеширования в C++

Ниже приведен пример реализации хэш-таблицы на основе Hopscotch хеширования в C++:

#include <iostream>#include <vector>const int NeighborhoodSize = 4; // размер окрестностиtemplate <typename K, typename V>class HopscotchHashMap {private:    std::vector<std::pair<K, V>> buckets; // хэш-таблица    std::vector<int> offsets; // массив смещенийpublic:    HopscotchHashMap(int size) : buckets(size), offsets(size, 0) {}    // Хэш-функция    int hash(const K& key) {        return std::hash<K>()(key) % buckets.size();    }    // Вставка ключа и значения    void insert(const K& key, const V& value) {        int index = hash(key);        for (int i = 0; i < NeighborhoodSize; ++i) {            int neighborIndex = (index + i) % buckets.size();            if (buckets[neighborIndex].first == key) {                buckets[neighborIndex].second = value;                return;            }            if (buckets[neighborIndex].first == 0) {                buckets[neighborIndex] = std::make_pair(key, value);                return;            }        }        // Если окрестность заполнена, применяем линейное зондирование        for (int i = 0; i < buckets.size(); ++i) {            int newIndex = (index + i) % buckets.size();            if (buckets[newIndex].first == 0) {                buckets[newIndex] = std::make_pair(key, value);                return;            }        }    }    // Поиск значения по ключу    V get(const K& key) {        int index = hash(key);        for (int i = 0; i < NeighborhoodSize; ++i) {            int neighborIndex = (index + i) % buckets.size();            if (buckets[neighborIndex].first == key) {                return buckets[neighborIndex].second;            }        }        // Если ключ не найден, возвращаем значение по умолчанию        return V();    }};int main() {    HopscotchHashMap<int, std::string> hashMap(10);    hashMap.insert(1, "one");    hashMap.insert(2, "two");    std::cout << hashMap.get(1) << std::endl; // Вывод: one    std::cout << hashMap.get(2) << std::endl; // Вывод: two    return 0;}

Реализация хэш-множества на основе Hopscotch хеширования в C++

Хэш-множество можно реализовать на основе хэш-таблицы, хранящей только ключи.