Как происходит сравнение в std::unordered_map, если ключ является объектом?

Сравнение в std::unordered_map с объектами как ключи

Для использования объектов в качестве ключей в std::unordered_map нужно определить две вещи: хэш-функцию и функцию сравнения (operator==).

Проблема: объект как ключ

struct Point {
    int x, y;
};

int main() {
    std::unordered_map<Point, std::string> map;
    // Ошибка! Нет std::hash<Point> и operator== для Point
}

Решение 1: Специализация std::hash

struct Point {
    int x, y;
    
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// Специализируем std::hash для Point
namespace std {
    template<>
    struct hash<Point> {
        size_t operator()(const Point& p) const {
            // Комбинируем хэши x и y
            size_t h1 = std::hash<int>{}(p.x);
            size_t h2 = std::hash<int>{}(p.y);
            
            // XOR (простой, но не идеальный способ)
            return h1 ^ (h2 << 1);
            
            // Или boost::hash_combine
            // h1 ^= h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2);
            // return h1;
        }
    };
}

int main() {
    std::unordered_map<Point, std::string> map;
    
    Point p1{1, 2};
    Point p2{1, 2};
    Point p3{2, 3};
    
    map[p1] = "First";
    map[p2] = "Second";  // Перезаписывает first (p1 == p2)
    map[p3] = "Third";
    
    std::cout << map.size() << std::endl;  // 2 (p1 и p2 — один ключ)
}

Решение 2: Через пользовательскую функцию сравнения

struct Point {
    int x, y;
};

struct PointHash {
    size_t operator()(const Point& p) const {
        return std::hash<int>{}(p.x) ^ (std::hash<int>{}(p.y) << 1);
    }
};

struct PointEqual {
    bool operator()(const Point& a, const Point& b) const {
        return a.x == b.x && a.y == b.y;
    }
};

int main() {
    std::unordered_map<Point, std::string, PointHash, PointEqual> map;
    
    map[{1, 2}] = "Point";  // Работает
    
    std::cout << map[{1, 2}] << std::endl;  // "Point"
}

Процесс поиска в unordered_map

1. Вычисление хэша ключа

size_t hash = hash_function(key);

2. Определение bucket'а

size_t bucket_index = hash % bucket_count();

3. Перебор элементов в bucket'е

for (auto& pair : buckets[bucket_index]) {
    if (equality_function(pair.first, key)) {
        return pair.second;
    }
}

Практический пример: String как ключ

struct Person {
    std::string name;
    int age;
    
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

namespace std {
    template<>
    struct hash<Person> {
        size_t operator()(const Person& p) const {
            // Комбинируем хэши string и int
            size_t h1 = std::hash<std::string>{}(p.name);
            size_t h2 = std::hash<int>{}(p.age);
            
            // boost::hash_combine эквивалент
            h1 ^= h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2);
            return h1;
        }
    };
}

int main() {
    std::unordered_map<Person, std::string> map;
    
    Person alice{"Alice", 30};
    Person bob{"Bob", 25};
    
    map[alice] = "Engineer";
    map[bob] = "Designer";
    
    std::cout << map[{"Alice", 30}] << std::endl;  // "Engineer"
    
    return 0;
}

Как работает unordered_map внутри

template<typename Key, typename Value, typename Hash, typename Equal>
class unordered_map {
private:
    std::vector<std::list<std::pair<const Key, Value>>> buckets;
    Hash hash_func;
    Equal equal_func;
    size_t size = 0;
    
public:
    Value& operator[](const Key& key) {
        // 1. Вычислить хэш
        size_t h = hash_func(key);
        
        // 2. Найти bucket
        size_t idx = h % buckets.size();
        
        // 3. Найти в bucket'е
        for (auto& pair : buckets[idx]) {
            if (equal_func(pair.first, key)) {
                return pair.second;  // Найден
            }
        }
        
        // 4. Добавить новый элемент
        buckets[idx].emplace_back(key, Value{});
        size++;
        
        // 5. Может быть rehash
        if (load_factor() > max_load_factor()) {
            rehash(buckets.size() * 2);
        }
        
        return buckets[idx].back().second;
    }
    
    void rehash(size_t new_size) {
        std::vector<std::list<...>> new_buckets(new_size);
        
        // Переместить все элементы в новые bucket'ы
        for (auto& bucket : buckets) {
            for (auto& pair : bucket) {
                size_t new_h = hash_func(pair.first) % new_size;
                new_buckets[new_h].splice(/*move pair*/);
            }
        }
        
        buckets = std::move(new_buckets);
    }
};

Важность хорошей хэш-функции

Плохая хэш-функция:

// Всегда возвращает одно значение
struct BadHash {
    size_t operator()(const Point& p) const {
        return 42;  // Все элементы в одном bucket'е!
    }
};

// Результат: O(n) вместо O(1) в среднем

Хорошая хэш-функция:

struct GoodHash {
    size_t operator()(const Point& p) const {
        // Распределяет элементы равномерно
        size_t h = 0;
        h ^= std::hash<int>{}(p.x) + 0x9e3779b9 + (h << 6) + (h >> 2);
        h ^= std::hash<int>{}(p.y) + 0x9e3779b9 + (h << 6) + (h >> 2);
        return h;
    }
};

Lambda как hash function (C++17+)

struct Point { int x, y; };

int main() {
    auto hash = [](const Point& p) -> size_t {
        return std::hash<int>{}(p.x) ^ (std::hash<int>{}(p.y) << 1);
    };
    
    auto equal = [](const Point& a, const Point& b) {
        return a.x == b.x && a.y == b.y;
    };
    
    std::unordered_map<Point, std::string, 
                       decltype(hash), 
                       decltype(equal)> map(0, hash, equal);
    
    map[{1, 2}] = "Point";
}

Для tuple как ключ (C++17)

template<typename... Args>
struct TupleHash {
    size_t operator()(const std::tuple<Args...>& t) const {
        return hash_tuple(t, std::index_sequence_for<Args...>{});
    }
    
private:
    template<typename Tuple, std::size_t... I>
    size_t hash_tuple(const Tuple& t, std::index_sequence<I...>) const {
        size_t seed = 0;
        (..., (seed ^= std::hash<std::tuple_element_t<I, Tuple>>{}(std::get<I>(t)) + 
                     0x9e3779b9 + (seed << 6) + (seed >> 2)));
        return seed;
    }
};

int main() {
    using Key = std::tuple<int, std::string>;
    
    std::unordered_map<Key, int, TupleHash<int, std::string>> map;
    
    map[{1, "hello"}] = 100;
}

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

1. Для простых типов — используй встроенный std::hash

std::unordered_map<std::string, int> map;  // std::hash<string> встроен

2. Для своих типов — специализируй std::hash

namespace std {
    template<> struct hash<MyClass> { /* ... */ };
}

3. Проверяй performance — может быть нужен custom hash

// Если load_factor() > 0.8 — хэш функция плохая
std::cout << map.load_factor() << std::endl;

Итог

Для использования объектов в std::unordered_map:

1. Определить operator== для равенства
2. Определить std::hash или custom hash function
3. Убедиться, что хэш функция распределяет элементы равномерно
4. Помнить: правильная хэш-функция = O(1) производительность

Знание этого важно для проектирования правильных data structures в production коде.