|
Objektorientiertes Programmieren mit C++ und JAVA
|
Wenn man eine Menge von Daten, die jeweils über einen Schlüssel
ansprechbar sind, abspeichern möchte, gibt es vielfältige
Möglichkeiten. Wir wollen vor allen Dingen schnell auf gespeicherte
Daten wieder zugreifen können (n=Anzahl der Elemente vor einem
Suchvorgang):
- Array/Liste:
-
Es muß der gesamte Datenbestand durchsucht
werden, Ordnung O(n).
- Falls auf dem Schlüsseltyp eine Ordnung
< definiert ist:
-
- sortierte Liste:
-
Der Suchvorgang kann ggf. frühzeitig abgebrochen werden,
wenn die mögliche Stelle des gesuchten Objekts überschritten ist.
Die Ordnung ist immer noch O(n).
- sortiertes Array:
-
Es kann mit binärer Suche (Intervallhalbierung) gearbeitet
werden, Ordnung O(log2n).
- sortierte Binärbäume:
-
Wenn kein entarteter Baum (listenähnlich) vorliegt,
ist hier auch die Ordnung O(log2n).
Hash-Verfahren benötigen dagegen nur O(1). Hier wird
der Schlüsseltyp auf ein Intervall abgebildet,
h:T -> [0,m-1] in N
abgebildet. Ein Element e mit h(e)=i wird dann im
i-ten "Eimer" (hash bucket) abgelegt.
Wird als Schlüsseltyp etwas String-ähnliches verwendet, könnte
die Hash-Funktion beispielsweise die Codes der einzelnen Zeichen verschoben
aufsummieren, etwa
-
h(t0 t1 ... tl-1)
:= (i=0Suml-1
ci · ord(ti) ) mod m
Diese Funktion verhält sich besonders gut, wenn die Anzahl m der
Eimer eine Primzahl ist.
Wenn der Datentyp n mögliche Werte annehmen kann und man eine
bijektive Funktion T -> [0,n-1] finden kann, kann man mit Arrays
arbeiten. Ansonsten sollte die Hashfunktion h nicht injektiv sein, da
sonst die Anzahl
benötigter Eimer zu groß wird: Strings mit vier Zeichen mit
jeweils 255 möglichen Werten lassen sich trivialer- aber
unrealistischerweise injektiv auf 2564=4294967296 Eimer abbilden.
Meist verwendet man ein Array aus n linearen Listen,
in denen Elemente mit gleichem Wert der Hashfunktion h verkettet
gespeichert werden.
Innerhalb eines Eimers muß linear mit Ordnung O(n)
gesucht werden. Wenn aber die einzelnen Eimer nicht überladen werden, ist
die Ordnung für das Auffinden eines Elements nur O(1).
Statt linearer Listen könnte man auch sortierte Binärbäume
verwenden. Wir wollen zur Verhinderung einer Entartung allerdings mit
Hashtabellen arbeiten, die sich bei Überladung automatisch
vergrößern. Dazu wird bei der Konstruktion ein sogenannter
"load factor" zwischen
0 und 1 festgelegt. Wenn die Anzahl eingetragener Elemente multipliziert
mit diesem Faktor die Anzahl der Eimer übersteigt, wird die Tabelle
um etwa den Kehrwert des Faktors vergrößert.
Schnittstellen:
Wir arbeiten mit einem Template
hashtable<ktype,dtype>,
abhängig von einem Schlüsseltyp ktype ( key type)
und einem Typ für die Daten dtype.
Da es nicht möglich ist, für jeden beliebigen Datentyp eine
Standard-Hashfunktion
zu erzeugen, muß dem Konstruktoren als Parameter der Zeiger auf eine
Hashfunktion für ktype übergeben werden. Außerdem kann
die Anfangszahl der Eimer und der Load-Factor angegeben werden.
Die Hash-Funktion selbst wiederum hat als zweites Argument die aktuelle Anzahl
der Eimer, die sich ja im Lauf der Benutzung der Tabelle ändern kann.
Eine Hash-Funktion für int sähe beispielsweise wie
folgt aus:
- int hash_int(const int &i, int cp)
{
return i%cp;
}
Die wichtigsten Zugriffsfunktionen sind folgende:
void clear()
| | löscht alle Elemente (aber nicht die
Eimer)
| | bool isempty() const
| | | Nachfrage, ob die Tabelle leer ist
| | int size() const
| | | gibt die Anzahl der aktuell gespeicherten
Elemente zurück
| | void put(const ktype&, const dtype&)
| | | ein Element wird mit Schlüssel und Datum
eingefügt
| | bool get(const ktype &k, dtype &d) const
| | | ein Element wird über seinen Schlüssel k
gesucht und sein Datum in d zurückgegeben (liefert
false, falls kein solcher Schlüssel gefunden wurde)
| | bool remove(const ktype &k)
| | | ein durch seinen Schlüssel k angegebenes
Element wird gelöscht (liefert false, falls kein
solcher Schlüssel gefunden wurde)
| | bool containskey(const ktype &k) const
| | | Nachfrage, ob ein bestimmter Schlüssel
k enthalten ist (schnell durch die Hash-Funktion)
| | bool contains(const dtype &d) const
| | | Nachfrage, ob ein bestimmtes Datum d
enthalten ist (Vorsicht: die gesamte Tabelle muß durchsucht
werden!)
| |
Die gesamte Hash-Tabelle kann außerdem mit Hilfe eines Cursors (in einer
Richtung) durchlaufen werden. Die Reihenfolge ergibt sich aus
Hashcode-Reihenfolge der Listen und der Elementreihenfolge innerhalb
der Listen. Nach einer Umstrukturierung der Hashtabelle können sich
alle Positionen geändert haben, weswegen der Cursor dann wieder auf
das (neue) erste Element gesetzt wird.
Es gibt folgende Cursor-bezogene Memberfunktionen:
void csr_start()
| | setzt den Cursor auf das erste Element
| | bool csr_moveto(const ktype &k)
| | | setzt den Cursor auf das erste Element mit dem
Schlüssel k (liefert false, falls kein
solcher Schlüssel gefunden wurde)
| | bool csr_get(ktype &k, dtype &d) const
| | | liest Schlüssel und Daten aus dem Element unter dem
Cursor nach k bzw. d (liefert false bei
undefiniertem Cursor)
| | bool csr_next()
| | | setzt den Cursor auf das nächste Element
(liefert false, falls der Cursor auf dem letzten Element
stand)
| | bool csr_change(const dtype&)
| | | ändert das Datum unter dem Cursor -- der
Schlüssel kann sinnvollerweise nicht verändert werden
(liefert false bei undefiniertem Cursor)
| |
Implementation:
Für die Listenknoten verwenden wir das Template hashentry mit
Schlüssel, Datum und Verzeigerung. Da die meisten Compiler Probleme
bei verschachtelten Templates machen, ist es aus dem Template
hashtable ausgelagert. etype ist eine Abkürzung für
diesen Knotentyp.
Als Datenmember von hashtable haben wir
außer loadfactor und dem Funktionspointer phashfunc
noch die Anzahl der Eimer (capacity), die Anzahl der aktuell
gespeicherten Daten (entries) sowie die Maximalanzahl bezüglich
des Load-Factors (maxentries). hasharray ist ein Zeiger auf
das Array mit den Listen-Anfängen.
Der Cursor ist mit Hilfe der beiden Datenmember csr_anchor (Nummer!
des Eimers) und csr_entry (Zeiger auf den Listenknoten) implementiert.
Die private Funktion getanchor bestimmt unter Verwendung der
Hash-Funktion den Anfang der Liste, in der sich ein gegebenes Element
befinden muß, gethandle einen Zeiger auf die Stelle, an der
ein Element eingehängt ist.
Die Funktion isprime prüft, ob eine gegebene Zahl Primzahl ist.
Sie wird verwendet, wenn die Tabelle vergrößert werden muß. Da
das nicht besonders oft der Fall sein wird, ist sie sehr einfach implementiert.
Sie ist nicht (als static) in die Klasse aufgenommen worden, da
sie nicht von den variablen Typen abhängt und sonst unnötigerweise
für jede Instanz erneut erzeugt werden würde.
Die Templates selbst erzeugen ja nicht direkten Maschinencode, nur die
einzelnen Instanzen. Deshalb ist der komplette Quelltext gut in einer
Header-Datei aufgehoben. Es folgt _hash.h:
- #ifndef _HASH_H
#define _HASH_H
#include <iostream.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
bool isprime(int p)
{
if ( p<=3) return p>=2;
if ( (p&1)==0 || p%3==0 ) return false;
int lim=(int)sqrt((double)p);
for ( int i=5 ; i<=lim ; i+=6 )
if ( p%i==0 || p%(i+2)==0 ) return false;
return true;
}
template <class ktype, class dtype>
struct hashentry
{
ktype key;
dtype value;
hashentry *next;
hashentry(const ktype &k, const dtype &v) : key(k), value(v), next(0) {}
};
template <class ktype, class dtype>
class hashtable
{
private:
typedef hashentry<ktype,dtype> etype;
typedef int (*phashfunc)(const ktype&,int);
int capacity;
double loadfactor;
etype **hasharray;
int entries;
int maxentries;
phashfunc hashfunc;
int csr_anchor;
etype *csr_entry;
void init();
void copyarray(const hashtable&);
void rehash();
etype *&getanchor(const ktype &k) const
{ return hasharray[hashfunc(k,capacity)]; }
etype **gethandle(const ktype &) const;
public:
hashtable(phashfunc, int=101, double=0.75);
hashtable(const hashtable &h2)
: capacity(h2.capacity), loadfactor(h2.loadfactor), entries(h2.entries),
hashfunc(h2.hashfunc), csr_anchor(-1), csr_entry(0)
{ init(); copyarray(h2); }
~hashtable() { clear(); delete[] hasharray; }
void clear();
hashtable & operator = (const hashtable&);
bool isempty() const { return entries==0; }
int size() const { return entries; }
bool contains(const dtype&) const;
bool containskey(const ktype &key) const { return gethandle(key)!=0; }
bool get(const ktype&, dtype&) const;
void put(const ktype&, const dtype&);
bool change(const ktype&, const dtype&);
bool remove(const ktype&);
void csr_start() { csr_anchor=-1; csr_next(); }
bool csr_moveto(const ktype &);
bool csr_get(ktype &, dtype &) const;
bool csr_next();
bool csr_change(const dtype &);
friend ostream & operator << (ostream&, const hashtable&);
};
template <class ktype, class dtype>
hashtable<ktype,dtype>::hashtable(int (*hf)(const ktype&,int),int cp,double lf)
: capacity(cp), loadfactor(lf), entries(0), hashfunc(hf),
csr_anchor(-1), csr_entry(0)
{
if (capacity<5) capacity=5;
if (loadfactor<1.0/capacity) loadfactor=1.0/capacity;
init();
}
template <class ktype, class dtype>
void hashtable<ktype,dtype>::init()
{
while (!isprime(capacity)) ++capacity;
maxentries=(int)(capacity*loadfactor);
hasharray=new(etype*)[capacity];
etype **P=hasharray;
for (int i=0;i<capacity;++i) *P++=0;
}
template <class ktype, class dtype>
void hashtable<ktype,dtype>::copyarray(const hashtable<ktype,dtype> &h2)
{
for (int i=0;i<capacity;++i)
{
etype **PE=&hasharray[i];
etype *E=h2.hasharray[i];
while (E!=0)
{
*PE=new etype(E->key,E->value);
PE=&(*PE)->next;
E=E->next;
}
}
if ((csr_anchor=h2.csr_anchor)>=0)
{
hashentry<ktype,dtype> *P=h2.hasharray[h2.csr_anchor];
int count=0;
while (P!=csr_entry) { ++count; P=P->next; }
csr_entry=hasharray[csr_anchor];
while (--count>0) csr_entry=csr_entry->next;
}
}
template <class ktype, class dtype>
hashtable<ktype,dtype>& hashtable<ktype,dtype>::operator = (const hashtable &h2)
{
clear();
delete[] hasharray;
capacity=h2.capacity;
loadfactor=h2.loadfactor;
entries=h2.entries;
init();
copyarray(h2);
return *this;
}
template <class ktype, class dtype>
void hashtable<ktype,dtype>::clear()
{
for (int i=0;i<capacity;++i)
{
etype *P1=hasharray[i],*P2;
while (P1!=0)
{
P2=P1->next;
delete P1;
P1=P2;
}
}
entries=0;
csr_anchor=-1;
}
template <class ktype, class dtype>
hashentry<ktype,dtype>
**hashtable<ktype,dtype>::gethandle(const ktype &k) const
{
int anchor=hashfunc(k,capacity);
etype **PE=&hasharray[anchor];
while (*PE!=0)
{
if ((*PE)->key==k) return PE;
PE=&(*PE)->next;
}
return 0;
}
template <class ktype, class dtype>
void hashtable<ktype,dtype>::rehash()
{
int i;
etype **P;
int oldcapacity=capacity;
int oldentries=entries;
etype **oldarray=hasharray;
capacity=(((int)(capacity/(0.95*loadfactor)))&(-2))+1;
init();
entries=0;
for (i=0,P=oldarray;i<oldcapacity;++i)
{
etype *E=*P++,*E2;
while (E!=0)
{
E2=E->next;
etype **anchor=&getanchor(E->key);
E->next=*anchor;
*anchor=E;
E=E2;
}
}
entries=oldentries;
csr_start();
}
template <class ktype, class dtype>
void hashtable<ktype,dtype>::put(const ktype &key, const dtype &value)
{
etype *newentry=new etype(key,value);
(void)getanchor(key);
etype **anchor=&getanchor(key);
newentry->next=*anchor;
*anchor=newentry;
if (++entries>maxentries) rehash();
}
template <class ktype, class dtype>
bool hashtable<ktype,dtype>::remove(const ktype &key)
{
etype **E=gethandle(key);
if (E!=0)
{
if (*E==csr_entry) csr_next();
etype *kill=*E;
*E=(*E)->next;
delete kill;
--entries;
return true;
}
return false;
}
template <class ktype, class dtype>
bool hashtable<ktype,dtype>::contains(const dtype &value) const
{
etype **P;
for (int i=0,P=hasharray;i<capacity;++i)
{
etype *E=*P++;
while (E!=0)
{
if (E->value==value) return true;
E=E->next;
}
}
return false;
}
template <class ktype, class dtype>
bool hashtable<ktype,dtype>::get(const ktype &key, dtype &value) const
{
etype **PE=gethandle(key);
if (PE==0) return false;
value=(*PE)->value;
return true;
}
template <class ktype, class dtype>
bool hashtable<ktype,dtype>::change(const ktype &key, const dtype &value)
{
etype **PE=gethandle(key);
if (PE==0) return false;
(*PE)->value=value;
return true;
}
template <class ktype, class dtype>
bool hashtable<ktype,dtype>::csr_change(const dtype &value)
{
if (csr_anchor<0) return false;
csr_entry->value=value;
return true;
}
template <class ktype, class dtype>
bool hashtable<ktype,dtype>::csr_get(ktype &key, dtype &value) const
{
if (csr_anchor<0) return false;
key=csr_entry->key;
value=csr_entry->value;
return true;
}
template <class ktype, class dtype>
bool hashtable<ktype,dtype>::csr_next()
{
if ( csr_anchor<0 || (csr_entry=csr_entry->next)==0 )
do
if (++csr_anchor==capacity) { csr_anchor=-1; return false; }
while ( (csr_entry=hasharray[csr_anchor]) ==0 );
return true;
}
template <class ktype, class dtype>
bool hashtable<ktype,dtype>::csr_moveto(const ktype &key)
{
hashentry<ktype,dtype> **PE=gethandle(key);
if (PE==0) { csr_anchor=-1; return false; }
else { csr_anchor=hashfunc(key,capacity); csr_entry=*PE; return true; }
}
template <class ktype, class dtype>
ostream & operator << (ostream &o, const hashtable<ktype,dtype> &ht)
{
hashentry<ktype,dtype> **anchor=ht.hasharray,*P;
for (int i=0;i<ht.capacity;++i)
if ((P=*anchor++)!=0)
do
o << P->key << ",\t" << P->value << endl;
while ((P=P->next)!=0);
}
#endif
Das folgende kurze Testprogramm hashtest.cpp
erzeugt 500 zufällige Paare von Vor- und
Nachnamen, hasht sie in die Tabelle und gibt die fertige Tabelle aus.
Die Tabelle nimmt dabei nacheinander folgende Größen an:
101, 149, 211, 307, 431, 607, 853.
Danach können einzelne Einträge (über den Nachnamen)
gelöscht werden.
- #include "_hash.h"
#include "_string.h"
#include <stdlib.h>
#include <ctype.h>
#include <time.h>
int hash_string(const string &s, int cp)
{
int hash=strlen(s);
for (int i=hash-1;i>=0;--i)
hash=13*hash+(int)s[i];
return (hash&INT_MAX)%cp;
}
string RandomName(int maxlen)
{
string s(maxlen);
int mode=rand()&1;
for (int i=4+(rand()%(maxlen-3));i>0;--i)
{
s+=(mode&1)?"aeiouy"[rand()%6]:"bcdfghjklmnpqrstvwxz"[rand()%20];
if ((rand()&15)!=15) ++mode;
}
s[0]=toupper(s[0]);
return s;
}
void main()
{
hashtable<string, string> h(hash_string);
srand(time(0));
for (int i=0;i<500;++i)
h.put(RandomName(10),RandomName(10));
for (;;)
{
cout << h;
cout << h.size() << " entries\n";
string s1,s2;
cout << "last name: ";
cin >> s1;
if (s1=="quit") break;
if (h.get(s1,s2)) cout << s1 << " found, first name: " << s2 << endl;
else cout << "last name " << s1 << " not found\n";
h.remove(s1);
}
}
16.3.2: Restklassen-Klassen
