|
Страница 37 из 60
Хеширование Хешированием называется процесс выделения элемента индексно-
го массива непосредственно по информации, которая содержится в
массиве. Полученный индекс называется хеш-адресом. Хеширование
обычно используется для уменьшения времени доступа к дисковым
файлам. Однако, тот же метод можно использовать для реализации
разреженных матриц. В приводимом ниже примере используется проце-
дура, где применяется специальная форма хеширования, называемая
прямым индексированием. При прямом индексировании каждому ключу
соответствует одна и только одна ячейка. (Т.е. хеширование дает
уникальный индекс для каждого ключа. Однако, следует заметить,
что применение массива указателей не обязательно требует исполь-
зования прямой индексации; просто для решения данной задачи такой
подход является очевидным). На практике такая схема прямого хеши-
рования используется не очень часто и чаще требуется более гибкий
метод. В этом разделе будут рассмотрены более общие методы хеши-
рования, более мощные и более гибкие.
Из предыдущего примера по электронной матрице ясно, что даже
в особых случаях не все ячейки будут использованы. Предположим,
что в большинстве случаев не более десяти процентов потенциальных
ячеек будет действительно использовано. Это значит, что логичес-
кий массив с размерами 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; { конец функции поиска }
Следует иметь в виду, что описанная в этом разделе схема хе-
ширования очень проста и на практике приходится применять более
сложные схемы хеширования. Например, при возникновении конфликта
очень часто используют вторичное и третичное хеширование прежде,
чем воспользоваться просмотром цепочки индексов хеширования. Од-
нако, основные принципы хеширования остаются неизменными.
|