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

Тема в разделе "WASM.BEGINNERS", создана пользователем Relic, 19 янв 2009.

  1. Relic

    Relic Member

    Публикаций:
    0
    Даны четыре 32-битных числа. Надо из них получить одно 64-битное, причем число это должно было уникальным для каждого из наборов 4 чисел.
    Схематично, так:
    Код (Text):
    1. hash(dword,dword,dword,dword) = qword
    Есть такая функция? Если будут коллизии одна на десять тысяч - устроит.
     
  2. Rel

    Rel Well-Known Member

    Публикаций:
    2
    ищи в интернете, много алгоритмов хеширование существует...

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

    drmad New Member

    Публикаций:
    0
    CRC-64 ?
    http://relf.livejournal.com/2379.html
     
  4. Relic

    Relic Member

    Публикаций:
    0
    ДА это понятно :)
    А если вместо двух dword будет два byte? Т.е. hash(byte,byte,dword,dword) = qword
     
  5. Rel

    Rel Well-Known Member

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

    l_inc New Member

    Публикаций:
    0
    Rel
    По 2^64 наборов из 4 чисел при равномерном распределении хэшей, если быть точным.
     
  7. Relic

    Relic Member

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

    SadKo Владимир Садовников

    Публикаций:
    8
    Если dword'ы равнозначны, то может подойти и обычный xor :).
     
  9. Relic

    Relic Member

    Публикаций:
    0
    Что есть "равнозначны"?
     
  10. MSoft

    MSoft New Member

    Публикаций:
    0
    наверное имелось ввиду по количеству байт в одном дворде
     
  11. Relic

    Relic Member

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

    MSoft New Member

    Публикаций:
    0
    Relic
    тссс, это было не тебе адресовано :)
     
  13. SadKo

    SadKo Владимир Садовников

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

    _basmp_ New Member

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

    Y_Mur Active Member

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

    Rel Well-Known Member

    Публикаций:
    2
    ну да... я просто по кривому сказал)))

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

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

    Relic Member

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

    SadKo Владимир Садовников

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

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

    SadKo Владимир Садовников

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

    Relic Member

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