MODULE Hashing; IMPORT Read, Write, Conclusions, RandomGenerators; CONST lengthListe = 11; (* sollte Primzahl sein *) TYPE Liste = POINTER TO Elements; Elements = RECORD content: INTEGER; next: Liste; END; HashTable = ARRAY lengthListe OF Liste; VAR counter: INTEGER; value: INTEGER; anchor: HashTable; (* Returns a random integer number between 1..max. *) PROCEDURE GetRandomNumber(max : INTEGER) : INTEGER; BEGIN RETURN ( (SHORT(RandomGenerators.Int32Val()) MOD max) + 1 ); END GetRandomNumber; (* Fuer jede moegliche Hashadresse eine Liste anlegen. *) PROCEDURE Init(); VAR count: INTEGER; BEGIN count := 0; WHILE count < LEN(anchor) DO anchor[count] := NIL; INC(count); END; END Init; (* Elemente nach dem Prinzip der einfach verketteten Liste * einfuegen (Wird im Hauptprogramm nicht verwendet, da * Elemente dann nicht sortiert sind)! *) PROCEDURE InsertEinfach(val: INTEGER); VAR add: INTEGER; elem: Liste; BEGIN add := val MOD lengthListe; NEW(elem); elem.content := val; elem.next := anchor[add]; anchor[add] := elem; END InsertEinfach; (* Elemente in sortierte Reihenfolge einfuegen *) PROCEDURE InsertSorted(val: INTEGER); VAR tmp, pre, elem: Liste; add: INTEGER; BEGIN add := val MOD lengthListe; pre := NIL; tmp := anchor[add]; (* Suche nach dem potentiellen Vorgaenger, * existiert kein Vorgaenger zeigt pre auf NIL * (potentieller Vorgaenger, da das Element erst * noch nach dem "Vorgaenger" eingefuegt werden * muss...)! *) WHILE (tmp # NIL) & (tmp.content < val) DO pre := tmp; tmp := tmp.next; END; (* Kein Vorgaenger vorhanden *) IF pre = NIL THEN NEW(elem); elem.content := val; elem.next := anchor[add]; anchor[add] := elem; (* Vorgaenger vorhanden *) ELSE NEW(elem); elem.content := val; elem.next := pre.next; pre.next := elem; END; END InsertSorted; (* Element aus der Liste loeschen mit Vorgaengersuche * (Wird im Hauptprogramm nicht verwendet, da DeleteNext * einfacher ist)! *) PROCEDURE DeletePre(val: INTEGER); VAR tmp, pre: Liste; add: INTEGER; BEGIN add := val MOD lengthListe; pre := NIL; tmp := anchor[add]; (* Suche nach dem Vorgaenger ( < )..., * existiert kein Vorgaenger zeigt pre auf NIL! *) WHILE (tmp # NIL) & (tmp.content < val) DO pre := tmp; tmp := tmp.next; END; (* Loesche Element, falls Vorgaenger und das gesuchte * Element (Nachfolger des Vorgaengers) exisitieren! *) IF (pre # NIL) & (pre.next # NIL) & (pre.next.content = val) THEN (* Element wird geloescht *) pre.next := pre.next.next; (* Das gesuchte Element kann immer noch an erster Stelle in * der Liste stehen und hat deshalb auch keinen Vorgaenger! *) ELSIF (anchor[add] # NIL) & (anchor[add].content = val) THEN (* Element wird geloescht *) Write.Ln; Write.String("Element"); Write.Int(anchor[add].content, 3); Write.String(" wurde geloescht!"); Write.Ln; anchor[add] := anchor[add].next; END; END DeletePre; (* Element aus der Liste loeschen mit next *) PROCEDURE DeleteNext(val: INTEGER); VAR tmp: Liste; add: INTEGER; BEGIN add := val MOD lengthListe; tmp := anchor[add]; (* Das erste Element ist das zu loeschende Element *) IF (tmp # NIL) & (tmp.content = val) THEN Write.Ln; Write.String("Element"); Write.Int(tmp.content, 3); Write.String(" wurde geloescht!"); Write.Ln; anchor[add] := tmp.next; (* Else: Solange die Liste durchsuchen, bis tmp.next auf das * zu loeschende Element zeigt. *) ELSIF (tmp # NIL) & (tmp.next # NIL) THEN WHILE (tmp.next # NIL) & (tmp.next.content # val) DO tmp := tmp.next; END; (* Achtung: Falls gar kein Element mit Wert = val * existiert zeigt tmp.next auf NIL (es gibt dann * nix zu loeschen)! *) IF (tmp.next # NIL) THEN Write.Ln; Write.String("Element"); Write.Int(tmp.next.content, 3); Write.String(" wurde geloescht!"); Write.Ln; tmp.next := tmp.next.next; END; END; END DeleteNext; PROCEDURE Ausgabe(); VAR count: INTEGER; tmp: Liste; BEGIN count := 0; WHILE count < LEN(anchor) DO Write.Int(count,3); Write.String(": "); tmp := anchor[count]; WHILE tmp # NIL DO Write.Int(tmp.content,3); tmp := tmp.next; END; Write.Ln; INC(count); END; END Ausgabe; BEGIN Init(); (* Was passiert wenn beim Hashing (Adresse mit MOD berechnen) * 2 Werte auf die gleiche Adresse abgebildet werden? Alle Werte * werden sowieso abhaengig von ihrer Adresse in einer Liste * gespeichert. Bei gleicher Abbildung wird die Liste einfach * verlaengert. *) Write.Ln; counter := 1; (* Fuer optimales Hashing sollte das Array zwischen 70% und 90% * belegt sein, d.h. das Array sollte bei 50 einzufuegenden * Elementen fuer mindestens 55 Elemente Platz bieten. Zu * Demonstrationszwecken bietet unser Array nur 11 Elementen * Platz, d.h. die Ueberlauflisten sind sehr lang (= nicht * optimal, aber wie gesagt Effizienz sei hier mal unwichtig)! *) WHILE counter <= 50 DO value := GetRandomNumber(99); Write.String(" ("); Write.Int(value MOD lengthListe, 2); Write.String(":"); Write.Int(value, 2); Write.String(")"); (* InsertEinfach(value); *) InsertSorted(value); (* Sortiertes Einfuegen *) INC(counter); END; Write.Ln; InsertSorted(40); InsertSorted(67); Write.Ln; Ausgabe(); DeleteNext(10); DeleteNext(10); DeleteNext(10); DeleteNext(21); DeleteNext(65); DeleteNext(21); DeleteNext(32); DeleteNext(98); DeleteNext(76); DeleteNext(21); Write.Ln; Ausgabe(); Write.Ln; Write.Ln; END Hashing.