Помощь - Поиск - Пользователи - Календарь
Полная версия: Хеш-таблица
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Fellout
Дано задание : написать программу, которая получает на входе набор идентификаторов, организует таблицу по заданному методу и позволяет осуществить многократный поиск идентификатора в этой таблице. Список идентификаторов считать заданным в виде текстового файла. Длина идентификаторов ограничена 32 символами.
Требуется, чтобы программа сообщала среднее число коллизий и среднее количество сравнений, выполненных для поиска идентификатора.

Тип хеш-функции : Сумма кодов первой и второй букв.
Способ разрешения коллизий : Метод цепочек.

Очень мало информации по хеш-таблицам. Было бы здорово найти пример выполнения подобных задач или хотя бы ссылочку на какой-либо источник по данной теме. В поиске нашел пару ссылок, но они битые sad.gif(
volvo
Цитата(Fellout @ 25.09.2008 11:41) *
Очень мало информации по хеш-таблицам. Было бы здорово найти пример выполнения подобных задач
Берешь исходники FreePascal-я (осторожно, размер = 42 Мб), открываешь файл \fpcbuild-2.2.2\fpcsrc\packages\fcl-base\src\contnrs.pp, и смотришь реализацию класса TFPCustomHashTable (который представляет собой не что иное, как хеш-таблицу с разрешением коллизий методом цепочек)...

Ну, или здесь:
1) Разрешение коллизий при хешировании методом цепочек
2) (кэш Гугла) Отсюда:
Цитата
Помимо повторного хэширования есть еще один прием разрешения коллизий. Команды, имеющие одинаковые значения хэш-индекса, выстраиваются в списки в соответствующих строках таблицы, а не располагаются на свободных строках. При таком методе разрешения коллизий, называемом методом цепочек, уменьшается число шагов разрешения коллизии.
и далее, включая пример реализации...
Fellout
Спасибо за помощь, буду смотреть smile.gif)
Гость
Скажите пожалуйста где можно найти метод квадратичной пробы
volvo
Метод квадратичной пробы - это правило просмотра хеш-таблицы.

Разницу между методами линейных и квадратичных проб см. здесь: 15.3 Метод открытой адресации
Гость
function FindItem(value : TTableData; 
var probes : Integer) : TQuadraticReturn Value;

var
new_value : TTableData;
pos: integer;

begin

probes:=1;
pos:=(value mod TableSize);

repeat
new_value:=HashTable^[pos];
if (new_value=value) then
begin
result:=qFound;
exit;
end;
if(new_value=UNUSED) then
begin
Result:=qNotFound;
exit;
end;
pos:=(value+probes*brobes) mod Tablesize;
if (probes>tablesize) then
begin
Result:=qNotFound;
exit;
end;
until(false);
end;


Помогите пожалуйста переделать для работы со стринггридом
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.