Новости           

Программы

Turbo Pascal

Игры

Документация

"Странности"

FAQ

Ссылки

Благодарности

Гостевая книга

От автора

ХЕШИРОВАНИЕ

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


        


                           Таблица
                    Индекс Знач.  След.  Индекс в таблице
                   +--------------------+
           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
                   +--------------------+

              Предполагается, что в ячейке 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 ((icname.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; { конец функции поиска }

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

(с)Все права защищены

По всем интересующим вопросампрошу писать на электронный адрес

    Rambler's Top100 PROext: Top 1000
    Rambler's Top100 Яндекс цитирования
Hosted by uCoz