Hashtabelle kreiren

Eine Hashtable wird nie größer, außer du wechselst mittendrin deine Hashfunktion (was sehr dumm wäre).
Du brauchst einfach ein Array mit Größe M, und jeder Eintrag davon beinhaltet eine verkettete Liste (die hat schon eine dynamische Größe).

zB

template <class T> struct Entry {
  T value;
  Entry *next;
};
template <class T> Entry<T> *hashtable[M];

Zitat von hal

Eine Hashtable wird nie größer, außer du wechselst mittendrin deine Hashfunktion (was sehr dumm wäre).

Die Hashing-Funktion kann ruhig die selbe bleiben. Aber wenn ich in eine Hashtable mit 10 Elementen schon 10.000 Elemente eingefügt habe ohne zu vergrößern ist der Vorteil der schnelle Lokalisierung eines Elements weg, da für jede Position der ganze Bucket durchsucht werden soll.

Schau mal z.B. auf http://en.wikipedia.org/wiki/Hash_table#Table_resizing.

Zitat von Ivy

Wenn also etwa bei einem statischen Hashverfahren die Tabelle den maximalen Belegungsfaktor (zb 0,7) überschreitet, so ist eine größere Tabelle anzulegen und die Werte sind neu zu hashen.

in dem fall musst du ein neues (größeres) M und damit eine neue hashfunktion (damit du die größere tabelle ausnutzen kannst) wählen sowie alle werte neu hashen. (siehe johnfoos link).

edit: 5.000ster post - spam ftw

Ok, da musst du dann einfach in deiner Hashfunktion dann den M-Parameter verändern, alle Elemente von der alten Liste auslesen und in die neue einfügen (dabei solltest du M logischerweise nicht nur um 1 erhöhen).

template <class T> struct hashtable {
  unsigned M;
  Entry<T> **table;
};


template <class T> hashtable<T> *createTable(int M) {
  hashtable<T> *table = new hashtable<T>;
  table->M = M;
  table->table = new Entry<T>*[M];
  return table;
}