Хорошая хеш-функция для двумерного индекса

Question

У меня есть структура под названием Point. Суть довольно проста:

struct Point
{
    Row row;
    Column column;

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

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

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

Итак, я хочу иметь unordered_set из Points. Обычно этот набор может содержать, например, каждую точку на терминале 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();
    }
};

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

Answer 1

Следующая методика дана в Effective 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 это функция для хеширования одного целого числа Вы можете посетить эту страницу, чтобы найти множество хороших хеш-функций для одиночных целых чисел.

Answer 2

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

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

Answer 3

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

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