IPB
ЛогинПароль:

> ВНИМАНИЕ!

Прежде чем задать вопрос, смотрите FAQ.
Рекомендуем загрузить DRKB.

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> Хэширование PJW-32, некорректно работает
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 37
Пол: Мужской
Реальное имя: Серёга

Репутация: -  0  +


Алгоритм hashpjw

В изначальном варианте, алгоритм был адаптирован на работу с хеш-таблицами, то есть на начальной стадии имелось сообщение s произвольной длины L, от которого требовалось найти хеш значение h. Перед вычислением значение h устанавливается в 0. Сообщение считывается посимвольно. Число m — предполагаемый размер таблицы.

Шаг 1
Каждый считанный символ с сообщения s переводится в число, а затем рассматривается его битовое значение. Преобразование отдельного символа в целое число обычно поддерживается языками программирования. Например, Pascal предоставляет для этого функцию ord, а С автоматически преобразовывает символ в целое число при выполнении арифметических операций.
Для полученного значения с производится сдвиг h на 4 позиции влево и суммирование с с.

Шаг 2
Производится проверка: если любой из 4 старших битов h равен 1 то сдвигаем их вправо на 24 позиции. Затем выполняем операцию исключающего или со значением h и сбрасываем значения 4 старших битов в 0.

Шаг 3
После проведения шагов 1-2 со всеми символами сообщения s, производится деление h по модулю m. Полученное число — это номер списка в таблице, к которому следует присоединить данную строку.

Код
procedure TForm1.Button1Click(Sender: TObject);
var str:string;
i,h,g:integer;
begin
  h:=0;
  g:=0;
  str:=edit1.text;
  for i:=1 to length(str) do
  begin
    h:=(h shl 4)+ord(i);
   { if g=(h and $00000000) then  }
    if $00001111 <> (h or $00001111) then
      h:= h xor (g shr 24);
      h:=h xor g;
      h:=h and $00001111;
  end;
  h:=h mod 211;
  edit2.text:=inttostr(h);
end;


Вроде как и работает, но по-моему как-то не так ... С битами работаю первый раз, может наврал где ...
Тестовый пример указан a(англ раскладка) - 97, а у меня для а хэш-функция получается равной 1...
Помогите пожалуйста разобраться.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






А почему ты делаешь
Цитата
    h:=(h shl 4)+ord(i);

, а не
    h:=(h shl 4)+ord(str[ i ]);
? Работаешь же со строкой, а у тебя str и не используется нигде...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






Так... Тут у тебя еще есть ошибки... Смотри:

procedure TForm1.Button1Click(Sender: TObject);
var
str: string;
i: integer;

h, g: LongWord; // Работаем с беззнаковыми числами. Размер = 32 бита
begin
h := $0;

str := Edit1.Text;
for i := 1 to Length(str) do
begin
// Для полученного значения с производится сдвиг
// h на 4 позиции влево и суммирование с с.
h := (h shl 4) or Ord(str[i]);

g := h and $F0000000;
// 4 старших бита G совпадают с 4-мя старшими битами H,
// остальные биты G = нулю

// Производится проверка: если любой из 4 старших битов h равен 1 ...
if g <> 0 then
begin
h := h xor (g shr 24); // ... то сдвигаем их вправо на 24 позиции.
h := h xor g; // Затем выполняем операцию исключающего или со значением h

// операции сброса 4-х старших битов не видел ни в одной реализации...
// Поэтому не буду его делать и здесь
end;
end;

// После проведения шагов 1-2 со всеми символами сообщения s,
// производится деление h по модулю m
h := h mod 211;
Edit2.Text := IntToStr(h);
end;
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Новичок
*

Группа: Пользователи
Сообщений: 37
Пол: Мужской
Реальное имя: Серёга

Репутация: -  0  +


Спасибо большое! Теперь работает корректно, буду разбираться.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 23.10.2020 7:01
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name