VPF::Хэш функция - Форум программистов

ts_

Дата 16.1.2007, 23:47 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 39
Регистрация: 6.10.2006

Репутация: нет
Всего: нет

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

Код


#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 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 53
Всего: 183

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

--------------------

...

ts_

Дата 18.1.2007, 02:49 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 39
Регистрация: 6.10.2006

Репутация: нет
Всего: нет

Код


#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 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 53
Всего: 183

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

--------------------

...

ts_

Дата 18.1.2007, 23:25 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 39
Регистрация: 6.10.2006

Репутация: нет
Всего: нет

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

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »