Хэш-таблица C ++ - Как разрешается коллизия для unordered_map с пользовательским типом данных в качестве ключей? - PullRequest
Новая
       82

Хэш-таблица C ++ - Как разрешается коллизия для unordered_map с пользовательским типом данных в качестве ключей?

0 голосов
/ 28 августа 2018

Я определил класс с именем 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 знает, как разрешить столкновение в этом случае? Нужно ли что-нибудь добавлять для разрешения коллизий?

Ответы [ 2 ]

0 голосов
/ 02 сентября 2018

Зная, что Point предназначен для хранения координат в изображении , лучшая хеш-функция здесь: 

pt.x() + pt.y() * width

, где width - ширина изображения.

Учитывая, что x является значением в диапазоне [0, width-1], вышеуказанная хеш-функция выдает уникальное число для любого действительного значения pt. Столкновения невозможны.

Обратите внимание, что это значение хеш-функции соответствует линейному индексу для точки pt, если вы сохраняете изображение как один блок памяти. То есть, учитывая, что y также находится в ограниченном диапазоне ([0, height-1]), все сгенерированные значения хеш-функции находятся в диапазоне [0, width* height-1], и все целые числа в этом диапазоне могут быть сгенерированы. Таким образом, рассмотрите возможность замены вашей хеш-таблицы простым массивом (то есть изображением). Изображение - это лучшая структура данных для сопоставления местоположения пикселя со значением.

0 голосов
/ 28 августа 2018

Это ужасная хеш-функция. Но это законно, поэтому ваша реализация будет работать.

Правило (и действительно единственное правило) для Hash and 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} одинаковое хеш-значение. Более серьезно, любая коллекция точек в маленьком прямоугольнике будет совместно использовать одно и то же небольшое количество различных хеш-значений, потому что старшие биты хеш-значений будут одинаковыми.

...