Помощь - Поиск - Пользователи - Календарь
Полная версия: Хэширование PJW-32
Форум «Всё о Паскале» > Современный Паскаль и другие языки > Делфи
SeregaR1Val
Алгоритм 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...
Помогите пожалуйста разобраться.
volvo
А почему ты делаешь
Цитата
    h:=(h shl 4)+ord(i);

, а не
    h:=(h shl 4)+ord(str[ i ]);
? Работаешь же со строкой, а у тебя str и не используется нигде...
volvo
Так... Тут у тебя еще есть ошибки... Смотри:

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;
SeregaR1Val
Спасибо большое! Теперь работает корректно, буду разбираться.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.