Хеширование 2D, 3D и ND векторов

Question

Что такое хорошие функции хеширования (быстрое, хорошее распределение, мало коллизий) для хеширования 2-х и 3-х векторов, состоящих из 32-битных операций IEEE. Я предполагаю общие 3d-векторы, но алгоритмы, предполагающие нормали (всегда в [-1,1]), также приветствуются. Я также не боюсь битовых манипуляций, так как IEEE-плавающие всегда IEEE-плавающие.

Еще одна более общая проблема - это хэширование вектора с плавающей запятой Nd, где N довольно мало (3-12) и постоянно, но не известно во время компиляции. В настоящий момент я просто беру эти поплавки как uints и XOR их вместе, что, вероятно, не лучшее решение.

Answer 1

Существует пространственная хеш-функция, описанная в Оптимизированное пространственное хеширование для обнаружения столкновения деформируемых объектов Они используют хэш-функцию

hash (x, y, z) = (x p1 xor y p2 xor z p3) мод n

где p1, p2, p3 большие простые числа, в нашем случае 73856093, 19349663, 83492791 соответственно. значение n - размер хеш-таблицы.

В статье x, y и z являются дискретизированными координатами; Вы также можете использовать двоичные значения ваших чисел с плавающей точкой.

Answer 2

У меня есть два предложения.

• Предположим ячейку сетки размером l и квантовать x , y и z координирует вычисление ix = пол (х / л) , iy = пол (г / л) и iz = пол (z/ l) , где ix, iy и iz являются целыми числами.Теперь используйте хеш-функцию, определенную в Оптимизированное пространственное хеширование для обнаружения столкновений деформируемых объектов

Если вы не выполните квантование, оно не будет чувствительно к близости (локальность).

• Хеширование с учетом локальных особенностей упоминалось для хеширования векторов более высокой размерности.Почему бы не использовать их для 3d или 2d векторов?Вариант LSH, использующий адаптированную для евклиановой метрики расстояния (что нам нужно для двухмерных и трехмерных векторов), называется локально-чувствительным хешированием с использованием p-стабильных распределений.Очень читаемый учебник: здесь .