Реализация различных методов доступа к данным в таблицах по имени
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
иапазонах от 1 до 100. Возможные ключевые значения обычно охватывают очень широкий диапазон. В качестве ключа база данных, содержащая записи о сотрудниках, может использовать номер социального страхования. Существует 1 млрд возможных комбинаций девятизначных чисел подобно номеру социального страхования. Теоретически можно создать массив с одной записью для каждого возможного девятизначного номера, но на практике для этого не хватит памяти и дискового пространства. При том, что каждая запись занимает 1 Кбайт памяти, для массива потребовалось бы 1 Тбайт (1 млн мегабайт) памяти. Даже если бы компьютер и выделил такой объем памяти, эта схема оказалась бы очень неэкономной.
Если в штате компании меньше 10 млн служащих, массив на 99% всегда будет пуст.
Для решения подобных задач схемы хеширования отображают потенциально большое количество возможных ключей в относительно компактной хеш-таблице. Если в вашей компании работает 700 рабочих, вы можете объявить хеш-таблицу с 1000 записями.
Схема хеширования устанавливает соответствие между 700 записями о служащих и 1000 позициями таблицы. Хеш-функция может заносить записи в ячейки таблицы rfo первым трем цифрам номера социального страхования. Запись о сотруднике с номером социального страхования 123-45-6789 будет находиться в позиции 123.
Конечно, если возможных ключевых значений больше, чем ячеек таблицы, некоторые ключевые значения должны отобразиться в одну и ту же позицию в хеш-таблице. Например, значения 123-45-6789 и 123-99-9999 отображаются в таблице в позицию 123. Если есть 1 млрд возможных номеров социального страхования, а в таблице всего 1000 позиций, в среднем каждую позицию будет занимать 1 млн записей.
Во избежание подобной проблемы схема хеширования должна включать алгоритм разрешения конфликтов (collision resolution policy), определяющий порядок действий, если ключ отображается на занятую другой записью позицию.
Данные методы используют сходные способы разрешения конфликтных ситуаций. Сначала ключ записи отображается на позицию хеш-таблицы. Если позиция уже занята, то ключ заносится в новую позицию. Эта операция повторяется многократно до тех пор, пока алгоритм, наконец, не найдет пустую позицию в таблице.
Последовательность действий при нахождении или добавлении элемента в хеш-таблицу называется последовательностью проверки (probe sequence).
Для реализации хеширования необходимы три вещи:
структура данных, называемая хеш-таблицей, для хранения данных;
хеш-функция для отображения ключевых значений на ячейки таблицы;
алгоритм разрешения конфликтных ситуаций, который определяет порядок действий в ситуации, если ключи отображаются на одну и ту же позицию.
ПРАКТИЧЕСКАЯ ЧАСТЬ
Связывание
Один из методов разрешения конфликтов состоит в том, чтобы сохранять записи, отображаемые на одну позицию таблицы, в связанных списках. Для вставки новой записи с помощью хеш-функции выбирается связанный список, в котором будет находиться эта запись. Затем запись добавляется в этот список.
На рис. 1 показан пример связывания хеш-таблицы, которая содержит 10 ячеек. Хеш-функция отображает ключ К на позицию массива К mod 10. Каждая позиция массива содержит указатель на первый элемент связанного списка. Чтобы вставить элемент в таблицу, вы добавляете его в соответствующий список.
Рисунок 1- Связывание
Чтобы создать хеш-таблицу в Delphi, нужно объявить массив ячеек, начинающийся с нуля. Этот массив и будет являться списком меток. Если хеш-таблица будет содержать NumChains списков, объявите массив с границами от 0 до Num-Chains - 1. Установите каждое значение NextCell ячеек в nil.
Чтобы найти в хеш-таблице элемент с ключом К, необходимо вычислить К mod NumChains. Таким образом вы получите индекс метки связанного списка, в котором может содержаться элемент. Затем нужно просматривать список, пока не найдется искомый элемент или не будет достигнут конец списка.
: PChainCell;
begin
// Определение цепи, содержащей значение.
cell := ListTci^ [value mod NumChains].NextCell;
while (cellonil) do
if (се!1Л.value = value) then break;:= cellA.NextCell;;(cellonil) then
begin
// Какие-либо действия с ячейкой.
end;
Чтобы вставить в таблицу элемент с ключом К, сначала вычислим К mod Num-Chains, определив таким образом, какой список должен содержать данное значение. Затем, добавим элемент.
Insertltem(value : TTableData);, new_cell : PChainCell;
begin
.// Определение цепи, содержащей значение.
cell := OListTops"[value mod NumChains];
// Вставка элемента в начало цепи.
New(new_cell);
.Value := value;_cell*.NextCell := се!1л.NextCell,
се!1л.NextCell := new_cell;
end;
Хеш-таблицы обычно содержат только одну запись с данным ключом. В этом случае процедуре InsertIteih перед добавлением элемента необходимо проверить, нет ли такого элемента в таблице.
Чтобы удалить элемент из хеш-таблицы, вычислите К mod NumChains, определив содержащий его список. Затем элемент удаляется из списка.
Removeltem(value : TTableData);, nxt_cell : PChainCell;
begin
// Определение цепи, содержащей значение.
cell := @ListTops/4 [value mod NumChains];_cell := се!1Л.NextCell;
// Поиск элемента.
while (nxt_cellonil) do
if (nxt_cel!A.Value = value) then break;:= nxt_cell;_cell := се!1л.NextCell;;(nxt_cellonil) then
// Ячейка найдена. Удаляем ее.
Се11л.NextCell := nxt_cellA.NextCell;(nxt_cell); ,;
end;
Преимущества и недостатки связывания
Одно из преимуществ этого метода заключается в том, что связанные хеш-таблицы никогда не переполняются. Всегда проще осуществить вст