Implementierung einer Hashtable

Phi*

Hallo zusammen,

kann mir jemand bei der Implementierung einer Hash Tabelle mit p=11 Listen weiterhelfen?

Ein Element sollte folgendermassen aussehen:

struct Tupel
{
   int key;
   string value;
   Tupel* chain_next;
};

Wobei zur Kollosionsverarbeitung der Zeiger

Tupel* chain_next

verwendet werden soll und die Hashfunktion

h(key)=key mod p

seien sollte.

Irgendwie habe ich letzte Woche den Stoff nämlich in der Uni verpasst...

Vielen Dank
Phil

leuchtturm

den parameter p gibts du am besten dem konstruktor der klasse mit. im konstruktor wird dann ein privates array A mit p elementen des typs struct Tupel angelegt -- und natürlich im destruktor wieder freigegeben. zur erkennung, ob eine liste leer ist oder nicht, kannst du z.b. den listenkopf unbenutzt lassen; in diesem fall gilt: die p-te liste ist genau dann leer, wenn A[p].chain_next == NULL. die hash funktion ist privat und wird nur von der einfüge-operation benutzt. die struktur kann dafür benutzt werden, zahlen auf ihre zeichenkettenrepräsentation zu mappen. ein einfügen hat dann die form hashtable.insert (1, "one");. insert macht folgendes:

-> den hashwert h des keys (1) ermitteln
-> falls in der h-ten liste der key schon vorhanden ist, dann überschreiben.
-> ansonsten einfach in die h-te liste einfügen

retrieve (int k) besorgt sich dann ebenfalls den hashwert h des keys k, und schaut dann in der h-ten liste nach, ob es ein listenelement e gibt mit e.key == k. wenn es ein solches element nicht gibt, pech gehabt. ansonsten e.value zurückgeben.

also irgendwie so:

struct Tupel { 
   int key; 
   string value; 
   Tupel* chain_next; 
};

class CHashTable {

private:
   Tupel  *data;
   int    p;
   int    hash (int key) { return key % p; }

public:
   CHashTable (int _p) : p(_p) { 
      data = new Tupel[p]; 
      for (int i=0; i<p; i++)
         data[i].chain_next = NULL;

   }
   ~CHashTable ()  { delete [] data; }
   bool insert (int key, string value) {...}

   bool delete (int key) {...}
   string retrieve (int key) {...}
};

ohne netz und doppeltem boden

-- leuchtturm

Mal ne dumme Frage:
Tut die Hash-Table nicht im Prinzip das gleiche wie std::map? Sieht für einen C++ Neuling nach einem assoziativem Array aus.

Bitte antwortet und haut nicht

Daumen hoch Herr Imperator!

Shade Of Mine

DummerHund schrieb:

Tut die Hash-Table nicht im Prinzip das gleiche wie std::map? Sieht für einen C++ Neuling nach einem assoziativem Array aus.

jein.
Eine hashmap ist genau wie std::map ein assoziativer Container.
Allerdings ist std::map als Baum implementiert und eine hashmap eben als hashmap

Ein Baum hat den Vorteil, dass der worst-case (also maximale Zeit die ein lookup des Schlüssels dauern kann) weit unter der einer Hashmap liegt. Der Nachteil eines Baumes ist aber, dass eine hashmap mit guter Hashfunktion schneller ist. Da man mit guter Hashfunktion viele Kollisionen vermeiden kann, und der 'worst-case' nicht ganz so schlimm ausfällt.

Bitte antwortet und haut nicht

so ne frechheit, jetzt darf man nicht mal mehr Leute schlagen die Fragen stellen...