Род Стивенс

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

probes := probes + 1;

new_value := HashTable^[pos] ;

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

if <new_value = value) then

begin

Result := rndFound; exit; end;

// Если ячейка не используется, то элемента в таблице нет.

if (new_value = UNUSED) then

begin

Result := rndNotFound ; exit; end;

// Если мы исследовали все записи таблицы.

if (probes > TableSize) then

begin

Result := rndNotFound; exit; end;

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

end;

Программа Rand демонстрирует открытую адресацию с псевдослучайной про­веркой. Она аналогична программам Linear и Quad, но использует псевдослучай­ную, а не линейную и квадратичную проверки.

В табл. 11.4 показана приблизительная средняя длина последовательности проверки, полученной в программах Quad и Random для хеш-таблицы со 100 ячей­ками и элементами в пределах от 1 до 999. Псевдослучайная проверка обычно дает лучшие результаты, хотя разница между квадратичной и псевдослучайной провер­ками не так велика, как между линейной и квадратичной.

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

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

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

Удаление элементов

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

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

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

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