Род Стивенс

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

Программа Chain формирует связанную хеш-таблицу. Введите число создава­емых списков в поле Table Creation (Создание таблицы). Отметьте опцию Sort lists (Упорядоченные списки), если хотите, чтобы программа использовала сор­тированные списки. Затем щелкните по кнопке Create Table (Создать таблицу), и программа сформирует хеш-таблицу. Можно вводить другие значения и нео­днократно использовать кнопку Create Table, чтобы создавать новые хеш-таблицы.

Хеш-таблицы, содержащие большое количество элементов, наиболее интерес­ны, поэтому программа Chain позволяет заполнять таблицу случайными элемен­тами. Введите число элементов и максимальное значение элементов в области Random Items (Случайные элементы). Затем щелкните по кнопке Create Items (Создать элементы), и программа добавит случайные элементы в хеш-таблицу.

И наконец, введите значение в поле Search Area (Поле поиска). При щелчке по кнопке Add (Добавить) программа вставляет элемент в хеш-таблицу, если та­кого элемента в таблице нет. Если вы нажимаете кнопку Find (Найти), программа выполняет поиск элемента в таблице. При нажатии кнопки Remove (Удалить) программа удаляет элемент.

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

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

 

Блоки

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

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

: Например, чтобы добавить новый элемент К к хеш-таблице, содержащей пять блоков, сначала попытайтесь добавить его в блок с номером К mod 5. Если этот блок заполнен, поместите его в блок переполнения.

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

На рис. 11.3 показано пять блоков, пронумерованных от 0 до 4, и один блок переполнения. Каждый блок может содержать пять элементов. В хеш-таблицу были добавлены следующие элементы в указанном порядке: 50, 13, 10, 72, 25, 46, 68,30,99,85,93,65,70. При вставке элементов 65 и 70 блоки были уже заполнены, поэтому они были помещены в первый блок переполнения.

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

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