Род Стивенс

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

На практике степень кластеризации будет чем-то средним между этими край­ними случаями. Вы можете использовать программу Linear, чтобы исследовать эффект кластеризации. Запустите программу и постройте хеш-таблицу со 100 ячейками. Затем добавьте 50 случайных элементов со значениями до 999. Вы об­наружите, что сформировалось несколько кластеров. В одном из тестов 38 из 50 элементов стали частью кластера. Если добавить еще 25 элементов, то большин­ство элементов будут входить в кластеры. В другом тесте 70 из 75 элементов были сгруппированы в кластеры.

Упорядоченная линейная проверка

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

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

function Findltem(value : TTableData;

: TOrderedRetumValue;

var probes : Integer)

var

new_value : TTableData; pos : Integer; begin

probes := 1;

// Бесконечный цикл.

pos := (value mod TableSize) ; repeat

new_value := HashTableA[pos];

// Если мы нашли элемент, то готово.

if ( new_value = value) then begin

Result := ordFound; exit; end;

// Если элемент не используется, то значения в таблице нет. if (new_value = UNUSED) then begin

Result := ordNotFound; exit; end;

// Если исследуемое значение больше, чем новое, if ( new_value > value) then begin

Result := ordNotFound; exit ; end;

// Пытаемся проверить следующую позицию последовательности. pos := (pos + 1) mod TableSize; probes := probes + 1;

// Если мы рассмотрели все ячейки. if (probes > TableSize) then begin

Result : = ordNotFound; exit;

end;

until (False); // Конец бесконечного цикла поиска значения.

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

Страницы раздела: 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.