home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / PASCAL / HASH.ZIP / LIST.7 < prev   
Encoding:
Text File  |  1993-01-04  |  3.6 KB  |  101 lines
  1. Program Search_With_Double_Hashing;
  2.  
  3.    Const
  4.       max_TAB_entry = 60;      {last TAB entry}
  5.       number_TAB_entries = 61; {number of entries in TAB}
  6.       empty = '    ';          {what an empty entry looks like}
  7.       p_prime = 59;            {first twin prime-used to calculate increment}
  8.       p = 61;                  {second twin prime-used to hash KEY}
  9.  
  10.    Type
  11.       string4 = string[4];
  12.  
  13.    Var
  14.       found: boolean;          {set true by search if KEY is found}
  15.       index: integer;          {pointer to the TAB entry being examined}
  16.       KEY: string4;            {name to found or entered}
  17.       i: integer;              {for FOR loop use}
  18.       n: integer;              {number of entries currently in TAB}
  19.       TAB: array[ 0 .. max_TAB_entry ] of string4;
  20.  
  21.    Procedure Search( KEY: string4 );
  22.  
  23.       Function h( KEY: string4; modulus: integer ): integer;
  24.  
  25.          Type
  26.             KEY_types = (char_KEY, integer_KEY);
  27.             KEY_overlay = record
  28.                case  KEY_types of
  29.                   char_KEY:      ( KEY_in_characters: string4);
  30.                   integer_KEY:   ( dummy: byte; {takes up room for string size}
  31.                                    integer_KEY_1: integer; {first 2 bytes}
  32.                                    integer_KEY_2: integer; {last 2 bytes} );
  33.             end;
  34.  
  35.          Var
  36.             KEY_record: KEY_overlay;
  37.  
  38.          begin {h}
  39.             with KEY_record do
  40.                begin
  41.                   KEY_in_characters := '    '; {in case KEY < 4 chars}
  42.                   KEY_in_characters := KEY;
  43.                   h := ( integer_KEY_1 xor integer_KEY_2 ) mod modulus;
  44.                end;
  45.          end; {h}
  46.       Procedure add_KEY_to_TAB;
  47.          begin {add_KEY_to_TAB}
  48.             n := n + 1;  {one more entry in TAB}
  49.             if n > max_TAB_entry then {table is full}
  50.                begin
  51.                   writeln('     ***Fatal Error***');
  52.                   writeln('Table overflow in table TAB');
  53.                   writeln('      program aborted');
  54.                   halt; {stop with a fatal error}
  55.                end
  56.             else {there's still room, so add another entry}
  57.                TAB[ index ] := KEY;
  58.          end; {add_KEY_to_TAB}
  59.  
  60.       Var
  61.          j: integer;              {increment for current KEY}
  62.  
  63.       begin {search}
  64.          found := false;
  65.          index := h( KEY, p );  {go hash KEY}
  66.          if TAB[ index ] = KEY then {found it}
  67.             found := true
  68.          else {we have to do some more looking}
  69.             begin
  70.                if TAB[ index ] = empty then {it's not there - enter it}
  71.                   add_KEY_to_TAB
  72.                else
  73.                   begin
  74.                      j := h( KEY, p_prime ) + 1;  {calculate the increment}
  75.                      repeat
  76.                         index := index + j;  {step index to next entry}
  77.                         if index > max_TAB_entry then {off the end of TAB}
  78.                            index := index - number_TAB_entries; {make circular}
  79.                         if TAB[ index ] = KEY then {we found it}
  80.                            found := true;   {so say so}
  81.                      until ( TAB[ index ] = empty )  or found;
  82.                      if not found then {we need to enter KEY}
  83.                         add_KEY_to_TAB;  {so do so}
  84.                   end;
  85.             end;
  86.       end; {search}
  87.  
  88.    Begin {Search_With_Double_Hashing}
  89.       n := 0;  {no entries in TAB yet}
  90.       for i := 0 to max_TAB_entry do TAB[ i ] := empty; {all entries available}
  91.  
  92.  
  93.  
  94.       {user code goes here}
  95.  
  96.  
  97.  
  98.  
  99.    End. {Search_With_Double_Hashing}
  100.  
  101.