Род Стивенс

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

В табл. 11.2 приведена средняя длина тестовой последовательности успешных и неудачных поисков с использованием линейных и упорядоченных линейных проверок. Средняя длина успешных поисков для этих двух методов одинакова, но в случае неудачи упорядоченная линейная проверка выполняется намного быст­рее. Разница особенно заметна, если хеш-таблица заполнена больше чем на 70%.

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

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

Квадратичная проверка

Один из способов уменьшить эффект первичной кластеризации заключается в том, чтобы использовать хеш-функцию следующего вида:

Hash (К, Р) = (К + Р2) mod N, где Р = 0,1,2,...

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

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

В следующем коде показывается, как найти элементы, используя квадратич­ную проверку (quadratic probing).

function Findltem(value : TTableData;

var probes : Integer) : TQuadraticReturnValue;

var

new value : TTableData; pos : Integer; begin

probes := 1;

pos := (value mod TableSize);

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

newvalue := HashTable'4 [pos] ; «

// Если мы нашли элемент, то готово. if (new value = value) 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.