хэширование множеств на с++

Ниже приведён обзор основных способов «хэширования» множеств в C++ и несколько связанных с этим приёмов. Под «множеством» здесь может пониматься как обычный контейнер std::set<T>, так и «набор» значений (например, массив или вектор), который мы хотим использовать в качестве ключа в каком‑либо unordered_* контейнере.

---

1. Использование стандартных unordered_set и unordered_map

1.1. Для базовых типов

Если мы хотим хранить множество (набор уникальных значений) из примитивных или стандартно хешируемых типов (например, int, std::string и т.п.), то используем:

cpp
#include <unordered_set>
#include <string>

int main() {
    std::unordered_set<int> uset1;
    uset1.insert(10);
    uset1.insert(20);
    uset1.insert(30);

    std::unordered_set<std::string> uset2;
    uset2.insert("hello");
    uset2.insert("world");

    return 0;
}

Стандартная библиотека уже предоставляет реализацию std::hash<T> для:

• целочисленных типов,
• плавающей запятой,
• std::string,
• std::basic_string,
• некоторых других простых типов.

В этих случаях вам не нужно писать свою функцию хеширования — она уже определена.

1.2. Для собственных структур и классов

Если нужно хранить элементы собственного (пользовательского) типа, в std::unordered_set требуется определить:

• функцию хеширования operator()(const MyType&),
• функцию сравнения на равенство (или, в ряде случаев, достаточно перегрузить == в самом классе, если используем стандартный std::equal_to).

Обычно это делается так:

cpp
#include <unordered_set>
#include <string>

// Пример пользовательского типа
struct Person {
    std::string name;
    int age;

    // Для удобства сравнения перегрузим operator==
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

// Определяем структуру-хешер
struct PersonHash {
    std::size_t operator()(const Person& p) const {
        // Простейший пример комбинирования hash от name и age:
        // 1) получаем std::hash<std::string>()(p.name)
//       2) комбинируем с hash<int>()(p.age).

        // Вариант 1: использовать boost::hash_combine (не в стандартной библиотеке).
        // Вариант 2: использовать std::hash_combine, если у вас есть C++20/23 расширение 
        // (официально пока нет, но можно выстроить аналог).
        // Вариант 3: вручную комбинировать.
        // Например, простой способ XOR + сдвиг:

        static const std::hash<std::string> hashStr;
        static const std::hash<int>         hashInt;

        std::size_t h1 = hashStr(p.name);
        std::size_t h2 = hashInt(p.age);

        // Простейшая схема (можно совершенствовать):
        // Можно взять, например, ((h1 << 1) ^ h2)
        std::size_t combined = (h1 << 1) ^ h2;
        return combined;
    }
};

int main() {
    // Теперь можем использовать std::unordered_set<Person, PersonHash>
    std::unordered_set<Person, PersonHash> people;

    Person p1 {"Alice", 30};
    Person p2 {"Bob",   25};
    Person p3 {"Alice", 30};

    people.insert(p1);
    people.insert(p2);
    people.insert(p3);

    // p1 и p3 равны (operator==) -> в множестве хранится один уникальный объект
    // Размер people будет 2
}

Таким образом, std::unordered_set позволяет эффективно хранить элементы по хешу, если:

1. Определён std::hash<T> (либо вы его дописали сами).
2. Тип умеет корректно сравниваться на равенство.

---

2. Хеширование самого std::set<T> (как ключа или элемента)

Если в программе нужно хранить в unordered_set (или unordered_map) объекты типа std::set<T>, то придётся написать пользовательский хешер и сравнение. Например:

cpp
#include <unordered_set>
#include <set>

struct SetIntHash {
    // Хеш-функция для std::set<int>
    std::size_t operator()(const std::set<int>& s) const {
        // Идея: пробежаться по всем элементам внутри s и
        // аккуратно их "смешать" (combine) в один хеш.

        // Для примера:
        std::size_t result = 0;
        static const std::hash<int> intHash;

        for (int val : s) {
            // Простейший способ: 
            // result = (result * 31) ^ intHash(val);
            // Или через сдвиги:
            result ^= (intHash(val) + 0x9e3779b97f4a7c15ULL + (result << 6) + (result >> 2));
        }
        return result;
    }
};

struct SetIntEqual {
    bool operator()(const std::set<int>& a, const std::set<int>& b) const {
        // Для std::set, достаточно сравнить их напрямую:
        return a == b; // оператор== у std::set проверяет равенство по элементам
    }
};

int main() {
    std::unordered_set<std::set<int>, SetIntHash, SetIntEqual> usetOfSets;

    std::set<int> s1 {1, 2, 3};
    std::set<int> s2 {2, 3, 4};
    std::set<int> s3 {1, 2, 3};

    usetOfSets.insert(s1);
    usetOfSets.insert(s2);
    usetOfSets.insert(s3);

    // s1 и s3 идентичны -> в наборе будут храниться 2 уникальных элемента
    // Размер usetOfSets будет 2

    return 0;
}

Важные замечания

1. std::set внутри себя упорядочен (красно-чёрное дерево). Это значит, что доступ к элементам для хеширования можно делать напрямую в цикле.
2. Если ваша задача — «множество множеств», и при этом их размеры не слишком велики, то решение с unordered_set<std::set<int>> может работать. Однако хранить большие std::set в unordered_set бывает не очень эффективно. В зависимости от ситуации могут быть альтернативы:
   • Использовать битовые маски (bitmask), если диапазон элементов небольшой.
   • Использовать std::vector<int> в отсортированном виде (для семантики множества) и хешировать его аналогично.
   • Подумать о более специфичных структурах данных.

---

3. Хеширование «множества» в виде массива/вектора

Когда элементы набора представляют собой, скажем, отсортированный std::vector<int>, можно использовать похожую идею:

cpp
#include <unordered_set>
#include <vector>
#include <algorithm>

struct VecIntHash {
    std::size_t operator()(const std::vector<int>& vec) const {
        // Аналогичное комбинирование
        std::size_t h = 0;
        static const std::hash<int> intHash;
        for (int val : vec) {
            h ^= (intHash(val) + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2));
        }
        return h;
    }
};

struct VecIntEqual {
    bool operator()(const std::vector<int>& a, const std::vector<int>& b) const {
        return a == b; // побитовое равенство (для вектора)
    }
};

int main() {
    std::unordered_set<std::vector<int>, VecIntHash, VecIntEqual> uset;

    std::vector<int> v1 = {1,2,3};
    std::vector<int> v2 = {2,3,1};
    std::vector<int> v3 = {1,2,3};

    // Если "множество" подразумевает, что порядок не важен,
    // нужно отсортировать перед вставкой. Иначе {1,2,3} и {2,3,1} будут разными:
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
    std::sort(v3.begin(), v3.end());

    uset.insert(v1);
    uset.insert(v2);
    uset.insert(v3);

    // В итоге будет 1 уникальный элемент, т.к. все три отсортированные вектора совпадают

    return 0;
}

---

4. Дополнительные советы по написанию хеш-функций

1. Комбинирование хешей. Если нужно совместить хеши нескольких полей, хорошей практикой считается использовать что-то вроде:

   cpp
   // Вариант "ручного" combine
   template<typename T>
   inline void hash_combine(std::size_t& seed, const T& val) {
       seed ^= std::hash<T>()(val) + 0x9e3779b97f4a7c15ULL + (seed << 6) + (seed >> 2);
   }

   Тогда:

   cpp
   std::size_t operator()(const Person& p) const {
       std::size_t seed = 0;
       hash_combine(seed, p.name);
       hash_combine(seed, p.age);
       return seed;
   }

2. Уникальность ключей. Хеш-функция лишь помогает группировать элементы. Для точной проверки равенства используется operator==, поэтому всегда нужно обе части: корректная функция хеширования и корректное равенство.
3. Производительность. При больших объёмах данных может оказаться, что использование std::set внутри std::unordered_set слишком медленное и/или потребляет много памяти. Рассмотрите альтернативы в зависимости от задачи.

---

Итог

• Если у вас примитивные (или стандартные) типы — используйте std::unordered_set<T> без дополнительных перегрузок.
• Если тип пользовательский, определите структуру-хешер и (при необходимости) функтор равенства.
• Если хотите использовать в качестве ключа само std::set<T> (или std::vector<T> как множество), пишите кастомный хешер, аккуратно комбинируя хеши элементов.
• Следите за эффективностью: иногда вместо того, чтобы хранить std::set<int> как ключ, можно использовать компактное представление (битовые маски и т. д.).

Таким образом, «хэширование множества» в C++ сводится к написанию корректной хеш-функции и при необходимости — сравнителя. Стандартные контейнеры (std::unordered_set, std::unordered_map) позволяют это сделать без лишних сложностей.