Род Стивенс

Книги → Delphi. Готовые алгоритмы → Глава 11. Хеширование

var

bucket, pos : Integer; begin

// Определение блока, в котором находятся элемент. bucket := (value mod NumBuckets);

GetBucket(bucket);

) '

/ / Поиск элемента или неиспользуемой позиции.

for pos := 0 to BUCKET_SIZE - 1 do begin

if (TheBucket[pos] = UNUSED) then begin

// Элемента в списке нет. exit;

end;

if (TheBucket[pos] = value) then begin

// Элемент найден. Какие-либо действия с этим элементом.

exit;

end;

end;

/ / Если не нашли элемент, проверяем блоки переполнения.

for bucket := NumBuckets to MaxOverflow do

begin

bucket_probes := bucket_probes + 1;

GetBucket(bucket);

for pos := 0 to BUCKET_SIZE - 1 do begin

item_probes := item_probes + 1; if (TheBucket[pos] = UNUSED) then , begin

/ / Элемента в списке нет. exit; end;

if (TheBucket[pos] = value) then begin

// Элемент найден. Какие-либо действия с элементом.

exit ; end;

end;

end;

// Если элемент так и не найден, то его в хеш-таблице нет.

end;

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

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

Каждый блок в программе Bucket2 может содержать до пяти элементов. Это позволяет легко вставлять элементы в блоки до тех пор, пока те не переполнятся. В реальной программе нужно уместить в блок как можно больше элементов так, чтобы размер блока оставался при этом кратным целому числу кластеров диска. Например, можно читать и записывать данные блоками по 1024 байт. Следую­щий код показывает, как программа может определить размер блоков по типу запи­си о служащем.

type

TTableData = record

LastName : String[20];

FirstName : String[20];

EmployeelD : Integer;

end;

const

ITEM_SIZE = SizeOf(TTableData) ;

ItEmS_PER_BUCKEt = 1024 div ITEM_SIZE;

type

← предыдущая следующая →

Страницы раздела: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Публикация компанией Dropbox кода Zulip – средства общения для IT-разработчиков

20.11.2015
Одной из одобрительно встреченных программистами инициатив, реализующихся в рамках акции Hack Week, стала публикация исходного кода приложения Zulip – веб-приложения для общения между собой разработчиков в сфере IT-технологий.

Объединение ОС Android и Chrome

17.11.2015
Слухи об объединении двух крупнейших ОС компании Google, Android и Chrome, гуляют по Интернету уже более 5 лет, но до сих пор этого не случилось, хотя очевидно, что с течением времени эти ОС становятся всё более похожими: так, в последнее время появилось немало Android-устройств, к которым прилагаются клавиатуры, а Chrome OS «научилась» работать с сенсорными экранами.

Конференция Linux Piter 2015

15.11.2015
Уже почти через неделю в Санкт-Петербурге впервые в истории пройдёт конференция, посвящённая проблемам свободного программного обеспечения – Linux Piter 2015.