Деревья. ХЕШ-таблица с цепочками переполнения

Древовидная таблица

ХЕШ-таблица с цепочками переполнения

ХЕШ-таблица с открытым перемешиванием

ХЕШ-таблица

Сравнение неупорядоченной и упорядоченной таблицы

Операция удаления

Операция добавления

Для добавления вначале выполняется поиск. В случае успешного поиска операция завершается с ошибкой. Иначе: выполняется добавление новых записей на место, указываемое левым (верхним) указателем (см. поиск). Добавление новой записи в отсортированную таблицу требует сдвига записей, чтобы сохранить порядок. В среднем, сдвигаться будет ½ записей.

Тд = Тп +n/2 * 2 + 1 (y.o.) = ]log₂n[ + n + 1

Выполняется поиск. Если запись не найдена, то завершение с ошибкой. Иначе: выполняется удаление записи.

Для сохранения упорядоченности ключей на освободившееся место нужно сдвинуть записи.

Туд. = Тп + n/2 * 2 (у.о.) = ]log₂n[ + n

	неупорядоченная		упорядоченная
n
Тв
Тд
Туд

Операции добавления и удаления эффективнее в неупорядоченной (почти в два раза быстрее, чем в упорядоченной). Операция выборки выполняется значительно дольше, чем в упорядоченной, особенно при больших n.

ХЕШ-таблицу можно рассматривать как модификацию неупорядоченной таблицы с целью повышения эффективности поиска. Также ХЕШ-таблицу можно рассматривать как таблицу прямого доступа с выделением одного элемента для нескольких ключей.

n 1: Тп = n/2

n m: Тп = n/(m*2)

Таблица создается на базе массива записей, который распределяется для всех групп таблицы. В группу выделяется определенное множество ключей. Разделение ключей по группам выполняется с помощью ХЕШ-функции. Аргументам функции является ключ, результат – номер группы (в некоторых случаях номер первой записи в массиве). ХЕШ-функция задается жестко и не изменяется в процессе работы с таблицей. ХЕШ-функция должна быть подобрана таким образом, чтобы ключи равномерно распределялись по группам, а для этого необходимо знать закон распределения ключей в процессе работы, что бывает очень редко. Если закон неизвестен, считают, что ключи следуют по равномерному распределению.

Операция поиска

Выполняется по массиву записей, начиная с группы, указанной ХЕШ-функцией. Операция завершается в трех случаях:

1. Ключ обнаружен (поиск успешен).
2. Обнаружена пустая запись → ключ отсутствует и текущая запись является местом добавления ключа.
3. Просмотрены все элементы таблицы → ключ отсутствует и добавлять некуда.

Массив записей закольцован, поэтому после просмотра последней записи осуществляется переход к первой.

(есть пример в конспекте)

ХЕШ-таблица с цепочками переполнения состоит из первичной таблицы и цепочек переполнения, которые реализуются динамическим списком или вторичной таблицей. Размер первичной таблицы равен числу групп. В этой таблице для каждой группы есть только одна запись. Таблица имеет три поля: ключ, информация и указатель на цепочку.

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

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

Древовидная таблица является видом упорядоченных таблиц, построенных на базе упорядоченных деревьев. Виды и структура древовидных таблиц рассмотрены в разделе «Деревья».

Дата добавления: 2014-01-15