home *** CD-ROM | disk | FTP | other *** search
/ Turbo Toolbox / Turbo_Toolbox.iso / 1989 / 01 / hitech / hash.pas < prev   
Encoding:
Pascal/Delphi Source File  |  1988-10-20  |  3.7 KB  |  110 lines
  1. (* ------------------------------------------------------ *)
  2. (*                      HASH.PAS                          *)
  3. (*              Testprogramm zum Hashing                  *)
  4. (*       (c) 1988 by Harald Großauer & TOOLBOX            *)
  5. (* ------------------------------------------------------ *)
  6. PROGRAM Hash;
  7.  
  8. USES Crt, Dos;
  9.  
  10. CONST
  11.   maxst          = 5000;     (* Maximaler Datenbereich    *)
  12.   calls          = 4000;     (* Anzahl der Sätze          *)
  13.   wiederholungen = 10;
  14.  
  15. TYPE
  16.   CARDINAL = WORD;     (* um eine gewisse Ähnlichkeit mit *)
  17.                        (* Modula2  zu erreichen...        *)
  18.   stTyp = RECORD
  19.             key     : CARDINAL;      (* Schlüssel         *)
  20.             element : INTEGER;       (* eigentliche Daten *)
  21.             col     : BOOLEAN;       (* Belegt-Flag       *)
  22.           END;
  23.  
  24. VAR
  25.   st:       ARRAY[1..maxst] OF stTyp;     (* Datenbereich *)
  26.   keytab:   ARRAY[1..calls] OF CARDINAL;
  27.                                       (* Schlüsseltabelle *)
  28.   sekukol,primkol:CARDINAL;           (* Kollisionszähler *)
  29.   i,j,k:  CARDINAL;
  30.   rndval,adress: CARDINAL;
  31.   h,m,s,hs:WORD;
  32.   maxkol: CARDINAL;                  (* maximal Kollision *)
  33.  
  34. PROCEDURE Init;
  35. VAR i:CARDINAL;
  36. BEGIN
  37.   FOR i := 1 TO maxst DO st[i].col := FALSE;
  38. END;
  39.  
  40. PROCEDURE KollisionFkt(typ : BOOLEAN; val : CARDINAL;
  41.                                      VAR adress : CARDINAL);
  42. VAR   ok     : BOOLEAN;
  43.       i      : CARDINAL;
  44. CONST faktor = 11;
  45. BEGIN
  46.   primkol := primkol + 1; ok := FALSE; i := 1;
  47.   WHILE NOT ok DO BEGIN
  48.  
  49. (* ------------ Kollisions-Strategien ------------------- *)
  50. (*  adress:= (adress + i * faktor) MOD maxst;             *)
  51. (*  adress:= (adress + i + faktor) MOD maxst;             *)
  52. (* ------------------------------------------------------ *)
  53.  
  54.     adress:= (adress + i * i     ) MOD maxst;
  55.  
  56.     IF typ THEN
  57.       IF NOT st[adress].col THEN BEGIN    (* Schreiben... *)
  58.         st[adress].col := TRUE;
  59.         ok             := TRUE;
  60.       END ELSE BEGIN
  61.         i := i + 1; sekukol := sekukol + 1;
  62.       END
  63.     ELSE
  64.       IF st[adress].key = val THEN ok := true (* Lesen... *)
  65.                               ELSE i := i + 1;
  66.   END;
  67.          (* ermittle maximal vorkommende Kollisionsanzahl *)
  68.   IF i > maxkol THEN maxkol := i;
  69. END;
  70.  
  71.  
  72. PROCEDURE HashFkt(typ : BOOLEAN; val : CARDINAL;
  73.                                      VAR adress : CARDINAL);
  74. BEGIN
  75.   adress := val MOD maxst;
  76.   IF typ THEN                             (* Schreiben... *)
  77.     IF st[adress].col THEN KollisionFkt(typ,val,adress)
  78.                                           (* kollidiert?  *)
  79.                       ELSE st[adress].col := TRUE
  80.     ELSE                                  (* Lesevorgang  *)
  81.       IF st[adress].key<>val THEN
  82.         KollisionFkt(typ,val,adress);
  83. END;
  84.  
  85.  
  86. BEGIN
  87.   Randomize;
  88.   Init;
  89.   sekukol := 0; primkol := 0; maxkol := 0;
  90.   FOR j := 1 TO calls DO BEGIN
  91.     rndval:=Random(10000);
  92.     HashFkt(TRUE,rndval,adress);
  93.                                (* Ermittlung der Adresse  *)
  94.     st[adress].key:=rndval;    (* Abspeicherung Schlüssel *)
  95.     keytab[j]:=rndval;
  96.   END;
  97.   Write('Sekundär Kollision ',sekukol:6); WriteLn;
  98.   Write('Primär   Kollision ',primkol:6); WriteLn;
  99.   Write('Maximal  Kollision ',maxkol :6); WriteLn;
  100.   SetTime(0,0,0,0);
  101.   FOR i:=1 TO wiederholungen DO
  102.     FOR j:=1 TO calls DO BEGIN
  103.       HashFkt(FALSE,keytab[j],adress);
  104.                                 (* Ermittlung der Adresse *)
  105.     END;
  106.   GetTime(h,m,s,hs);
  107.   Write('HASHING Zeit: ',m*60+s+hs/100:6:2); WriteLn;
  108. END.
  109. (* ------------------------------------------------------ *)
  110. (*                   Ende von HASH.PAS                    *)