Энциклопедия Turbo Pascal. Главы 1-4 - Хеширование
ОГЛАВЛЕНИЕ
Хеширование
Хешированием называется процесс выделения элемента индексного массива непосредственно по информации, которая содержится в массиве. Полученный индекс называется хеш-адресом. Хеширование обычно используется для уменьшения времени доступа к дисковым файлам. Однако, тот же метод можно использовать для реализации разреженных матриц. В приводимом ниже примере используется процедура, где применяется специальная форма хеширования, называемая прямым индексированием. При прямом индексировании каждому ключу соответствует одна и только одна ячейка. (Т.е. хеширование дает уникальный индекс для каждого ключа. Однако, следует заметить, что применение массива указателей не обязательно требует использования прямой индексации; просто для решения данной задачи такой подход является очевидным). На практике такая схема прямого хеширования используется не очень часто и чаще требуется более гибкий метод. В этом разделе будут рассмотрены более общие методы хеширования, более мощные и более гибкие.
Из предыдущего примера по электронной матрице ясно, что даже в особых случаях не все ячейки будут использованы. Предположим, что в большинстве случаев не более десяти процентов потенциальных ячеек будет действительно использовано. Это значит, что логический массив с размерами 26х100 (2600 ячеек) потребует в действительности иметь память только под 260 элементов. Следовательно, потребуется иметь физический массив как максимум на 260 элементов. Тогда встает следующая задача: как логический массив отобразить на физический массив и как осуществлять к нему доступ? Ответ заключается в использовании списка индексов хеширования.
Когда пользователь вводит формулу в электронную матрицу (логический массив), адрес ячейки, задаваемый ее обозначением, используется для поручения индекса небольшого физического массива. Предположим, что переменная "sheet" является физическим массивом. Индекс определяется на основе обозначения ячейки путем его преобразования в число, как было сделано в примере с массивом указателей. Затем это число делится на десять для получения начальной точки входа в массив. (Следует помнить, что для вашего примера физический массив составляет только десять процентов от логического массива). Если ячейка с этим индексом свободна, то в нее помещается логический индекс и значение. В противном случае возникает конфликт. Конфликт случается при получении во время хеширования двух одинаковых ключей. В этом случае полученный индекс будет соответствовать одному элементу физического массива. Следовательно, в массиве "sheet" делается поиск свободного элемента. Когда свободный элемент найден, в него помещается информация, а указатель на это место будет помещен в исходный элемент.
Это иллюстрируется на рис.17.
Для поиска элемента в физическом массиве при заданном индексе логического массива сначала делается преобразование логического индекса в адрес, полученный посредством хеширования, и затем делается проверка физического массива на наличие в элементе с этим индексом требуемого значения. Если сравнение выполняется удачно, то информация найдена. В противном случае следует пройти по цепочке индексов до тех пор, пока не будет найдено нужное значение или пока не будет обнаружен конец цепочки.
Для того, чтобы понять, как эту процедуру можно применить к программе электронной таблицы сначала определим в качестве физического массива следующий массив записей:
const
SIZE = 260;
type
str9 = string[9];
str128 = string[128];
cell = record
CellName: str9;
formula: str128;
next: integer;
end;
var
sheet:array[0..SIZE] of cell;
name: cell;
Таблица
Индекс Знач. След. Индекс в таблице
-------T------T------¬
A1 ¦ A1 ¦ 100 ¦ 1 ¦0
+------+------+------+
A2 ¦ A2 ¦ 200 ¦ 3 ¦1
+------+------+------+
B19 ¦ B19 ¦ 50 ¦ -1 ¦2
+------+------+------+
A3 ¦ A3 ¦ 300 ¦ -1 ¦3
+------+------+------+
¦ -1 ¦ 0 ¦ -1 ¦4
+------+------+------+
¦ -1 ¦ 0 ¦ -1 ¦5
+------+------+------+
D2 ¦ D2 ¦ 99 ¦ -1 ¦6
+------+------+------+
¦ -1 ¦ 0 ¦ -1 ¦7
+------+------+------+
¦ ¦ ¦
¦ ¦
¦ ¦
¦ ¦
¦ ¦ ¦
+------+------+------+
¦ -1 ¦ 0 ¦ -1 ¦2597
+------+------+------+
¦ -1 ¦ 0 ¦ -1 ¦2598
+------+------+------+
¦ -1 ¦ 0 ¦ -1 ¦2599
L------+------+-------
Предполагается, что в ячейке A1 значение 100, в A2 значение 200, в A3 - 300, в B19 - 50, а в D2 - 99.
Рис.17. Пример хеширования.
Перед использованием этот массив должен быть инициализирован. Приводимая ниже процедура используется для установки поля обозначения ячейки на значение "empty" (пусто) для указания на отсутствие элемента. Значение -1 в поле следующего индекса означает конец цепочки индексов хеширования.
{ инициализация физического массива }
procedure InitSheet;
var
t:integer;
begin
for t := 0 to SIZE do
begin
sheet[t].CellName := 'empty';
sheet[t].next:= -1;
end;
end; { конец процедуры инициализации физического массива }В процедуре вставки делается обращение к функции HashIndex для вычисления индекса хеширования и помещения его в массив "sheet". Следует отметить, что если непосредственно полученное значение индекса хеширования указывает на занятую ячейку, то в процедуре выполняется поиск первого свободного места. Это делается путем просмотра цепочки индексов хеширования до тех пор пока не будет обнаружена первая свободная ячейка. Когда свободная ячейка найдена, то делается запоминание значения логического индекса и значения элемента массива. Значение логического индекса требуется сохранить, поскольку он требуется при новом обращении к этому элементу.
{ вычисление индекса хеширования и вставка значения элемента }
function HashIndex(i:str9):integer;
var
loc, temp, code:integer
t :str9;
begin
loc := ord(i[1]-ord('A');
t := copy(i,2,9)
val(t, temp, code)
HashIndex := (loc*26+temp) div 10;
end;
{ выполнение действительной вставки значения элемента }
procedure Store(New:Cell);
var
loc, i:integer;
begin
loc := HashIndex(New.Cellname);
if loc>SIZE then Writeln('Location out of bounds')
else
begin
if ((sheet[loc].Cellname = 'empty') or
(sheet[loc].Cellname = New.Cellname)) then
begin
sheet[loc].Cellname = New.Cellname;
sheet[loc].formula = New.formula;
end else { поиск свободной ячейки }
begin
{ сначала просмотр до конца всей цепочки существующих индексов}
while(sheet[loc].next <>-1) do
loc := sheet[loc].next;
{ теперь поиск свободной ячейки }
i := loc;
while ((i<SIZE) and (sheet[loc].Cellname='empty'))
do i := i+1;
if(i = SIZE) then
begin
Writeln('cannot plase in hash array');
end else
begin { поместить значение в свободную ячейку и
обновить цепочку }
sheet[i].Cellname = New.Cellname;
sheet[i].formula = New.formula;
sheet[loc].next := i; { обеспечение связи в
цепочке }
end;
end;
end;
end; { конец процедуры вставки }При поиске значения элемента сначала вычисляется индекс хеширования и делается проверка на равенство логического индекса, который содержится в физическом массиве, и искомого логического индекса. Если они совпадают, то в результате выдается этот индекс хеширования. В противном случае делается просмотр цепочки индексов до обнаружения требуемого значения или до обнаружения значения -1 в поле ссылки на следующий элемент. Последняя ситуация возникает при отсутствии требуемого элемента в физическом массиве. Ниже приводится функция, выполняющая эти действия:
{ поиск физического адреса ячейки }
function Find(cname:cell):integer;
var
loc:integer;
begin
loc := FindIndex(cname.CellName);
while((sheet[loc].CellName<>cname.CellName) and
(loc <> -1)) do loc:=sheet[loc].next;
if(loc = -1) then
begin
WriteLn('Not found');
Find := -1;
end else Find := loc;
write('loc is'); writeLn(loc);
end; { конец функции поиска }Следует иметь в виду, что описанная в этом разделе схема хеширования очень проста и на практике приходится применять более сложные схемы хеширования. Например, при возникновении конфликта очень часто используют вторичное и третичное хеширование прежде, чем воспользоваться просмотром цепочки индексов хеширования. Однако, основные принципы хеширования остаются неизменными.