Nächste Seite: A.2.9 Einfache Integration Aufwärts: A.2 Lösungen Vorherige Seite: A.2.7 Geschlossenes Hashing Inhalt
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 )