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

Question

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

struct Point
{
    Row row;
    Column column;

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

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

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

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

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

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

Answer 3

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

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