Хорошая хэш-функция для индекса 2d

У меня есть структура, называемая Point. Точка довольно проста:

struct Point
{
    Row row;
    Column column;

    // some other code for addition and subtraction of points is there too
}

Row и Column в основном прославлены int s, но мне стало неловко переносить входные аргументы в функции и давал им каждый класс-оболочку.

Сейчас я использую set точек, но повторные поиски действительно замедляют работу. Я хочу переключиться на unordered_set.

Итак, я хочу иметь unordered_set of Point s. Обычно этот набор может содержать, например, каждую точку на терминале 80x24 = 1920 точек. Мне нужна хорошая хэш-функция. Я просто придумал следующее:

struct PointHash : public std::unary_function<Point, std::size_t>
{
    result_type operator()(const argument_type& val) const
    {
        return val.row.value() * 1000 + val.col.value();
    }
};

Однако я не уверен, что это действительно хорошая хеш-функция. Я хотел что-то быстро, так как мне нужно очень быстро сделать много поисков. Есть ли лучшая хеш-функция, которую я могу использовать, или это нормально?

Ответ 1

Следуя методу, дается в Эффективной Java (2-е издание) и цитируется там в Программе в Scala. Имейте первичную константу (мы скажем 53, но вы можете найти что-то большее, чтобы получить более равномерное распределение здесь) и выполнить умножение и добавление следующим образом:

(53 + int_hash(row)) * 53 + int_hash(col)

Для большего количества значений (например, вы добавляете координату z) просто держите вложенность, например

((53 + int_hash(row)) * 53 + int_hash(col)) * 53 + int_hash(z)

Где int_hash - функция для хэширования единственного целого. Вы можете посетить эту страницу, чтобы найти кучу хороших хэш-функций для одиночных целых чисел.

Ответ 2

Я думаю, что выполнение бит-дро на 10 вместо этого было бы более эффективным, чем умножение на 1000.

return (val.row.value()<<10) + val.col.value();

Ответ 3

С достаточно небольшим доменом вы можете создать идеальную хеш-функцию. Или, возможно, просто используйте 2-мерный массив. Для больших объемов данных используйте умножение на основе простых чисел и mod для вашего размера таблицы (и если ваша таблица является номером базы 2). Это устраняет деление /mod, которое может быть дорогостоящим для небольших систем с встроенным типом.

Или найдите любое количество хеш-функций с целым числом, которые уже существуют. Убедитесь, что вы измеряете любую функцию хэша, которую вы создаете для столкновения. Достаточные столкновения исключают любые преимущества над методами O (n log n), такими как карты/деревья.