Хороший способ хешировать вектор с плавающей точкой?

Мне хорошо знакомы все проблемы, связанные с сравнением поплавков. Это и есть причина этого вопроса.
Я ищу для создания быстрой хэш-таблицы для значений, представляющих собой 3D-векторы (3 поплавка - x, y, z). Можно предположить, что длина вектора всегда равна 1,0 (sqrt(x*x+y*y+z*z) 1,0)

По сути, это означает, что я ищу хеш-функцию, которая принимает значения, которые почти равны одному и тому же значению без знака int и соответствующему оператору равенства, который является истинным, если значения хэша равны (не обязательно, только если они равный)

Изменить -
Ложные срабатывания (то есть векторы, которые отличаются друг от друга, но сопоставляются с одним и тем же ведром) являются заданными, поскольку это хэш-таблица.
Ложные негативы (т.е. Векторы, близкие, но отображающие разные ведра) нежелательны, но, похоже, нет способа избежать их. В моем случае они не будут вызывать общий полом, просто дублирование данных, с которым мне придется жить.

Ответ 1

Я думаю, что то, что вы ищете, напрямую не возможно. Важным свойством равенства является то, что оно транзитивно. (т.е. если a == b и b == c, то a == c). Однако с дистанционной оценкой вы действительно не хотите этого свойства. Пример:

Возьмите один поплавок (для простоты). Предположим, мы хотим, чтобы хэш каждого поплавка так, чтобы плавать менее 1е-3, одинаковое значение. Теперь предположим, что мы добавим к этой хеш-таблице 1000 значений float всех 1е-4. Любые соседние 2 значения должны иметь хеш для одного и того же float, так как они ближе, чем 1e-3. Однако из-за транзитивности соседние значения этих значений также должны иметь одинаковое значение, а их соседи и т.д. В результате все 1000 значений, включая пары дальше, чем 1е-3 друг от друга, будут иметь хеш с одним и тем же целым числом. Если вы должны были нарисовать эти точки на картинке:

A  B  C  D  E  F  G  H ... Y Z

Предположим, что все промежутки являются < 1е-3 друг от друга, но А и Z > 1е-3 (не для масштаба!). Это не может быть выполнено, потому что, если хеш (A) == hash (B) и hash (B) == hash (C) и т.д. Для всех пар (поскольку они равны < 1e-3 отдельно), чем hash ( A) должен == hash (Z).

Один из возможных вариантов состоит в том, чтобы определить области вашего векторного пространства, в которых все векторы будут иметь хэш с одним и тем же значением (т.е. объединить их перед их хэшированием), но вы все равно можете получить 2 вектора на краях их соответствующих пространств, которые близки вместе, но хэш на другое значение. Вы можете обойти это, выполнив поиск всех соседних пространств для вектора. (т.е. в 1-м случае выше, вы должны округлить все векторы до ближайшего кратного 1e-3, а затем искать соседей, поэтому 5.3e-3 будет искать 5e-3, 4e-3 и 6-e3. В случаях с более высоким размером вам придется искать соседей во всех измерениях.)

Ответ 2

Я бы преобразовал значения float в целые числа следующим образом:

unsigned int IntValue = (int)(floatValue * MULT) + MULT;

чтобы вы получили некоторые первые цифры, а затем используйте

const MULT1 = (MULT << 1) + 1;
unsigned long long HashValue = (xIntValue * MULT1  * MULT1) + (yIntValue * MULT1) + zIntValue;

как значение хэша (используя (MULT * 2) + 1, потому что IntValues будет находиться между 0 и MULT * 2 включительно).

Необходимая память будет зависеть от мультипликатора MULT. Например, используя 32, вы получите хэш-таблицу с размером 64 * 64 * 64 * (размер хэш-элемента) = 262144 * (размер хэш-единицы).

Ответ 3

Некоторые языки (C, Java 5) позволяют вам получить доступ к двоичному значению ваших поплавков. Таким образом, вы можете извлечь первые N бит мантиссы (игнорируя последние несколько бит, которые вызывают проблемы при сравнении) и вычислить хэш из этого.

Ответ 4

Можете ли вы активировать свою проблему?

Предполагая, что вы используете хэш-карту для сопоставления некоторых дополнительных данных определенным векторам, вы можете просто использовать XOR двоичных представлений компонентов (если это возможно на выбранном вами языке). Затем используйте столько LSB (для уменьшения коллизий), сколько вам нужно для хэш-карты. Разумеется, это свойство обладает тем свойством, что два одинаковых (с точки зрения с плавающей точкой) векторов могут иметь не один и тот же хеш (например, плавающая точка IEEE 0 равна -0, но они имеют различный знаковый бит).

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

Ответ 5

Я думаю, вы эффективно пытаетесь решить ближайшую проблему K. Я верю, что вы ищете чувствительность к местоположению. Кроме того, вы можете использовать квадрантные структуры для достижения того же результата.

Ответ 6

не знают, как быстро это может произойти, но поскольку у вас есть единичные векторы, все они лежат на поверхности сферы. конвертировать в http://en.wikipedia.org/wiki/Spherical_coordinate_system. затем используйте phi и theta, чтобы выбрать ведро. не будет ложных срабатываний. вы можете посмотреть в соседних ячейках для ложных негативов.

Ответ 7

Вам нужно, чтобы это была быстрая хеш-таблица или была бы древовидная структура?

Мне кажется, что было бы проще искать совпадающие поплавки в дереве поиска некоторых Сортировать. A B-Tree минимизирует количество промахов в кешках, предполагая, что вы выбираете правильный размер node. Это должно сделать это довольно быстро на практике.