Как можно улучшить хеш-функцию для использования в контесте на Яндексе?

Как структурировать код так, чтобы можно было использовать структуру `Circle` вместе с `std::unordered_set` без указания дополнительных шаблонных параметров, помимо самого `Circle`?
  • 25 июля 2024 г. 18:23
Ответы на вопрос 2
1. Для улучшения хеш-функции можно использовать более сложный алгоритм, который учитывает больше параметров объекта `Circle`. Например, можно комбинировать значения радиуса, центра круга, цвета и других свойств круга для создания уникального хеша.

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

Чтобы структурировать код так, чтобы объекты `Circle` могли использоваться с `std::unordered_set` без дополнительных шаблонных параметров, можно перегрузить операторы `==` и `std::hash` для `Circle`.

Примерно код может выглядеть следующим образом:

```cpp
#include <unordered_set>

struct Circle {
    int radius;
    int x, y;
    std::string color;

    bool operator==(const Circle& other) const {
        return radius == other.radius && x == other.x && y == other.y && color == other.color;
    }
};

namespace std {
    template <>
    struct hash<Circle> {
        size_t operator()(const Circle& c) const {
            size_t hash_val = 0;
            hash_val ^= hash<int>()(c.radius) + 0x9e3779b9 + (hash_val<<6) + (hash_val>>2);
            hash_val ^= hash<int>()(c.x) + 0x9e3779b9 + (hash_val<<6) + (hash_val>>2);
            hash_val ^= hash<int>()(c.y) + 0x9e3779b9 + (hash_val<<6) + (hash_val>>2);
            hash_val ^= hash<std::string>()(c.color) + 0x9e3779b9 + (hash_val<<6) + (hash_val>>2);
            return hash_val;
        }
    };
}

int main() {
    std::unordered_set<Circle> circles;
    
    Circle c1 = {10, 0, 0, "red"};
    Circle c2 = {15, 5, 5, "blue"};

    circles.insert(c1);
    circles.insert(c2);

    return 0;
}
```

В данном примере мы перегрузили оператор `==` для сравнения объектов `Circle` и определили специализацию шаблона `std::hash` для создания уникального хеша на основе значений радиуса, координат центра и цвета круга. Теперь объекты `Circle` могут использоваться в `std::unordered_set` без указания дополнительных шаблонных параметров.
Сам допёр до решения. Дело было в том, что не надо было хешировать color, т.к. с разным цветом круги считаются равными. 
Вот готовое решение:
#include
#include
struct Circle {
int x, y, r;
char color;
Circle(int x, int y, int r, char color) : x(x), y(y), r(r), color(color) {}
bool operator== (const Circle& another) const{
return (x == another.x) && (y == another.y) && (r == another.r);
}
};
template <>
struct std::hash {
size_t operator()(const Circle& c) const {
size_t hash = 17;
hash = hash * 31 + std::hash()(c.x);
hash = hash * 31 + std::hash()(c.y);
hash = hash * 31 + std::hash()(c.r);
return hash;
}
};
Похожие вопросы