Род Стивенс

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

Открытая адресация

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

При открытой адресации (open addressing) хеш-функция вычисляет положе­ние элементов данных в массиве. Например, в качестве хеш-таблицы можно ис­пользовать массив с нижним индексом 0 и верхним 99.

Тогда хеш-функция будет сопоставлять ключу со значением К индекс масси­ва, равный К mod 100. При этом программа вставляет значение 1723 в таблицу на позицию 23. Затем, когда понадобится найти элемент 1723, в массиве исследуется именно эта позиция.

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

Линейная проверка

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

Рассмотрим снова пример с массивом размерами от 0 до 99 и хеш-функцией, отображающей элемент К на позицию К mod 100. Чтобы добавить элемент 1723, сначала исследуется позиция массива 23. Если она занята, то проверяется пози­ция 24. Если и она используется, рассматриваются позиции 25, 26, 27 и т.д., пока не найдется пустая позиция.

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

Можно записать объединенную функцию хеширования и проверки таким об­разом:

Hash(K,P) = (К + Р> mod 100, где Р = 0,1,2,...

Здесь Р - это номер элемента в последовательности проверки для элемента К. Другими словами, для хеширования элемента К проверяются элементы Hash (К, 0), Hash (К, 1), Hash (К, 2) и следующие до тех пор, пока не найдется незанятая позиция.

Можно обобщить эту идею, построив таблицу размера N с использованием массива размерами от 0 до N - 1. Хеш-функция выглядит следующим образом:

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

Следующий код показывает, как можно найти элемент в Delphi, используя линейную проверку.

type

TLinearReturnValue= (linlnserted, linFound,linNotFound,linTableFull);

: TLinearReturnValue;

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

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