Хэш-функция?

Даны четыре 32-битных числа. Надо из них получить одно 64-битное, причем число это должно было уникальным для каждого из наборов 4 чисел.
Схематично, так:

Код (Text):

1. hash(dword,dword,dword,dword) = qword

Есть такая функция? Если будут коллизии одна на десять тысяч - устроит.

 

ищи в интернете, много алгоритмов хеширование существует...

ЗЫ нельзя из 128 бит захешировать 64 бита, чтобы не было повторений... в данном случае, как минимум по два набора из 4 чисел будут иметь одно и тоже хеш-значение... без коллизий не бывает))))

 

CRC-64 ?
http://relf.livejournal.com/2379.html

 

ДА это понятно
А если вместо двух dword будет два byte? Т.е. hash(byte,byte,dword,dword) = qword

 

блин... если ты хочешь, чтобы вообще не было коллизий, то выбирай аргументы, чтобы сумма их разрядности совпадала с разрядностью результата... то есть byte + byte + dword + dword = 80 вроде))) а не 64... но если так делать, то это уже не хеширование, а кодирование получается))) просто взять какую-нить одностороннюю функцию и шпарить её)))

 

Rel

По 2^64 наборов из 4 чисел при равномерном распределении хэшей, если быть точным.

 

Хорошо. Хэш-функций полно и реализаций CRC64 тоже. Подскажите, что что из них лучше подходит для моих целей? Критично по скорости вычисления.

 

Если dword'ы равнозначны, то может подойти и обычный xor .

 

Что есть "равнозначны"?

 

наверное имелось ввиду по количеству байт в одном дворде

 

А что, в двордах может быть разное количество байт?! Я всегда считал, что 1 dword = 4 bytes :lol:

 

Relic
тссс, это было не тебе адресовано

 

Имелось в виду, что функции распределения вероятностей появления значений в каждом dword'е являются равномерными.

 

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

 

Если ты делаешь "быстрое сравнение", то в твоём случае лучше всего сравнивать 1й dword без всяких хешей, если совпало тогда следующий и т.д. - в 99,9(9)% случаев всё решит первое сравнение и остальные не потребуются, а если ты делаешь какой-то мегаизврат, то разьясняй толком, что за цели )

 

ну да... я просто по кривому сказал)))

мда... как я в институте ненавидел статистику... а её нам все пять лет преподавали(((((
можно и ещё проще сказать: если все значение, которые может принимать dword, равновероятны))))

а что за задача то? для чего это нужно?

 

Что-то типа создания индекса для четырех значений.
Уточняю диапазон входящих параметров для функции GetUniquеInt64(a,b,c,d):
a = 1..24
b = 0..3
c = 0..8388607
d = 0..8388607
Это как-то поможет в нахождении нужного алгоритма?

 

a, b вносишь без изменений младшими битами, c d xor'ишь и вносишь старшими битами.
Получается такая штука:
биты 0-1 - b
биты 2-25 - c xor d
биты 25-30 - a-1

Вполне нормальное хэш-значение, на мой взгляд.

 

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

 

SadKo - спасибо, попробую.
А теперь вопрос знатокам комбинаторики
Какое количество комбинаций abcd можно составить при
a = 1..24
b = 0..3
c = 0..8388607
d = 0..8388607
?