Основные операции с хешированием данных

Формулировка задания

Используя метод хеширования с открытой адресацией, написать программу поиска записи по первых трем буквам фамилии.

Указания: в качестве хэш-функции использовать:

- сумму кодов символов по модулю m

В качестве метода адресации использовать:

- линейный метод.

Основные операции с хешированием данных

1) Линейный метод хеш–функции

Алгоритм:

- Обнуляем число коллизий;

- Для i от 1 до n;

а) Строке str присваиваем фамилию i-го человека;

б) Присваиваем число шагов для хеш-функции 0 (j:=0);

в) Переменной а присваиваем значение хеш-функции от первых трех букв фамилии + количество шагов хеш-функции умноженную на константу С;

г) Если в ячейке с номером а свободно, пишем туда значение i, выходим из цикла;

д) Иначе, увеличиваем шаг и число коллизий на единицу;

collisions:=0;{ обнуляем число коллизий}

for i:=1 to n do{ Для i от 1 до n}

begin

str:=persons[i].name;{ присваиваем фамилию i-го человека}

j:=0;{ присваиваем число шагов для хеш-функции}

while (true) do

begin

a:=h1(str[1],str[2],str[3])+j*c;{ присваиваем значение хеш-функции от первых трех букв фамилии + количество шагов хеш-функции умноженную на константу С}

if t[a]=0 then{ если в ячейке с номером а свободно}

begin

t[a]:=i;{ пишем значение i}

break;{выходим из цикла}

end

else

begin

j:=j+1;

inc(collisions);{ увеличиваем шаг и число коллизий на единицу}

end;

end;

end;

end;

Функция поиска

Алгоритм:

а) Количество шагов хеш-функции приравниваем 0;

б) присваиваем h значение хеш - функции от первых трех букв фамилии + количество шагов хеш-фукнции умноженную на константу С;

в) если в ячейке таблицы с номером h ничего нет, то такого человека в базе нет;

г) Иначе, пока не найдем;

д) присваиваем h значение хеш-функции от первых трех букв фамилии + количество шагов хеш-фукнции умноженную на константу C;

е) Если первые три буквы фамилии человека, чей номер записан в ячейке таблицы с номером h, совпадают с первыми тремя буквами введенной фамилии, выводим его фамилию и номер телефона;

ж) Увеличиваем количество шагов;

j:=0;{ количество шагов хеш-функции приравниваем 0}

h:=h1(s[1],s[2],s[3])+j*c;{ присваиваем h значение хеш - функции от первых трех букв фамилии + количество шагов хеш-фукнции умноженную на константу С}

if t[h]=0 then writeln('такого нет'){ если в ячейке таблицы с номером h ничего нет, то такого человека в базе нет}

else

while (j<max) do{ пока не найдем}

begin

h:=h1(s[1],s[2],s[3])+j*c;{ присваиваем h значение хеш-функции от первых трех букв фамилии + количество шагов хеш-фукнции умноженную на константу C}

if ((persons[t[h]].name[1]=s[1]) and (persons[t[h]].name[2]=s[2]) and (persons[t[h]].name[3]=s[3])) then{ если первые три буквы фамилии человека, чей номер записан в ячейке таблицы с номером h, совпадают с первыми тремя буквами введенной фамилии, выводим его фамилию и номер телефона}

begin

writeln(persons[t[h]].name, ' ', persons[t[h]].number);

end;

j:=j+1;{ увеличиваем количество шагов}

end;

Не нашли, что искали? Воспользуйтесь поиском: