требуется 32битная хэш-функция для строк

Тема в разделе "WASM.A&O", создана пользователем jabocrack, 25 янв 2011.

  1. jabocrack

    jabocrack New Member

    Публикаций:
    0
    Регистрация:
    27 мар 2010
    Сообщения:
    96
    F(const char *) -> unsigned int32_t.
    главное - минимум коллизий( при количестве обрабатываемых строк от 100 000 и при их длине от 2 до 64 символов) , ну а уже потом быстродействие алгоритма.
     
  2. Atlantic

    Atlantic Member

    Публикаций:
    0
    Регистрация:
    22 июн 2005
    Сообщения:
    322
    Адрес:
    Швеция
    Код (Text):
    1. uint32_t fnv32( const void *buf, size_t len )
    2. {
    3.   const unsigned char *data = (const unsigned char *)(buf);
    4.   uint32_t crc = 2166136261UL;
    5.   while ( len-- )
    6.     crc = ( crc * 16777619 ) ^ ( *data++ );
    7.   return crc;
    8. }
    Подробнее тут: http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
     
  3. jabocrack

    jabocrack New Member

    Публикаций:
    0
    Регистрация:
    27 мар 2010
    Сообщения:
    96
    Ага. спасибо.
     
  4. Proteus

    Proteus Member

    Публикаций:
    0
    Регистрация:
    19 июн 2004
    Сообщения:
    344
    Адрес:
    Russia
    вот такая штука одной из лучших считается.
    Код (Text):
    1. pow=1,hash=0
    2. for(i=0; i<s.len(); ++i)
    3. {
    4.     hash+= s[i]*pow;
    5.     pow *= p;
    6. }
    7. return hash;
     
  5. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Proteus
    pow, p_pow, p, has, hash. Откуда вы это взяли?
     
  6. Proteus

    Proteus Member

    Публикаций:
    0
    Регистрация:
    19 июн 2004
    Сообщения:
    344
    Адрес:
    Russia
    опечатки... поправил... хотя там и так догадаться можно, как полином такой считать...
    P число простое, можно небольшое брать двух-значное...

    p.s.
    можно так и воообще просто crc32 делать для строки, чем не идеальная сумма.. будет таблица в памяти на 256 чисел, а так код даже проще станет.. по крайней мере быстрее...
    без таблицы даже можно так сделать, тоже на глазз набираю:
    Код (Text):
    1. dword CRC(const char *txt)
    2. {
    3.     dword hash=(dword)-1;
    4.     while(*txt) {
    5.         hash^=*txt++;
    6.         for(n=0;n<8;n++) hash=(-(hash&1)&0xDB710641)^(hash>>1);
    7.     }
    8.  return hash;
    9. }
     
  7. jabocrack

    jabocrack New Member

    Публикаций:
    0
    Регистрация:
    27 мар 2010
    Сообщения:
    96
    Proteus

    это вроде у тя FNV-1a hash.
    Я пришел к выводу, что для надежности нужно пройтись 2 вариантами хеш функции по строке:
    FNV-1
    Код (Text):
    1. hash = FNV_offset_basis
    2.    for each octet_of_data to be hashed
    3.     hash = hash * FNV_prime
    4.     hash = hash XOR octet_of_data
    5.    return hash
    FNV-1a
    Код (Text):
    1. hash = FNV_offset_basis
    2.    for each octet_of_data to be hashed
    3.     hash = hash XOR octet_of_data
    4.     hash = hash * FNV_prime
    5.    return hash
     
  8. jabocrack

    jabocrack New Member

    Публикаций:
    0
    Регистрация:
    27 мар 2010
    Сообщения:
    96
    Кстати вдогонку, позволяет ли openmp распараллелить эти 2 алго на 2 ядра.
     
  9. Proteus

    Proteus Member

    Публикаций:
    0
    Регистрация:
    19 июн 2004
    Сообщения:
    344
    Адрес:
    Russia
    хз =)
    Позволяет. crc32 никак не распаралелишь. Чётные не чётные байты можно отельно во всех слуячаях считать, потом сшить результат. Можно отрезки побольше складывать, тут никаких сложностей не видно. Только толку тоже не заметно, такие простые операции ускорять... даже если будешь строки по 10 метров кидать, всё равно непонятно зачем (либо больше кеш промахиваться будет либо ещё что-то).. Проще разные строки на разных ядрах считать...
     
  10. jabocrack

    jabocrack New Member

    Публикаций:
    0
    Регистрация:
    27 мар 2010
    Сообщения:
    96
    1 ядро - FNV-1 2 ядро - FNV-1a. При чтении строки они будут мешать друг другу? Как то слабо представляю этот момент.
     
  11. ivan2k2

    ivan2k2 New Member

    Публикаций:
    0
    Регистрация:
    28 янв 2006
    Сообщения:
    95
    здесь куча хэш-функций с исходниками и тестами http://amsoftware.narod.ru/algo.html
     
  12. gazlan

    gazlan Member

    Публикаций:
    0
    Регистрация:
    22 май 2005
    Сообщения:
    414
    h**p://w*w.azillionmonkeys.com/qed/hash.html
     
  13. jabocrack

    jabocrack New Member

    Публикаций:
    0
    Регистрация:
    27 мар 2010
    Сообщения:
    96
    Мда. Побегал я по ссылкам. Получается, Fnv совсем не айс по сравнению с crc32.
    Кол-во коллизий у crc32 на всех тестах ровно, как и у хеш-функций автора кстати.
    А вот fnv1 и fnv1a впадают в маразм при длинных строках тесты E и F. По видимому, изза инструкции умножения качество хеша постепенно падает.
    По скорости Crc32 уступает, но ненамного. То есть, fnv1a fnv-1 можно смело выкидывать и использовать crc32.
     
  14. Proteus

    Proteus Member

    Публикаций:
    0
    Регистрация:
    19 июн 2004
    Сообщения:
    344
    Адрес:
    Russia
    Код (Text):
    1. class CRC32 {
    2.     dword table[256];
    3. public:
    4.     CRC32(dword polynom=0xDB710641); // 0xEDB88320 0x04C11DB7 0x1EDC6F41
    5.     dword Calc(char*);
    6. };
    7.  
    8. CRC32::CRC32(dword polynom) // Init - один раз на всю программу
    9. {
    10.     for(int n=0;n<256;n++) {
    11.         dword c=n;
    12.         for(int k=0;k<8;k++) c=c>>1^(-(int)(c&1)&polynom);
    13.         table[n]=c;
    14.     }
    15. }
    16.  
    17. dword CRC32::Calc(char *str)
    18. {
    19.     dword hash=(dword)-1;
    20.     while(*str) hash=(hash>>8)^table[(char)hash^*str++];
    21.     return hash;
    22. }
    скорость проверять вообще не имеет смысла...=)
     
  15. jabocrack

    jabocrack New Member

    Публикаций:
    0
    Регистрация:
    27 мар 2010
    Сообщения:
    96
    В FNv применяется умножение. Так что их можно сравнивать.
    В CRC нет умножения но зато используется таблица(задействуется ОЗУ).
     
  16. eshkinkot

    eshkinkot New Member

    Публикаций:
    0
    Регистрация:
    6 май 2010
    Сообщения:
    73
    а как эти алгоритмы представить в виде макроса FASM?
     
  17. edemko

    edemko New Member

    Публикаций:
    0
    Регистрация:
    25 ноя 2009
    Сообщения:
    454
    как устроен fnv?
     
  18. DEEP

    DEEP Андрей

    Публикаций:
    0
    Регистрация:
    27 апр 2008
    Сообщения:
    491
    Адрес:
    г. Владимир
    Охтыж! Как раз такую функцию искал.
    edemko, благодарю что подняли тему =)
     
  19. Person

    Person Hugh Person

    Публикаций:
    0
    Регистрация:
    29 июн 2011
    Сообщения:
    23
    RtlHashString
     
  20. scf

    scf Member

    Публикаций:
    0
    Регистрация:
    12 сен 2005
    Сообщения:
    385
    Можно предположить, что существующие криптохеши дают минимальные коллизии