Unterabschnitte


A.2.7 Geschlossenes Hashing


A.2.7.1 Java-Version

Für die Testdaten wird die Klasse Student aus Java-Version wiederverwendet, allerdings erweitert um eine Hashfunktion.

Die Hashfunktion ist in der Schnittstelle Hashfaehig deklariert:

// Time-stamp: "(23.05.02 20:35) Hashfaehig.java [Klaus@Wachtler.de]"
//
// Interface für eine Klasse, die in eine Hashtabelle eingefügt werden kann
// für die Übungsaufgabe "Hashfunktion".
// Eine Implementation dieser Schnittstelle muß aus ihren
// sonstigen Daten einen Hashwert bilden, und als Rückgabewert
// von hashfunktion() liefern.
// Dieser Wert kann dann als Index in die Hashtabelle verwendet werden.

interface Hashfaehig
{
    int hashfunktion();
}

(Anmerkung: Ein Java-Object besitzt für Hashing bereits eine Methode namens hashCode(), die man hier verwenden könnte. Damit wäre das Interface Hashfaehig überflüssig und in der Klasse Student wäre lediglich die Methode hashfunktion() durch hashCode() zu ersetzen. Dies wird hier aber nicht genutzt, um unabhängig von existierenden Bibliotheken den Mechanismus möglichst klar darzustellen.)

Die Klasse für einen Studenten sieht damit so aus:

// Time-stamp: "(23.05.02 19:58) Student.java [Klaus@Wachtler.de]"
//
// Testklasse zum Einfügen in eine Hashtabelle

import java.util.*;

public class Student implements Hashfaehig
{
    private String   VorName;
    private String   NachName;
    public  int      Matrikelnummer;

    public Student()
    {
        VorName = NachName = "?";
        Matrikelnummer = -1;
    }

    public Student( String v, String n, int m )
    {
        VorName = v;
        NachName = n;
        Matrikelnummer = m;
    }

    public String toString()
    {
        return "<" + VorName + " "
            + NachName + " "
            + Matrikelnummer  + ">";
    }

    // vergleicht zwei Studenten auf Gleichheit
    public boolean equals( Object s )
    {
        return Matrikelnummer==((Student)s).Matrikelnummer;
    }

    // Implementation von Hashfaehig:
    // Weil der Suchschlüssel (die Matrikelnummer) bereits ein geeigneter
    // Hashwert ist, wird einfach diese geliefert; eine
    // Modulobildung zum Begrenzen auf die Tabellengröße wird
    // beim Aufrufer erledigt.
    public int hashfunktion()
    {
        return Matrikelnummer;
    }

} // class Student

Die Hashtabelle mit linearem Sondieren ist generisch, kann also nicht nur diesen einen Datentypen verwalten, sondern für jeden beliebigen (wichtig ist nur, daß die Methode equals() und die Schnittstelle Hashfaehig implementiert sind):

// Time-stamp: "06.05.03 18:22 Hash.java klaus@wachtler.de"
//
// Hash 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.
//
// Um zwischen noch freien, belegten und gelöschten Elementen zu
// unterscheiden, wird folgende Schweinerei gemacht:
//  - ein noch nie benutzter Platz in der Tabelle ist null.
//  - ein belegter Platz ist vom Typ Hashfaehig (also von einem
//    benutzerdefinierten Datentyp, der das Interface Hashfaehig
//    implementiert)
//  - ein früher benutzter, aber bereits wieder gelöschter Eintrag
//    wird auf ein Objekt vom Typ Geloescht gesetzt, und ist somit
//    als "bereits gelöscht" erkennbar.
// Nicht schön, aber praktisch.

import java.util.*;
import java.lang.Class;

public class Hash
{
    static class Geloescht implements Hashfaehig
    {
        public int hashfunktion() { return 0; } // egal, was
    }

    private Hashfaehig[]  Tabelle = null;
    private int           Tabellenlaenge = 0;

    public Hash( int Tabellengroesse )
    {
        Tabelle = new Hashfaehig[Tabellengroesse];
        Tabellenlaenge = Tabellengroesse;
    }

    // Beim Einfügen wird nach dem nächsten freien oder gelöschten
    // Eintrag gesucht; falls dabei bereits ein gültiger Eintrag mit
    // demselben Hashwert gefunden wird, dann wird der überschrieben.
    // Wenn die Tabelle bereits restlos gefüllt ist, dann wird
    // false geliefert; sonst true.
    public boolean insert( Hashfaehig neu )
    {
        // Hier sollte der neue Eintrag landen, falls möglich:
        int wunschindex = neu.hashfunktion() % Tabellenlaenge;

        // Da lineares Sondieren gefordert ist, wird ab dem wunschindex
        // jeder Tabelleneintrag geprüft, bis ein geeigneter Platz
        // gefunden wird:
        for( int i=0; i<Tabellenlaenge; i++ )
        {
            int index = (wunschindex+i)%Tabellenlaenge;
            if( Tabelle[index]==null                       // unbenutzt?
                ||
                Tabelle[index].getClass()==Geloescht.class // gelöscht?
                ||
                Tabelle[index].equals( neu )               // vorhanden?
                )
            {
                Tabelle[index] = neu;
                return true;
            }
        }

        // Alle Einträge betrachtet, und keinen freien Platz gefunden?
        // Dann ist die Tabelle schon voll!
        return false;
    }

    // Beim Suchen mit get() wird solange gesucht, bis der Suchschlüssel
    // gefunden ist, oder ein unbenutzter Eintrag erreicht ist;
    // gelöschte Einträge werden übergangen.
    public Object get( Hashfaehig key )
    {
        // Hier sollte der gesuchte Eintrag stehen, falls er
        // ohne Kollision eingefügt wurde:
        int wunschindex = key.hashfunktion() % Tabellenlaenge;

        // Da lineares Sondieren gefordert ist, wird ab dem wunschindex
        // jeder Tabelleneintrag geprüft, bis der Schlüssel gefunden
        // ist, oder ein unbenutzter Eintrag erreicht ist:
        for( int i=0; i<Tabellenlaenge; i++ )
        {
            int index = (wunschindex+i)%Tabellenlaenge;
            if( Tabelle[index]==null )                     // unbenutzt?
            {
                return null; // nichts gefunden!
            }



            if( Tabelle[index].getClass()!=Geloescht.class // nicht gelöscht?
                &&
                Tabelle[index].equals( key )               // gleich?
                )
            {
                return Tabelle[index];
            }
        }

        // Alle Einträge betrachtet, und nichts gefunden?
        return null;
    }

    // Zum Löschen mit delete() wird solange gesucht, bis der Suchschlüssel
    // gefunden ist, oder ein unbenutzter Eintrag erreicht ist;
    // andere bereits gelöschte Einträge werden übergangen.
    public boolean delete( Hashfaehig key )
    {
        // Hier sollte der gesuchte Eintrag stehen, falls er
        // ohne Kollision eingefügt wurde:
        int wunschindex = key.hashfunktion() % Tabellenlaenge;

        // Da lineares Sondieren gefordert ist, wird ab dem wunschindex
        // jeder Tabelleneintrag geprüft, bis der Schlüssel gefunden
        // ist, oder ein unbenutzter Eintrag erreicht ist:
        for( int i=0; i<Tabellenlaenge; i++ )
        {
            int index = (wunschindex+i)%Tabellenlaenge;
            if( Tabelle[index]==null )                     // unbenutzt?
            {
                return false; // nichts gefunden!
            }



            if( Tabelle[index].getClass()!=Geloescht.class // nicht gelöscht?
                &&
                Tabelle[index].equals( key )               // gleich?
                )
            {
                // zu löschenden Eintrag gefunden!
                Tabelle[index] = new Geloescht(); // als gelöscht markieren
                return true;
            }
        }

        // Alle Einträge betrachtet, und nichts gefunden?
        return false;
    }

} // public class Hash

Das Testprogramm legt ein paar Studenten in der Tabelle ab, sucht etwas, und löscht dann wieder welche:

// Time-stamp: "06.05.03 18:16 TestHash.java klaus@wachtler.de"
//
// javac TestHash.java Hashfaehig.java Hash.java Student.java
// java TestHash

import java.util.*;

public class TestHash
{
    public static void main( String args[] )
    {
        // eine kleine Tabelle:
        Hash  Studententabelle = new Hash( 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
                                              )
                                 );
        // Anm.: weil die Tabellenplätze 7, 8, und 9 bereits belegt
        // sind, wird der letzte eingefügte Student statt bei 7
        // an der Stelle 0 eingetragen.

        // 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++ )
        {
            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 );
            }
        }

        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 TestHash


A.2.7.2 C++-Version

Die Klasse Student ist aus C++-Version übernommen; auch hier muß man für die Hashfunktion sorgen, sowie für den Vergleich auf Gleichheit (hier mit dem operator==()):

// Time-stamp: "11.05.03 19:09 Student.h klaus@wachtler.de"
//
// Beispieldatentyp für Hashtabellen.

#ifndef _STUDENT_H_
#define _STUDENT_H_

class Student
{
public:

  // Konstruktor
  Student( string v = "", string n = "", int m = -1 )
    : Vorname(v ),
      Nachname( n ),
      Matrikelnummer( m )
  {
  }

  // copy-Konstruktor
  Student( const Student &rechteSeite )
    : Vorname( rechteSeite.Vorname ),
      Nachname( rechteSeite.Nachname ),
      Matrikelnummer( rechteSeite.Matrikelnummer )
  {
  }

  // Destruktor
  virtual ~Student()
  {
  }

  // Zuweisung Student = Student
  Student & operator=( const Student &rechteSeite )
  {
    Vorname = rechteSeite.Vorname;
    Nachname = rechteSeite.Nachname;
    Matrikelnummer = rechteSeite.Matrikelnummer;

    return *this;
  }

  // Ausgabe auf einen ostream
  virtual void streamout( ostream & s ) const
  {
    s << Vorname;
    s << ",";
    s << Nachname;
    s << ",";
    s << Matrikelnummer;
  }

  // Kopie von sich selbst allokieren
  virtual Student &clone() const
  {
    return *(new Student(*this));
  }

  bool operator==( const Student &rS ) const
  {
    return Matrikelnummer==rS.Matrikelnummer;
  }

  // Die Hashfunktion liefert einfach die Matrikelnummer;
  // wenn der Aufrufer diesen Wert modulo Tabellengröße rechnet,
  // sollte ein vernünftiger Tabellenplatz herauskommen:
  size_t hashfunktion() const
  {
    return Matrikelnummer;
  }

private:

  // Nutzdaten:
  string Vorname;
  string Nachname;
  int    Matrikelnummer;


}; // class Student...

// ggf. nach Student.cpp kopieren (und static entfernen):
static ostream &operator<<( ostream &s, const Student &obj )
{
  obj.streamout( s );
  return s;
}

#endif /* _STUDENT_H_ */

Die C++-Lösung führt dieselben Operationen durch wie die Java-Version. Allerdings ist die Implementation ganz anders: durch die Nutzung von templates braucht man weniger Aufwand mit der Verwaltung von gelöschten Elementen treiben.

// Time-stamp: "11.05.03 19:28 hash.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:
//
// 04.05.2003 kw   im Destruktor ~Hash() das delete zu delete[] korrigiert
// 11.05.2003 kw   HashEintrag zu Unterklasse von Hash gemacht;
//                 aufgeteilt in hash.h und testhash.cpp

#ifndef _HASH_H_
#define _HASH_H_


#include <iostream>
#include <string>

using namespace std;

template<class T> class Hash
{
private:

  // Ein Eintrag der Tabelle besteht aus einem Zeiger auf die Nutzdaten,
  // sowie einem flag, ob der aktuelle Eintrag vielleicht gelöscht
  // wurde.
  // Mögliche Einträge:
  //  nutzdaten  |  geloescht |  Bedeutung
  //  -----------+------------+-------------------------------------
  //  NULL       |  false     | Eintrag noch unbenutzt
  //  -----------+------------+-------------------------------------
  //  !=NULL     |  egal      | Eintrag belegt
  //  -----------+------------+-------------------------------------
  //  NULL       |  true      | Eintrag war belegt, und ist gelöscht
  //  -----------+------------+-------------------------------------
  //

  class HashEintrag
  {
  public:

    T    *nutzdaten;
    bool  geloescht;

    // Konstruktor
    HashEintrag()
    {
      nutzdaten = NULL;
      geloescht = false;
    }

    // Destruktor
    ~HashEintrag()
    {
      delete nutzdaten;
    }
  }; // class HashEintrag


  // Die eigentliche Tabelle ist ein Zeiger auf ein
  // HashEintrag-Feld, das beim Erzeugen mit der richtigen
  // Anzahl allokiert wird:
  HashEintrag       *Tabelle;
  size_t             Tabellenlaenge;

 private:

  // Konstruktor ohne Parameter: private, damit niemand eine
  // leere Tabelle erzeugen kann.
  Hash()
  {
    Tabelle = NULL;
  }

 public:

  // Konstruktor mit Anzahl Einträge
  Hash( size_t Tabellengroesse )
  {
    Tabelle = new HashEintrag[Tabellengroesse];
    Tabellenlaenge = Tabellengroesse;
  }

  // Destruktor
  ~Hash()
  {
    delete[] Tabelle; Tabellenlaenge = 0;
  }

  bool insert( const T &neu )
  {
    size_t wunschindex = neu.hashfunktion() % Tabellenlaenge;

    // Da lineares Sondieren gefordert ist, wird ab dem wunschindex
    // jeder Tabelleneintrag geprüft, bis ein geeigneter Platz
    // gefunden wird:
    for( unsigned int i=0; i<Tabellenlaenge; i++ )
    {
      size_t index = (wunschindex+i)%Tabellenlaenge;

      if( Tabelle[index].nutzdaten==NULL )
      {
        // Eintrag leer, als hier einfügen!
        // Da hier eine Kopie angelegt wird, hat dieser Container eine
        // Wertsemantik.
        Tabelle[index].nutzdaten = new T( neu );
        return true;
      }
      else if( *(Tabelle[index].nutzdaten)==neu )
      {
        // Eintrag mit diesem Schlüssel schon vorhanden,
        // also überschreiben:
        *(Tabelle[index].nutzdaten) = neu;
        return true;
      }
    }

    // Alle Einträge betrachtet, und keinen freien Platz gefunden?
    // Dann ist die Tabelle schon voll!
    return false;

  }

  // Die Suche mit get() liefert einen Zeiger auf das gefundene Objekt,
  // oder NULL, wenn nichts gefunden wird.
  const T *get( const T &key )
  {
    size_t wunschindex = key.hashfunktion() % Tabellenlaenge;

    // Da lineares Sondieren gefordert ist, wird ab dem wunschindex
    // jeder Tabelleneintrag geprüft, bis das gesuchte Element
    // gefunden wird:
    for( unsigned int i=0; i<Tabellenlaenge; i++ )
    {
      size_t index = (wunschindex+i)%Tabellenlaenge;

      if( Tabelle[index].nutzdaten==NULL  // nicht belegt!
          &&
          !Tabelle[index].geloescht       // nicht gelöscht
          )
      {
        // dies ist ein jungfräulicher Eintrag,
        // die Suche kann abgebrochen werden!
        return NULL;
      }
      else if( Tabelle[index].nutzdaten!=NULL   // belegt!
               &&
               *(Tabelle[index].nutzdaten)==key // Treffer!
               )
      {
        return Tabelle[index].nutzdaten;
      }
    }
    // Alle Einträge betrachtet, und keinen freien Platz gefunden?
    // Dann ist die Tabelle schon voll, und nichts gefunden!
    return NULL;
  }

  // Beim Löschen mit delete() wird false geliefert, wenn nichts gelöscht
  // werden kann.
  bool del( const T &key )
  {
    size_t wunschindex = key.hashfunktion() % Tabellenlaenge;

    // Da lineares Sondieren gefordert ist, wird ab dem wunschindex
    // jeder Tabelleneintrag geprüft, bis das gesuchte Element
    // gefunden wird:
    for( unsigned int i=0; i<Tabellenlaenge; i++ )
    {
      size_t index = (wunschindex+i)%Tabellenlaenge;

      if( Tabelle[index].nutzdaten==NULL  // nicht belegt!
          &&
          !Tabelle[index].geloescht       // nicht gelöscht
          )
      {
        // dies ist ein jungfräulicher Eintrag,
        // die Suche kann abgebrochen werden!
        return false;
      }
      else if( Tabelle[index].nutzdaten!=NULL   // belegt!
               &&
               *(Tabelle[index].nutzdaten)==key // Treffer!
               )
      {
        delete Tabelle[index].nutzdaten; // Speicher freigeben
        Tabelle[index].nutzdaten = NULL; // als "unbenutzt" markieren
        Tabelle[index].geloescht = true; // als "gelöscht" markieren
      }
    }

    // Alle Einträge betrachtet, und keinen freien Platz gefunden?
    // Dann ist die Tabelle schon voll, und nichts gefunden!
    return false;
  }


}; // class Hash



#endif /* _HASH_H_ */

Das Testprogramm hierzu:

// Time-stamp: "11.05.03 19:13 testhash.cpp klaus@wachtler.de"
//
// Testprogramm zur C++-Lösung der Übungsaufgabe "Hashtabelle".
//
// ANSI-C++
//
// Linux:    g++ -Wall testhash.cpp && ./a.out
//
// VC++ 6.0: cl /Zi /GX testhash.cpp
//           .\testhash
//
// 04.05.2003 kw   im Destruktor ~Hash() das delete zu delete[] korrigiert
// 11.05.2003 kw   HashEintrag zu Unterklasse von Hash gemacht;
//                 aufgeteilt in hash.h und testhash.cpp

#include <iostream>
#include <string>


//////////////////////////////////////////////////////////////////////
//
// Testprogramm:

#include "hash.h"

#include "Student.h"

using namespace std;



int main( int nargs, char **args )
{
  // eine kleine Tabelle:
  Hash<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
                                    )
                           );
  // Anm.: weil die Tabellenplätze 7, 8, und 9 bereits belegt
  // sind, wird der letzte eingefügte Student statt bei 7
  // an der Stelle 0 eingetragen.

  // 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