Энциклопедия Turbo Pascal. Главы 1-4
Страница 37. Хеширование


Хеширование

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

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

 
« Предыдущая статья