Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Хэш функция

Автор: ts_ 16.1.2007, 23:47

В следущей хэш функции из "Страуструпа" не понмиаю как находиться индекс массива:

Код


#include <string.h>
name* look(const char* p, int ins =0) {
   int ii = 0; // хэш-код
   const char* pp = p;
   while (*pp) ii = ii<<1 ^ *pp++;  //  <--  ЗДЕСЬ
   if (ii < 0) ii = -ii;
   ii %= TBLSZ;
   for (name* n=table[ii]; n; n=n->next) // поиск
   if (strcmp(p,n->string) == 0) return n;
   if (ins == 0) error("имя не найдено");
   name* nn = new name; // занесение 
   nn->string = new char[strlen(p)+1];
   strcpy(nn->string,p);
   nn->value = 1;
   nn->next = table[ii];
   table[ii] = nn;
   return nn;
}

а именно не понимаю что возвращаеться в строке "ii<<1 ^ *pp++", что возвращает поразрядная операция исключающего ИЛИ ^? Кто это знает подскажите пожайлуста

Автор: Earnest 17.1.2007, 08:50

Исключающее ИЛИ, как обычно возвращает 1 для комбинации 0 и 1, и 0 в других случаях. А что же еще?
У тебя вычисляется хэш-индекс для строки. Текущее значение сдвигаем и "складываем" операцией XOR со следующим символом.
Смысл в том, чтобы "разбросать" хранимые значения так, чтобы разные значение с малой вероятностью давали одинаковый хэш (т.е. чтобы списки в элементах table) были короткими, желательно не более 1. Этот алгоритм не единственный.

Автор: ts_ 18.1.2007, 02:49

Код


#include <stdio.h>
void main() {
   char* pp = "ab";
   int ii = 0; 
   while (*pp) ii = ii<<1 ^ *pp++;
   printf("%c%i",'\n',ii);
}

Спасибо Earnest, частично понял, не понял как определяеться код для следуещего символа после первого, если ввести один символ, возвращает ANSI код символа, если например "ab" -- выдает 160, поему выходит такой результат объясните пожайлуста?

Автор: Earnest 18.1.2007, 10:24

Пардон, невнимательно посмотрела: в формуле используется код текущего символа, а не следующего (*pp++). С одним символом все ясно: 0 XOR [нечто] == [нечто]. На втором шаге это [нечто] сдвигается и ксорится со следующим символом. Почему получается 160 - ну посмотри по битам сам.

Автор: ts_ 18.1.2007, 23:25

Теперь все понял, еще раз спасибо, тема закрыта.