Хеш-таблица

Cтраница 2

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

Объясните, чем упорядоченная хеш-таблица отличается от обычной хеш-таблицы. [17]

В интересном варианте хеш-таблиц используется цифровой ( или алфавитный) порядок имен. Это ведет к более быстрому поиску ценой небольшой дополнительной работы во время включения. [18]

Еще одно преимущество хеш-таблицы с использованием блоков, сохраненных на диске, состоит в том, что расширить таблицу, если она переполняется, очень просто. Когда все резервные блоки заполнятся, нужно просто создать новый блок переполнения в конце файла. [19]

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

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

Программа Chain формирует связанную хеш-таблицу. [22]

Чтобы найти в хеш-таблице элемент с ключом К, не обходимо вычислить К mod NumChains. Таким образом вы получите индекс метки связанного списка, в котором может содержаться элемент. Затем нужно просматривать список, пока не найдется искомый элемент или не будет достигнут конец списка. [23]

Чтобы удалить элемент из хеш-таблицы, вычислите KmodNumChains, определив содержащий его список. [24]

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

Квадратичная проверка. [26]

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

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

С - Связанные блоки переполнения. [29]

Если в блоках переполнения хеш-таблицы содержится много элементов, то связывание блоков переполнения может сэкономить много времени. Предположим, что имеется достаточно большая хеш-таблица, содержащая 1000 блоков, каждый из которых вмещает по 10 элементов. Предположим также, что в блоках переполнения находятся 1000 элементов, для которых понадобится 100 блоков переполнения. Чтобы найти один из последних элементов в блоках переполнения, необходимо исследовать i 01 блок. [30]

Страницы: 1 2 3 4