Что требуется для использования структуры в качестве ключа unordered_set?

Использование структуры в качестве ключа unordered_set

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

Что требуется

1. Функция хеширования (hash function) — преобразует объект в целое число
2. Оператор равенства (equality operator) — проверяет, равны ли два объекта

Базовый пример

struct Person {
    std::string name;
    int age;
    
    // Оператор равенства ОБЯЗАТЕЛЕН
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

// Специализация std::hash для Person
namespace std {
    template<>
    struct hash<Person> {
        size_t operator()(const Person& p) const {
            // Комбинируем хеши полей
            size_t h1 = hash<std::string>()(p.name);
            size_t h2 = hash<int>()(p.age);
            return h1 ^ (h2 << 1);
        }
    };
}

// Использование
std::unordered_set<Person> people;
people.insert(Person{"Alice", 30});
people.insert(Person{"Bob", 25});

if (people.count(Person{"Alice", 30})) {
    std::cout << "Найдена";
}

Реализация функции хеширования

Способ 1: XOR комбинация

Простой, но может привести к коллизиям:

namespace std {
    template<>
    struct hash<Person> {
        size_t operator()(const Person& p) const {
            size_t h1 = hash<std::string>()(p.name);
            size_t h2 = hash<int>()(p.age);
            return h1 ^ h2;
        }
    };
}

Способ 2: Сдвиг и комбинация (лучше)

namespace std {
    template<>
    struct hash<Person> {
        size_t operator()(const Person& p) const {
            size_t h1 = hash<std::string>()(p.name);
            size_t h2 = hash<int>()(p.age);
            // Популярная формула: h1 XOR (h2 + смещение)
            return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
        }
    };
}

Способ 3: boost::hash_combine (из Boost)

Есть даже рекомендуемый стандарт для комбинации:

inline void hash_combine(size_t& seed, const std::string& val) {
    seed ^= std::hash<std::string>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

inline void hash_combine(size_t& seed, int val) {
    seed ^= std::hash<int>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

namespace std {
    template<>
    struct hash<Person> {
        size_t operator()(const Person& p) const {
            size_t seed = 0;
            hash_combine(seed, p.name);
            hash_combine(seed, p.age);
            return seed;
        }
    };
}

Полный пример с обеими реализациями

#include <unordered_set>
#include <string>
#include <iostream>

struct Product {
    int id;
    std::string category;
    double price;
    
    // 1. Оператор равенства
    bool operator==(const Product& other) const {
        return id == other.id && 
               category == other.category && 
               price == other.price;
    }
};

// 2. Специализация hash
namespace std {
    template<>
    struct hash<Product> {
        size_t operator()(const Product& p) const {
            size_t h1 = hash<int>()(p.id);
            size_t h2 = hash<std::string>()(p.category);
            // Примечание: хеширование double нетривиально из-за precision
            size_t h3 = hash<long long>()(*reinterpret_cast<const long long*>(&p.price));
            
            return h1 ^ (h2 << 1) ^ (h3 << 2);
        }
    };
}

int main() {
    std::unordered_set<Product> products;
    
    products.insert(Product{1, "electronics", 99.99});
    products.insert(Product{2, "books", 19.99});
    products.insert(Product{1, "electronics", 99.99}); // Дубликат
    
    std::cout << "Размер: " << products.size() << std::endl; // 2
    
    Product search{1, "electronics", 99.99};
    if (products.find(search) != products.end()) {
        std::cout << "Найден продукт\n";
    }
    
    return 0;
}

Альтернатива: использовать std::set вместо unordered_set

Если реализовать хеш функцию сложно, можно использовать std::set, который требует только оператор сравнения:

struct Person {
    std::string name;
    int age;
    
    // Для std::set достаточно оператора <
    bool operator<(const Person& other) const {
        if (name != other.name) return name < other.name;
        return age < other.age;
    }
};

std::set<Person> people; // Работает без специализации hash!
popple.insert(Person{"Alice", 30});

Типичные ошибки

1. Забыли оператор ==

   // ❌ Не скомпилируется
   std::unordered_set<Person> s;
   

2. Плохая функция хеширования (много коллизий)

   // ❌ Плохо — коллизии
   size_t hash(const Person& p) { return p.age % 10; }
   

3. Изменение объекта в unordered_set

   Person p{"Alice", 30};
   auto it = people.insert(p).first;
   it->age = 31;  // ❌ ОПАСНО! Нарушает инвариант хеш-таблицы
   

Рекомендации

• Хеш-функция должна быть быстрой — её вызывают часто
• Распределение должно быть равномерным — избегайте коллизий
• Используйте std::set, если хеш-функция сложна
• Не изменяйте ключи в unordered_set
• Тестируйте распределение хеша для ваших данных

Правильная реализация хеш-функции критична для производительности unordered_set!