хеш-функция, обеспечивающая уникальный uint от целочисленной координатной пары
Установка tail = tail->next устанавливает tail в null, потому что он не устанавливается в первый раз, а затем и tail, и head сразу же перезаписываются при следующем вызове.
6 ответов
хеш-функция, которая ГАРАНТИРУЕТСЯ без коллизий, не является хеш-функцией :)
Вместо того, чтобы использовать хеш-функцию, Вы могли рассмотреть использование двоичных деревьев раздела пространства (BSPs) или (тесно связанных) XY-деревьев.
Если Вы хотите хешировать два uint32 в один uint32, не используйте вещи как Y и 0xFFFF, потому что это отбрасывает половину битов. Сделайте что-то как
(x * 0x1f1f1f1f) ^ y
(необходимо преобразовать одну из переменных сначала, чтобы удостовериться, что хеш-функция не является коммутативной),
Перечисление Кантором пар
n = ((x + y)*(x + y + 1)/2) + y
могло бы быть интересным, поскольку это является самым близким к Вашему исходному canvaswidth * y + x, но будет работать на любой x или y. Но для реального мира int32 хеш, а не отображение пар целых чисел к целым числам, Вы, вероятно, более обеспечены с небольшим управлением, таким как соединение и вызов Bob Jenkin это с x, y и солью.
Как Emil, но дескрипторы 16-разрядное переполнение в x способом это производит меньше коллизий и берет меньше инструкций вычислить:
hash = ( y << 16 ) ^ x;
Ваш "идеал" невозможен.
Вы хотите отображение (x, y)-> я, где x, y, и я - все 32-разрядные количества, который, как гарантируют, не генерирует дублирующиеся значения меня.
Вот то, почему: предположите, что существует функциональный хеш () так, чтобы хеш (x, y) дал различные целочисленные значения. Существуют 2^32 (приблизительно 4 миллиарда) значения для x, и 2^32 значения y. Таким образом, хеш (x, y) имеет 2^64 (приблизительно 16 миллионов триллионов) возможные результаты. Но существуют только 2^32 возможные значения в 32-разрядном интервале, таким образом, результат хеша () не поместится в 32-разрядный интервал.
См. также http://en.wikipedia.org/wiki/Counting_argument
Обычно необходимо всегда разрабатывать структуры данных для контакта с коллизиями. (Если Ваши хеши не очень долго (по крайней мере 128 битов), очень хороший (используйте криптографические хеш-функции), и Вы чувствуете себя удачливыми).
Возможно?
hash = ((y & 0xFFFF) << 16) | (x & 0xFFFF);
Работы пока X и Y могут быть сохранены как целые числа на 16 битов. Никакая идея о том, сколько коллизий это вызывает для больших целых чисел, все же. Одна идея могла бы быть, чтобы все еще использовать эту схему, но объединить ее со схемой сжатия, такой как взятие модуля 2^16.
Если вы можете сделать 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;
}
. Таким образом вы получите результат случайного вида, а не старшие биты из одного измерения и младшие биты из другого.