Хеш-таблица, Создание хеш-таблиц Опции

[Fellout]

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

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

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

[volvo]

Очень мало информации по хеш-таблицам. Было бы здорово найти пример выполнения подобных задач

Берешь исходники FreePascal-я (осторожно, размер = 42 Мб), открываешь файл \fpcbuild-2.2.2\fpcsrc\packages\fcl-base\src\contnrs.pp, и смотришь реализацию класса TFPCustomHashTable (который представляет собой не что иное, как хеш-таблицу с разрешением коллизий методом цепочек)...

Ну, или здесь:
1) Разрешение коллизий при хешировании методом цепочек
2) (кэш Гугла) Отсюда:

Помимо повторного хэширования есть еще один прием разрешения коллизий. Команды, имеющие одинаковые значения хэш-индекса, выстраиваются в списки в соответствующих строках таблицы, а не располагаются на свободных строках. При таком методе разрешения коллизий, называемом методом цепочек, уменьшается число шагов разрешения коллизии.

и далее, включая пример реализации...

[Fellout]

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

[Гость]

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

[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; 

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