Хэш-функция, предоставляющая уникальный uint из целочисленной координатной пары

Ответ 1

хеш-функция, которая ГАРАНТИРОВАНА без конфликтов, не является хэш-функцией:)

Вместо использования хэш-функции вы можете рассмотреть использование двоичных разделов (BSPs) или XY-деревьев (тесно связанных).

Если вы хотите хэш два uint32 в один uint32, не используйте такие вещи, как Y и 0xFFFF, потому что это отбрасывает половину бит. Сделайте что-то вроде

(x * 0x1f1f1f1f) ^ y

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

Ответ 2

Cantor перечисление пар

   n = ((x + y)*(x + y + 1)/2) + y

может быть интересным, так как он ближе всего к вашей исходной ширине canvas * y + x, но будет работать для любых x или y. Но для реального хэша int32 в реальном мире, а не для сопоставления пар целых чисел с целыми числами, вам, вероятно, лучше работать с небольшими манипуляциями, такими как Bob Jenkin mix и называя это с помощью x, y и соли.

Ответ 3

Как и Emil, но обрабатывает 16-битные переполнения в x таким образом, чтобы производить меньше коллизий и требует меньше инструкций для вычисления:

hash = ( y << 16 ) ^ x;

Ответ 4

Ваш "идеал" невозможен.

Вы хотите, чтобы отображение (x, y) → i, где x, y и я - все 32-битные величины, что гарантировано не генерирует повторяющиеся значения i.

Вот почему: предположим, что существует функция hash(), так что хеш (x, y) дает разные целочисленные значения. Для x есть 2 ^ 32 (около 4 миллиарда) значений и 2 ^ 32 значений y. Таким образом, hash (x, y) имеет 2 ^ 64 (около 16 миллионов триллионов) возможных результатов. Но в 32-битном int есть только 2 ^ 32 возможных значения, поэтому результат hash() не будет соответствовать 32-битовому int.

См. также http://en.wikipedia.org/wiki/Counting_argument

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

Ответ 5

Может быть,?

hash = ((y & 0xFFFF) << 16) | (x & 0xFFFF);

Работает до тех пор, пока x и y могут быть сохранены как 16-битные целые числа. Однако не знаю, сколько коллизий это вызывает для больших целых чисел. Одна из идей может заключаться в том, чтобы по-прежнему использовать эту схему, но объединить ее со схемой сжатия, например, взять модуль 2 ^ 16.

Ответ 6

Если вы можете сделать a = ((y и 0xffff) < 16) | (x и 0xffff), вы можете впоследствии применить обратимое 32-битное микс к a, например, Thomas Wang

uint32_t hash( uint32_t a)
    a = (a ^ 61) ^ (a >> 16);
    a = a + (a << 3);
    a = a ^ (a >> 4);
    a = a * 0x27d4eb2d;
    a = a ^ (a >> 15);
    return a;
}

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

Ответ 7

Если вы уже используете языки или платформы, для которых все объекты (даже примитивные, такие как целые), реализованы встроенные хеш-функции (Java-платформа Языки, такие как Java, языки платформы .NET, такие как С#. И другие, такие как Python, Ruby, и т.д). Вы можете использовать встроенные значения хэширования как строительный блок и добавить свой "хеширующий вкус" в микс. Как:

// C# code snippet 
public class SomeVerySimplePoint { 

public int X;
public int Y;

public override int GetHashCode() {
   return ( Y.GetHashCode() << 16 ) ^ X.GetHashCode();
}

}

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

Ответ 8

Вы можете сделать

a >= b ? a * a + a + b : a + b * b

взято здесь.

Это работает для точек в положительной плоскости. Если ваши координаты также могут быть в отрицательной оси, вам нужно будет:

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
A >= B ? A * A + A + B : A + B * B;

Но для ограничения вывода на uint вам нужно будет сохранить верхнюю границу для ваших входов. и если да, то оказывается, что вы знаете границы. Другими словами, при программировании непрактично писать функцию, не имея идеи по целочисленному типу, ваши входы и выходные данные могут быть, и если так, то определенно будет нижняя граница и верхняя граница для каждого целочисленного типа.

public uint GetHashCode(whatever a, whatever b)
{
    if (a > ushort.MaxValue || b > ushort.MaxValue || 
        a < ushort.MinValue || b < ushort.MinValue)
    {    
        throw new ArgumentOutOfRangeException();
    }

    return (uint)(a * short.MaxValue + b); //very good space/speed efficiency
    //or whatever your function is.
}

Если вы хотите, чтобы вывод был строго uint для неизвестного диапазона входов, тогда будет разумное количество столкновений в зависимости от этого диапазона. Я бы предложил использовать функцию, которая может переполняться, но не проверяется. Решение Emil отлично, в С#:

return unchecked((uint)((a & 0xffff) << 16 | (b & 0xffff))); 

См. Сопоставление двух целых чисел с одним, уникальным и детерминированным способом для множества опций.

Ответ 9

хеш Фибоначчи очень хорошо работает для целых пар

множитель 0x9E3779B9

другие размеры слова 1/phi = (sqrt (5) -1)/2 * 2 ^ w round to odd

a1 + a2 * множитель

это даст очень разные значения для близких пар пар

Я не знаю о результате со всеми парами

Ответ 10

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

Ответ 11

Вы можете рекурсивно разделить вашу XY-плоскость на ячейки, затем разделить эти ячейки на под-ячейки и т.д.

Густаво Нимейер изобрел в 2008 году свою геокодирующую систему Geohash.

Amazon с открытым исходным кодом Geo Library вычисляет хэш для любой долготы-широты. Полученное значение Geohash - это 63-битное число. Вероятность столкновения зависит от разрешения хеширования: если два объекта ближе, чем внутреннее разрешение, рассчитанный хеш будет идентичным.

Подробнее:

https://en.wikipedia.org/wiki/Geohash https://aws.amazon.com/fr/blogs/mobile/geo-library-for-amazon-dynamodb-part-1-table-structure/ https://github.com/awslabs/dynamodb-geo