Род Стивенс

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

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

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

Перераспределение

Чтобы освободить записи хеш-таблицы, помеченные как удаленные, можно пе­рераспределить элементы таблицы, или выполнить ее рехеширование (rehashing). Но прежде нужно выяснить, не было ли выполнено перераспределение элемента раньше. Один из способов реализации такого подхода заключается в использова­нии массива переменных Boolean, указывающих ячейки, которые еще не перерас­пределены.

Начните с установки всех этих значений в True. Это означает, что все элемен­ты должны быть перераспределены. Затем следует просмотреть таблицу в поис­ках записей, которые не отмечены как удаленные и еще не перераспределены.

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

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

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

type

TBoolArray = array [0..1000000] of Boolean;

PBoolArray = ATBoolArray;

procedure Rehash;

var

not_rehashed ; PBoolArray;

i, pos ; Integer;

value, new_value : TTableData;

begin

// Выделеьже места для флагов Перераспределена.

GetMem(not_rehashed,TableSize*SizeOf(Boolean));

11 Пометка всех элементов как

for i := 0 to TableSize - 1 do not_rehashedA[i] : = True;

// Поиск неперераспределенных элементов.

for i ;= 0 to TableSize - 1 do

begin

if (not_rehashedA[i]) then begin

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

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