Хеш-код для трехмерных целочисленных координат с высокой пространственной когерентностью

Question

это мой первый вопрос на этих форумах:)

Я пишу класс координат в Java для пространственной системы вокселей октодерева. Эти координаты не являются координатами с плавающей точкой, они представляют собой 4-мерные целочисленные индексы в октрее (3 нормальных измерения X, Y, Z и четвертая часть для глубины в дереве). Первые 3 значения являются короткими, последнее измерение - байтом. При фактическом использовании сейчас используются только первые 11 бит шортов и только 3 бита байта, но это может быть изменено.

Теперь я пытаюсь написать «хорошую» хеш-функцию для этого класса. Проблема, с которой я борюсь, состоит в том, что координаты часто будут использоваться в высоко пространственных согласованных ситуациях (надеюсь, я использую правильную терминологию там). Я имею в виду, что часто координаты хешируются вместе с соседними соседями и другими соседними координатами.

Существует ли эффективная практика, чтобы эти координаты "близко друг к другу" создавали существенно разные хэш-коды?

Answer 1

Вам повезло: есть способ получить приличные кодовые координаты с высокой пространственной когерентностью, используя нечто, называемое Кривая Z-порядка .

Хитрость заключается в том, чтобы чередовать биты разных компонентов координат. Так что если у вас есть 3 8-битные координаты, такие как:

[XXXXXXXX, YYYYYYYY, ZZZZZZZZ]

Тогда закодированное значение z-кривой будет одним 24-битным значением:

XYZXYZXYZXYZXYZXYZXYZXYZ

При необходимости вы можете увеличить число битов или координат.

Это кодирование работает, потому что координаты, которые находятся близко в пространстве, будут иметь различия главным образом в битах младшего разряда. Таким образом, чередуя координаты, вы получаете фокусы различий в младших битах закодированного значения.

Еще одним интересным свойством является то, что младшие биты описывают координаты внутри кубов пространства. Таким образом, самая низкая 3-битная позиция адреса с 2x2x2 кубами, самая низкая 6-битная позиция адреса в 4 * 4 * 4 кубах, самая низкая 9-битная позиция в 8 * 8 * 8 кубов и т. Д. Так что это на самом деле довольно идеальная система для адресации -координаты в октрее.

Answer 2

«Значительно другое» действительно зависит от того, что вы делаете с хеш-кодом впоследствии.В некоторых случаях он будет подвергаться циклическому выбору, например, hash % size, где size - это размер используемой вами хэш-карты.Очевидно, что со временем это изменится.Я бы обычно использовал что-то вроде:

int hash = 23;
hash = hash * 31 + x;
hash = hash * 31 + y;
hash = hash * 31 + z;
hash = hash * 31 + depth;
return hash;

(в основном это взято из Effective Java .) Очевидно, это означает, что (x1, y1, z1) и (x1 + 1, y1 - 31, z1) будут иметь одинаковый хешкод, но если вы больше всего беспокоитесь о очень рядом с соседями, это не должно быть проблемой.

РЕДАКТИРОВАТЬ: ответ Микеры, скорее всего, будет работать лучше , носложнее кодировать.Я лично сначала попробую этот очень простой подход и посмотрю, достаточно ли он для ваших реальных случаев использования.Используйте все более эффективные, но сложные подходы, пока не найдете достаточно хороший.