Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Хеш-таблица

Автор: Fellout 25.09.2008 15:41

Дано задание : написать программу, которая получает на входе набор идентификаторов, организует таблицу по заданному методу и позволяет осуществить многократный поиск идентификатора в этой таблице. Список идентификаторов считать заданным в виде текстового файла. Длина идентификаторов ограничена 32 символами.
Требуется, чтобы программа сообщала среднее число коллизий и среднее количество сравнений, выполненных для поиска идентификатора.

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

Очень мало информации по хеш-таблицам. Было бы здорово найти пример выполнения подобных задач или хотя бы ссылочку на какой-либо источник по данной теме. В поиске нашел пару ссылок, но они битые sad.gif(

Автор: volvo 29.09.2008 14:25

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

Ну, или здесь:
1) http://www.structur.h1.ru/hash.htm
2) http://209.85.135.104/search?q=cache:kLzw0xsV7kYJ:www.khspu.ru/~khpms/learner/distant/files/2006/ol_inf10-11.doc+%D1%85%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5+%D0%BC%D0%B5%D1%82%D0%BE%D0%B4+%D1%86%D0%B5%D0%BF%D0%BE%D1%87%D0%B5%D0%BA+procedure&hl=ru&ct=clnk&cd=5 Отсюда:
Цитата
Помимо повторного хэширования есть еще один прием разрешения коллизий. Команды, имеющие одинаковые значения хэш-индекса, выстраиваются в списки в соответствующих строках таблицы, а не располагаются на свободных строках. При таком методе разрешения коллизий, называемом методом цепочек, уменьшается число шагов разрешения коллизии.
и далее, включая пример реализации...

Автор: Fellout 2.10.2008 18:45

Спасибо за помощь, буду смотреть smile.gif)

Автор: Гость 9.04.2009 18:25

Скажите пожалуйста где можно найти метод квадратичной пробы

Автор: volvo 9.04.2009 18:49

Метод квадратичной пробы - это правило просмотра хеш-таблицы.

Разницу между методами линейных и квадратичных проб см. здесь: http://cyber.sibsutis.ru:82/KURAPOVA/SAOD-BOOK-OLD/html/15.html#_label_15_3

Автор: Гость 9.04.2009 20:35

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;


Помогите пожалуйста переделать для работы со стринггридом