хеш-функция, обеспечивающая уникальную UINT из пары целочисленных координат

Question

Проблема в целом: У меня есть большое 2-х точечное пространство, редко заполненное точками. Думайте об этом как о большом белом холсте, посыпанном черными точками. Мне приходится многократно повторять и искать по этим точкам. Холст (точка пространства) может быть огромным, граничащим с границами из int и его размер неизвестен до установки там точек.

Это привело меня к идее хеширования:

Ideal: Мне нужна хеш-функция, берущая 2D-точку и возвращающая уникальный uint32. Так что никаких столкновений не может произойти. Можно предположить, что число точки на холсте легко подсчитываются с помощью uint32.

ВАЖНО: Невозможно заранее узнать размер холста (это может даже измениться), так что вроде

Ширина холста * у + х

печально не может быть и речи.

Я тоже очень наивно пробовал

абс (х) + абс (у)

но это вызывает слишком много столкновений.

Компромисс: Хеш-функция, которая обеспечивает ключи с очень низкой вероятностью столкновения.

Есть идеи у кого-нибудь? Спасибо за любую помощь.

С уважением, Андреас Т.

Edit: Мне пришлось что-то изменить в тексте вопроса: Я изменил предположение «умеет считать количество точек холста» с помощью uint32 «в» можно посчитать точки на холсте (или количество координатных пар для хранения »с помощью uint32. Мой оригинальный вопрос не имел особого смысла, потому что у меня был бы холст размером sqrt (max (uint32)) xsqrt (max (uint32)), который уникально представлен сдвигом 16 бит и ИЛИ.

Надеюсь, это нормально, поскольку все ответы по-прежнему имеют смысл с обновленными предположениями

Извините за это.

Answer 1

Кантор перечисление пар

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

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

Answer 2

ГАРАНТИРУЕМЫЕ хеш-функции без столкновений не являются хеш-функциями:)

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

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

(x * 0x1f1f1f1f) ^ y

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

Answer 3

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

hash = ( y << 16 ) ^ x;

Answer 4

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

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

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

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

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

Answer 5

Вы можете рекурсивно разделить вашу плоскость 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

Answer 6

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

Answer 7

Если вы можете сделать a = ((y & 0xffff) << 16) | (x & 0xffff), затем вы можете применить обратимое 32-битное микширование к a, например, </p> Томаса Вана

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;
}

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

Answer 8

Возможно

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

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

Answer 9

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

множитель 0x9E3779B9

другие размеры слова 1 / phi = (sqrt (5) -1) / 2 * 2 ^ w округление до нечетного

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

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

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

Answer 10

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

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 для неизвестного диапазона входных данных, тогда будет разумное количество коллизий в зависимости от этого диапазона. Я хотел бы предложить функцию, которая может переполняться, но не проверена . Решение Эмиля великолепно, в C #:

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

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