Практические работы (задачи) / Задача 7

МИНИСТЕРСТВО ЦИФРОВОГО РАЗВИТИЯ, СВЯЗИ И МАССОВЫХ КОММУНИКАЦИЙ РОССИЙСКОЙ ФЕДЕРАЦИИ

Ордена Трудового Красного Знамени федеральное государственное бюджетное образовательное учреждение высшего образования

«Московский технический университет связи и информатики»

Кафедра «Сетевые информационные технологии и сервисы»

Задача №7

по дисциплине

«Принципы построения систем управления базами данных и знаний»

Выполнила:

Вариант №13

Проверил: доцент, к.т.н., Гадасин Д.В.

Москва 2023

Содержание

Условие задачи 3

Индивидуальное задание 5

Выполнение 5

Условие задачи

Поясните, как повлияют на содержимое сегментов хеш-таблицы, приведенной на рис, перечисленные ниже операции вставки и замены записей с заданными ключами. Вставляются записи g-k, а записи a и j удаляются; При условии, что блок может содержать 3 записи. Решение оформить в виде рисунка и дать подробное описание действий.

В таблице 1 заданы результаты хэш-функций для 26 записей.

Таблица 1 результаты хэш-функций

Запись	Результат хэш-функции
a	3
b	2
c	1
d	0
e	1
f	3
g	0
h	2
i	3
j	0
k	0
l	3
m	1
n	3
o	0
p	2
q	2
r	1
S	3
t	1
u	2
v	0
w	2
x	0
y	0
z	3

Индивидуальное задание

Индивидуальное задание

Вариант	Задание
13	Вставляются записи g, j, k, затем записи a и j удаляются. При условии, что блок может содержать 2 записи

Выполнение

Дана хэш-таблица (рис. 1).

Рисунок 1 – Исходная хэш-таблица

Требуется вставить записи g, j, k. Обратимся к таблице 1 чтобы узнать соответствующие индексы для записей. По этим индексам будет происходить дальнейшее добавление и удаление элементов.

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

Для записей g, j, k результат хэш-функции равен 0. Следовательно они все должны попасть в блок с индексом 0, но так как в этом блоке всего две свободные ячейки, то последняя запись попадет в область переполнения этого блока (рис.2).

Рисунок 2 – Хэш-таблица с добавленными записями g, j, k

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

Требуется удалить записи a и j, значения хэш-функции равны 3 и - соответственно, удаляем запись a и j, сдвигая следующий элемент выше (рис.3).

Рисунок 3 –Удаление записи a и j из хэш-таблицы

Так как в блоке, на который ссылается область переполнения, нет свободной ячейки, то запись остается области переполнения.