Für die Testdaten wird die Klasse Student aus Java-Version wiederverwendet, allerdings erweitert um eine Hashfunktion.
Siehe dazu Java-Version.
Die Klasse ist generisch, kann also nicht nur diesen einen Datentypen verwalten, sondern jeden beliebigen (wichtig ist nur, daß die Methode equals() und die Schnittstelle Hashfaehig implementiert sind):
// Time-stamp: "11.05.03 08:06 oHash.java klaus@wachtler.de" // // oHash kann eine Hashtabelle von fast beliebigen Daten verwalten. // Der zugrundeliegende Typ muß aber folgende Bedingungen erfüllen: // - die Methode equals() muß so implementiert sein, daß zwei // Objekte anhand des gewünschten Suchschlüssels als gleich oder // ungleich erkannt werden, und // - das Interface Hashfaehig muß implementiert sein. // // Die Tabellengröße wird beim Erzeugen der Hashtabelle im Konstruktor // angegeben, und kann im Nachhinein nicht mehr verändert werden. import java.util.*; import java.lang.Class; public class oHash { private einfacheListeGenerisch[] Tabelle = null; private int Tabellenlaenge = 0; public oHash( int Tabellengroesse ) { Tabelle = new einfacheListeGenerisch[Tabellengroesse]; Tabellenlaenge = Tabellengroesse; for( int i=0; i<Tabellengroesse; i++ ) { Tabelle[i] = new einfacheListeGenerisch(); } } // Zum Einfügen wird mit der Hashfunktion der zugehörige Platz // bestimmt, und das Objekt an die dort stehende Liste angefügt. // Der Einfachheit halber wird nicht geprüft, ob das Element // bereits in der Liste steht. // Dadurch wäre mehrfaches Einfügen eines Objekts möglich. // Nach dem Berechnen der Tabellenposition wird die gesamte Arbeit // der entsprechenden Liste überlassen. public void insert( Hashfaehig neu ) { Tabelle[neu.hashfunktion() % Tabellenlaenge].einf_vorn( neu ); } // Suchen eines Elementes: anhand des Hashwertes die richtige Liste // finden, und dort suchen lassen. public Object get( Hashfaehig key ) { return Tabelle[key.hashfunktion() % Tabellenlaenge].sucheWert( key ); } // Löschen eines Elementes: anhand des Hashwertes die richtige Liste // finden, und dort löschen lassen. public boolean delete( Hashfaehig key ) { return Tabelle[key.hashfunktion() % Tabellenlaenge].entf_wert( key ); } } // public class oHash
Das Testprogramm legt ein paar Studenten in der Tabelle ab, sucht etwas, und löscht dann wieder welche:
// Time-stamp: "11.05.03 19:44 TestoHash.java klaus@wachtler.de" // // javac TestoHash.java Hashfaehig.java oHash.java Student.java \ // einfacheListeGenerisch.java // java TestoHash import java.util.*; public class TestoHash { public static void main( String args[] ) { // eine kleine Tabelle: oHash Studententabelle = new oHash( 10 ); // etwas einfügen: Studententabelle.insert( new Student( "Kurt", "Warsteiner", 1234567 // hash=7 ) ); Studententabelle.insert( new Student( "Fritz", "Flens", 2345678 // hash=8 ) ); Studententabelle.insert( new Student( "Silke", "Amaretto", 3456789 // hash=9 ) ); Studententabelle.insert( new Student( "Marie", "Huana", 3456787 // hash=7 ) ); // nach Studenten suchen: Student[] key = new Student[5]; key[0] = new Student( "", "", 1234567 ); // vorhanden key[1] = new Student( "", "", 2345678 ); // vorhanden key[2] = new Student( "", "", 3456789 ); // vorhanden key[3] = new Student( "", "", 3456787 ); // vorhanden key[4] = new Student( "", "", 4567812 ); // nicht vorhanden for( int i=0; i<5; i++ ) { Object gefunden; gefunden = ( Studententabelle.get( key[i] ) ); if( gefunden==null ) { System.out.println( "Student " + key[i] + " nicht gefunden" ); } else { System.out.println( "gefunden: " + (Student)gefunden ); } } System.out.println( "\n" ); // 2 löschen: Studententabelle.delete( key[1] ); System.out.println( "gelöscht: " + key[1] ); Studententabelle.delete( key[2] ); System.out.println( "gelöscht: " + key[2] ); System.out.println( "\n" ); // und wieder suchen: for( int i=0; i<5; i++ ) { Student gefunden; gefunden = (Student)( Studententabelle.get( key[i] ) ); if( gefunden==null ) { System.out.println( "Student " + key[i] + " nicht gefunden" ); } else { System.out.println( "gefunden: " + gefunden ); } } } } // public class TestoHash
Die Klasse Student für die Testdaten ist wie beim geschlossenen Hashing aus C++-Version übernommen; auch hier muß man für die Hashfunktion sorgen, sowie für den Vergleich auf Gleichheit (hier mit dem operator==()). Siehe dazu die Lösung zum geschlossenen Hashing in C++-Version.
Anstelle des linearen Sondierens wird beim geschlossenen Hashing fast die gesamte Arbeit auf die Listen abgewälzt; dadurch wird die Lösung recht kompakt und übersichtlich:
// Time-stamp: "11.05.03 19:37 ohash.h klaus@wachtler.de" // // C++-Lösung der Übungsaufgabe "Hashtabelle". // // Die verwalteten Daten benötigen eine Methode int hashfunktion(), // die eine ganze Zahl als Tabellenindex liefert, sowie den // operator==(). // Der von hashfunktion() gelieferte Wert darf beliebig groß sein // (oder auch negativ); eine Reduzierung auf die Tabellenlänge wird // automatisch vorgenommen. // // // Änderungen: // // 11.05.2003 kw aus hash.h übernommen und auf offenes Hashing // umgebaut #ifndef _OHASH_H_ #define _OHASH_H_ #include <iostream> #include <string> #include "einfacheListeGenerisch.h" using namespace std; template<class T> class oHash { private: // Die eigentliche Tabelle ist ein Zeiger auf ein // Feld von Listen von T, das beim Erzeugen mit der richtigen // Anzahl allokiert wird: einfacheListeGenerisch<T> *Tabelle; size_t Tabellenlaenge; private: // Konstruktor ohne Parameter: private, damit niemand eine // leere Tabelle erzeugen kann. oHash() { Tabelle = NULL; } public: // Konstruktor mit Anzahl Einträge oHash( size_t Tabellengroesse ) { Tabelle = new einfacheListeGenerisch<T>[Tabellengroesse]; Tabellenlaenge = Tabellengroesse; } // Destruktor ~oHash() { delete[] Tabelle; Tabellenlaenge = 0; } // Da die Listen beim offenen Hashing theoretisch beliebig lang // werden können, gibt es keinen Fehler beim Einfügen. // Deshalb gibt insert() nichts zurück. void insert( const T &neu ) { Tabelle[neu.hashfunktion() % Tabellenlaenge].einf_vorn( neu ); } // Die Suche mit get() liefert einen Zeiger auf das gefundene Objekt, // oder NULL, wenn nichts gefunden wird. const T *get( const T &key ) { return Tabelle[key.hashfunktion() % Tabellenlaenge].sucheWert( key ); } // Beim Löschen mit delete() wird false geliefert, wenn nichts gelöscht // werden kann. bool del( const T &key ) { return Tabelle[key.hashfunktion() % Tabellenlaenge].entf_wert( key ); } }; // class oHash #endif /* _OHASH_H_ */
Das Testprogramm entspricht C++-Version:
// Time-stamp: "11.05.03 19:44 testohash.cpp klaus@wachtler.de" // // Testprogramm zur C++-Lösung der Übungsaufgabe "Offenes Hashing". // // ANSI-C++ // // Linux: g++ -Wall testohash.cpp && ./a.out // // VC++ 6.0: cl /Zi /GX testohash.cpp // .\testohash // // 11.05.2003 kw aus testhash.cpp übernommen und auf offenes Hashing // umgebaut #include <iostream> #include <string> ////////////////////////////////////////////////////////////////////// // // Testprogramm: #include "ohash.h" #include "Student.h" using namespace std; int main( int nargs, char **args ) { // eine kleine Tabelle: oHash<Student> Studententabelle( 10 ); // etwas einfügen: Studententabelle.insert( Student( "Kurt", "Warsteiner", 1234567 // hash=7 ) ); Studententabelle.insert( Student( "Fritz", "Flens", 2345678 // hash=8 ) ); Studententabelle.insert( Student( "Silke", "Amaretto", 3456789 // hash=9 ) ); Studententabelle.insert( Student( "Marie", "Huana", 3456787 // hash=7 ) ); // nach Studenten suchen: Student key[5]; key[0] = Student( "", "", 1234567 ); // vorhanden key[1] = Student( "", "", 2345678 ); // vorhanden key[2] = Student( "", "", 3456789 ); // vorhanden key[3] = Student( "", "", 3456787 ); // vorhanden key[4] = Student( "", "", 4567812 ); // nicht vorhanden int i; for( i=0; i<5; i++ ) { const Student *gefunden; gefunden = Studententabelle.get( key[i] ); if( gefunden==NULL ) { cout << "Student " << key[i] << " nicht gefunden" << endl; } else { cout << "gefunden: " << *gefunden << endl; } } cout << endl; // 2 löschen: Studententabelle.del( key[1] ); cout << "gelöscht: " << key[1] << endl; Studententabelle.del( key[2] ); cout << "gelöscht: " << key[2] << endl; cout << endl; // und wieder suchen: for( i=0; i<5; i++ ) { const Student *gefunden; gefunden = Studententabelle.get( key[i] ); if( gefunden==NULL ) { cout << "Student " << key[i] << " nicht gefunden" << endl; } else { cout << "gefunden: " << *gefunden << endl; } } return 0; } // main( int nargs, char **args )
www.wachtler.de