Unterabschnitte


A.2.8 Offenes Hashing


A.2.8.1 Java-Version

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


A.2.8.2 C++-Version

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