Конференция "Прочее" » Хеширование
 
  • xayam © (18.03.19 19:54) [0]
    какой алгоритм хеширования лучше использовать чтобы не было коллизий?
    для английских и русских слов.
    То есть во входной строке только одно такое слово,
    на выходе 32 шестнадцатеричные цифры или меньше...
  • asail © (18.03.19 20:29) [1]
    Если всего одно слово надо хешировать, то зачем его вообще хешировать, а не хранить as is? На размерах особо не сэкономишь, ибо средний размер слова вряд ли будет превышать эти самые 64 байта, а коллизий вообще не будет ни каких...
    Или я чего-то не понимаю?
  • xayam © (18.03.19 20:46) [2]

    > Если всего одно слово надо хешировать,

    не ну английских и русских слов много
    но на входе функции только одно слово
  • Dimka Maslov © (18.03.19 20:54) [3]

    >  то зачем его вообще хешировать, а не хранить as is


    Сам пришёл к такому же выводу давным давно.
  • xayam © (18.03.19 21:15) [4]

    > Сам пришёл к такому же выводу давным давно

    у хеша есть одно хорошое свойство - он имеет одинаковую длину
    в отличии от слов
  • Sha © (18.03.19 21:18) [5]
    Выбор очевиден: ShaPerfectHash отсюда :)

    http://www.guildalfa.ru/alsha/node/32
  • xayam © (18.03.19 22:06) [6]

    > Sha ©   (18.03.19 21:18) [5]
    > Выбор очевиден: ShaPerfectHash отсюда

    так это действительно так или нет? :)
  • Sha © (18.03.19 22:34) [7]
    Сфера применения не описана.
    Если нужно точно 128 бит, то проще всего взять MD5,
    или можно SHA256 обрезать,
    или можно несколько разных 4-байтовых скомбинировать.
  • Styx © (19.03.19 00:57) [8]

    > у хеша есть одно хорошое свойство - он имеет одинаковую длину
    > в отличии от слов

    Короткие слова добивать нулями, а от длинных считать хэш...
  • иосифович © (19.03.19 09:59) [9]
    у хеша есть одно хорошое свойство - он имеет одинаковую длину
    в отличии от слов


    у слова есть одно хорошее свойство - его можно прочитать.
    а еще большинство слов  и все слова этой ветки короче своих хеш-функций.
  • Dimka Maslov © (19.03.19 10:38) [10]

    > то проще всего взять MD5


    Для md5 слишком часто случаются коллизии. Чаще, чем можно ожидать. Когда давно я делал список с поиском по md5. Ничем хорошим это не кончилось. Ну, а кроме того, функция простого посимвольного сравнения строк сразу прерывается, как только обнаружит, что строки не равны. Поэтому в С++ я всегда пользуюсь std::map<std::wstring, ...> и не парюсь.
  • Sha © (19.03.19 11:12) [11]
    > Когда давно я делал список с поиском по md5.

    список или хеш-таблицу?
  • KSergey © (19.03.19 11:36) [12]
    > xayam ©   (18.03.19 21:15) [4]
    > у хеша есть одно хорошое свойство - он имеет одинаковую длину

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

    Правда что делать со словами более 16 букв - вопрос, но тут и любой хеш даст коллизии по определению.
  • KSergey © (19.03.19 11:37) [13]
    > asail ©   (18.03.19 20:29) [1]
    >  ибо средний размер слова вряд ли будет превышать эти самые 64 байта,

    32 шестнадцатеричные цифры - это вроде 16 байт же?
  • Dimka Maslov © (19.03.19 15:45) [14]

    > список или хеш-таблицу?


    Сейчас уже это не важно. Главное, что часто были коллизии.
  • asail © (19.03.19 16:24) [15]

    > 32 шестнадцатеричные цифры - это вроде 16 байт же?

    Конечно. Башка моя старая - плохо соображает уже... :)
  • Sha © (20.03.19 00:20) [16]
    >> список или хеш-таблицу?
    > Сейчас уже это не важно. Главное, что часто были коллизии.

    для хеш-таблицы коллизии - это штатно и не должно быть проблемой
  • xayam © (20.03.19 01:33) [17]

    > это штатно и не должно быть проблемой

    и как решается эта проблема?
  • Sha © (20.03.19 10:43) [18]
    > и как решается эта проблема?

    текст по приведенной ссылке читал?
  • Mystic © (20.03.19 13:01) [19]
    Самый быстрые — третий мур-мур. Но не он не криптографический.
  • Mystic © (20.03.19 13:11) [20]

    > и как решается эта проблема?


    Дальше поиск по массиву на точное соотвествие, если коллизия. Вообще, вероятность колизии вычисляется приближённо как exp(-k(k-1)/(2*N)), так что можно подобрать значение N таким образом, чтобы k слов из словаря имели минимальную вероятсноть + память.
Есть новые Нет новых   [99016   +12][b:0.001][p:0.002]