0

Для хеширования строк.

4
  • варианты можно предлагать в зависимости от нужного уровня безопасности: 1. защищаемся от школьников 2. защищаемся от любителей 3. защищаемся от профи
    – jmu
    2 апр 2012 в 11:14
  • Мы не защищаемся, мы ищем:)
    – PaulD
    2 апр 2012 в 13:39
  • ну ищете вы для какой-то цели или просто так? вопрос ведь тоже задаете с целью получить ответ, или просто так?
    – jmu
    2 апр 2012 в 13:53
  • ищу с целью получения денег, как это ни странно :)
    – PaulD
    2 апр 2012 в 14:02

3 ответа 3

3

Недавно отвечал.

Перенесено из комментария.

@pol500, боюсь, Вы что-то недопонимаете в хэшировании. Объем хэшированного словаря всегда больше исходного.

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

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

Насколько мне известно, на практике так никогда не поступают.

UPD 2

Простая программка проверки хэшкода для русских (думаю любых) слов.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// try hash h = h * 31 +str[i]

int
hash (char *s)
{
  int h = 0;
  while (*s) 
    h = h*31+*s++;
  return h;
}

main ()
{
  // make dictionary
  unsigned char str[10000];
  FILE *dict = fopen("dict","w");
  int  nwi = 0, nwo = 0;

  while (scanf("%s",str) == 1) {
    nwi++;
    if (str[0] >= 'A') {
      nwo++;
      fprintf (dict,"%s\n",str);
    }
  }
  fclose(dict);
  printf ("raw dict %d of %d\n",nwo,nwi);
  dict = popen("sort -u dict","r");
  FILE *hf = fopen("hashcodes","w");
  int nwu = 0;
  while (fscanf(dict,"%s",str) == 1) {
    nwu++;
    fprintf (hf,"%d\n", hash(str));
  }
  pclose(dict);
  fclose(hf);
  printf ("%d unic words\nunic hashcodes ",nwu); fflush(stdout);
  system ("sort -u hashcodes | wc -w");
}
4
  • да, я помню, и именно по вашему совету я и реализовал свою хеш-функцию. но она не подошла - словарь генерируется почти из всего объема словаря, хотя предыдущая версия моей программы генерила выходные словари процентов на 50 меньшие. Видать то ли хэши повторяются, то ли еще что.
    – PaulD
    2 апр 2012 в 5:18
  • Перенесено в ответ.
    – avp
    2 апр 2012 в 7:56
  • Кстати, та функция, что вы советовали ранее, генерирует только 403 уникальных ключа на диапазоне из 9970 слов
    – PaulD
    2 апр 2012 в 17:16
  • @pol500, Вы меня просто заинтриговали. Написал программку, проверил на "Космической Одиссеи" (первое, что попалось с русскими буквами) avp@avp-ubu1:~/hashcode$ ./a.out <sp raw dict 52370 of 53838 19288 unic words unic hashcodes 19282 avp@avp-ubu1:~/hashcode$ Кладу ее (программку) в UPD 2. Проверьте у себя и отпишите, пожалуйста, о результате.
    – avp
    2 апр 2012 в 19:24
1

Рекомендую хэш функцию Whirlpool. Хорош тем, что во первых он принадлежит семейству SHA-2 и рекомендован NIST, во вторых алгоритм находится в public domain, в третьих есть сишные (и Java) исходники, ну и в оконцове не так заезжен как MD5 иже с ними.

4
  • Это же криптографический хэш...
    – karmadro4
    2 апр 2012 в 8:42
  • Ну да, а камрад не указал чего он хотел то...
    – Barmaley
    2 апр 2012 в 10:25
  • Ему надо быстро искать русские слова в словаре. Тут раньше было обсуждение его проблемы.
    – avp
    2 апр 2012 в 12:13
  • Я думаю, что а) это приступ предварительной оптимизации б) пора уже писать кот в) Jenkins is fine too и г) при корпусе в 15к слов результат от изысканий самого-самого алгоритма будет ничтожно мал.
    – karmadro4
    2 апр 2012 в 19:08
0

В 2015 году это xxHash, есть реализации на всех популярных языках.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.