hashmap — C ++ Hash Table — Как разрешается коллизия для unordered_map с пользовательским типом данных в качестве ключей?
Я определил класс под названием Point который должен использоваться в качестве ключа внутри unordered_map, Итак, я предоставил operator== функция внутри класса, и я также предоставил template specialization за std::hash, Основываясь на моих исследованиях, это две вещи, которые я счел необходимыми. Соответствующий код выглядит так:
class Point
{
int x_cord = {0};
int y_cord = {0};
public:
Point()
{
}
Point(int x, int y):x_cord{x}, y_cord{y}
{
}
int x() const
{
return x_cord;
}
int y() const
{
return y_cord;
}
bool operator==(const Point& pt) const
{
return (x_cord == pt.x() && y_cord == pt.y());
}
};
namespace std
{
template<>
class hash<Point>
{
public:
size_t operator()(const Point& pt) const
{
return (std::hash<int>{}(pt.x()) ^ std::hash<int>{}(pt.y()));
}
};
}
// Inside some function
std::unordered_map<Point, bool> visited;
Программа скомпилирована и дала правильные результаты в случаях, которые я тестировал. Тем не менее, я не уверен, достаточно ли этого при использовании пользовательского класса в качестве ключа. Как работает unordered_map знаете, как разрешить столкновение в этом случае? Нужно ли что-нибудь добавить для разрешения коллизий?
Решение
Это ужасная хеш-функция. Но это законно, поэтому ваша реализация будет работать.
Правило (и действительно единственное правило) для Hash и Equals:
- если
a == b, затемstd::hash<value_type>(a) == std::hash<value_type>(b),
(Также важно, чтобы и Hash, и Equals всегда выдавали одно и то же значение для одних и тех же аргументов. Раньше я думал, что это само собой разумеется, но я видел несколько SO вопросов, где unordered_map приводил к неожиданным результатам именно потому, что одна или обе эти функции зависели на какую-то внешнюю ценность.)
Это было бы удовлетворено хэш-функцией, которая всегда возвращала 42, и в этом случае карта становилась довольно медленной, когда заполнялась. Но кроме проблемы скорости, код будет работать.
std::unordered_map использует цепочечный хеш, не хэш с открытым адресом. Все записи с одинаковыми значениями хеш-функции помещаются в одну корзину, которая является связанным списком. Таким образом, низкокачественные хэши не очень хорошо распределяют записи между сегментами.
Понятно что твой хеш дает {x, y} а также {y, x} то же самое хеш-значение. Более серьезно, любая коллекция точек в маленьком прямоугольнике будет совместно использовать одно и то же небольшое количество различных хеш-значений, потому что старшие биты хеш-значений будут одинаковыми.
Другие решения
Знаю это Point предназначен для хранения координат в изображении, лучшая хеш-функция здесь:
pt.x() + pt.y() * width
где width ширина изображения.
Учитывая, что x это значение в диапазоне [0, width-1]вышеупомянутая хеш-функция создает уникальное число для любого допустимого значения pt, Столкновения невозможны.
Обратите внимание, что это значение хеша соответствует линейному индексу для точки pt если вы сохраняете изображение как один блок памяти. То есть дано y также в ограниченном диапазоне ([0, height-1]), все сгенерированные значения хеша находятся в пределах диапазона [0, width* height-1]и все целые числа в этом диапазоне могут быть сгенерированы. Таким образом, рассмотрите возможность замены вашей хеш-таблицы простым массивом (то есть изображением). Изображение — это лучшая структура данных для сопоставления местоположения пикселя со значением.