Полиномиальное хеширование против Cycli c Полиномиальный сдвиг для строк - PullRequest
Новая
       99

Полиномиальное хеширование против Cycli c Полиномиальный сдвиг для строк

1 голос
/ 14 июля 2020

Я использую эту функцию для cycli c shift: 

int hashcyclic(char *p, int len)
{
   unsigned int h = 0;
   int i;
   for (i = 0; i < len; i++)
   {
      h = (h << 5) | (h >> 27);
      h += (unsigned int)p[i];
   }
   return h%TABLESIZE;
}

В текстовом файле с примерно 20K строками (одно слово / строка) общее количество коллизий составляет 45187. В текстовом файле с 40К + строк (опять же, одно слово / строка) - 12922252 (!) Коллизии с тем же алгоритмом.

При полиномиальном хешировании: 

int hashpoly(char *K)
{
   int h = 0, a = 33;
   for (; *K != '\0'; K++)
      h = (a * h + *K) % TABLESIZE;
   return h;
}

Теперь я получаю около 25К коллизий на файл 20K слов и 901K коллизий в файле слов 40K (почти в 12 раз меньше, чем cycli c shift).

Мой вопрос: имеет ли это смысл или одна из моих реализаций испортилась? Я ожидал, что cycli c будет самым быстрым для моих строк (файл слов 40K представляет собой серию слов из 8 букв, разделенных символом новой строки), но полиномиальные столкновения значительно реже. 

int HashInsertPoly(Table T, KeyType K, InfoType I)
{
   int i;
   int ProbeDecrement;
   i = hashpoly(K);
   ProbeDecrement = p(K);

   while (T[i].Key[0] != EmptyKey)
   {
      totalcol++;
      T[i].Info.col++;
      i -= ProbeDecrement;
      if (i < 0)
         i += TABLESIZE;
   }

   strcpy(T[i].Key, K);
   insertions++;

   /*T[i].Info = I;*/

   return i;
}

Та же функция HashInsert применяется к ha sh с cycli c shift, за исключением того, что теперь я вызываю hashcycli c вместо hashpoly

1 Ответ

0 голосов
/ 15 июля 2020

Я догадываюсь, что разброс слов обычного текста невелик, и поэтому cycli c ha sh недостаточно chaoti c.

Давайте посмотрим на две строки " cat "и" dog ". 

cat 

c 01100011
a 01100001
t 01110100

h starts at 
00000000 00000000 00000000 01100011 (c)
and is then cycled to 
00000000 00000000 00001100 01100000
then we add `a` to get
  00000000 00000000 00001100 01100000
+                            01100001
= 00000000 00000000 00001100 11000001
which is then cycled to
00000000 00000001 10011000 00100000
then we add `t` to get 
  00000000 00000001 10011000 00100000
+                            01110100
= 00000000 00000001 10011000 10010100
we then return this number mod 41893 for 20810

Similarly, for dog

d 01100100
o 01101111
g 01100111

start: 
00000000 00000000 00000000 01100100 (d)
cycled and added o:
00000000 00000000 00001100 11101111
cycled and added t:
00000000 00000001 10011110 01000111
ends up at 22269

Поскольку диапазон ASCII невелик, а алгоритм цикла использует все пространство беззнакового int, для того, чтобы действительно pu sh the ha * 1017, использовались длинные строки. * в совершенно другое пространство. Особенно последний символ, который действительно доминирует в окончательной операции модуля.

Другой способ взглянуть на это: очень мало взаимодействия с 7-битным символом ASCII и предыдущим 7-битным символом ASCII после сдвига 5 удалите эти биты и замените их нулями, особенно для более коротких слов.

Поскольку полином ha sh использует только размер таблицы, он chaoti c «быстрее», даже для меньших строк. Ему не нужно заполнять целое int, прежде чем оно станет действительно chaoti c. Один символ ASCII намного больше размера таблицы.

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

...