IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Хеш-таблица, Создание хеш-таблиц
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 9
Пол: Мужской

Репутация: -  0  +


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

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

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


Гость






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

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





Группа: Пользователи
Сообщений: 9
Пол: Мужской

Репутация: -  0  +


Спасибо за помощь, буду смотреть smile.gif)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Скажите пожалуйста где можно найти метод квадратичной пробы
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






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

Разницу между методами линейных и квадратичных проб см. здесь: 15.3 Метод открытой адресации
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






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;


Помогите пожалуйста переделать для работы со стринггридом
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 7:58
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name