Design Hashtabelle

Nirvash

Guten Abend,

in meinem kleinen Projekt habe ich zur Zeit eine Hashtabelle implementiert. Für die Initialisierung muss eine Größe der Hashtabelle angegeben werden. Für eine bestmöglichste Verteilung der Hash-Werte sollte diese Größe einer Primzahl entsprechen.
An dieser Stelle kommt bei mir die Frage auf, wie lassen sich Hashtabellen entwerfen, deren Größe nicht vorbestimmt bzw. an eine gewisse Speichergröße gebunden ist?
Angenommen ich möchte in meiner Hashtabelle 20 Elemente speichern, muss ich dann vorher die nächst höhere Primzahl suchen oder gibt es dafür andere Verfahren?

Meine bisherigen Suchergebnisse haben mich nur auf Hashtabellen mit einer Primzahlgröße geführt.

Die Grösse der Hashtable muss überhaupt keine Primzahl sein.

Es ist die Aufgabe der Hashfunktion die Werte schön zufällig zu verteilen. Die Tashtable kann jede beliebige Grösse nehmen. In der Praxis werden oft Zweierpotenzen genommen ( https://en.wikipedia.org/wiki/Hash_table ). Sobald die Tabelle voll ist (Anzahl Elemente * 2 = Anzahl Buckets oder so) wächst sie geometrisch (oft auch Faktor 2).

Wenn du schon weisst, dass es 20 Elemente werden sollen, dann kannst du gleich die Grösse 20 nehmen. Der Index ist dann hash(wert)%20.

volkard

Nirvash schrieb:

Guten Abend,
in meinem kleinen Projekt habe ich zur Zeit eine Hashtabelle implementiert. Für die Initialisierung muss eine Größe der Hashtabelle angegeben werden. Für eine bestmöglichste Verteilung der Hash-Werte sollte diese Größe einer Primzahl entsprechen.

Sicher? Viele Hastables haben diese Beschränkung gar nicht. Und die, die sie haben, wünchen sich gerne einen oberen Primzahlenzwilling. Ah, Du willst als Hashfunktion einfach x%SIZE nehmen. Das ist unüblich. Meinstens hat man ja Typen, die nicht nur gerade ein uint sind, und die jagt man erst durch eine zu diesem Typen passende Hashfunktion, es wird hash(x)%size. Dann hat die Hashfunktion gefälligst gut zu sein und es reicht, size beliebig (gerne als Zweierpotenz) zu wählen.

Nirvash schrieb:

An dieser Stelle kommt bei mir die Frage auf, wie lassen sich Hashtabellen entwerfen, deren Größe nicht vorbestimmt bzw. an eine gewisse Speichergröße gebunden ist?

Normalerweise können sie wachsen. Aber beim Wachsen werden alle Elemente neu gehasht und in die neue normal eingefügt, was ein wenig dauert. Ist aber selten, daß es passieren muss.

Nirvash schrieb:

Angenommen ich möchte in meiner Hashtabelle 20 Elemente speichern, muss ich dann vorher die nächst höhere Primzahl suchen

Ja. Fast immer. Diese mit den Primzahlenzwillingen haben üblicherweise irgendwo ein globales Array von guten vorberechten Primzahlen und hangeln sich beim Wachsen an dem Array hoch.

Nirvash schrieb:

oder gibt es dafür andere Verfahren?

Auch die gibt es. http://en.wikipedia.org/wiki/Extendible_hashing (auch "Extensible hash table"). Die sind aber meistens gar nicht so einfach zu implemetieren, wenn man einigermaßen schnell bleiben will. Den Hammer würde ich erst auspacken, wenn die Daten persistent in einer Datei liegen.

Nirvash schrieb:

Meine bisherigen Suchergebnisse haben mich nur auf Hashtabellen mit einer Primzahlgröße geführt.

Ich denke, Du solltest "cockoo hashing" anschauen. Und auf der anderen Seite natürlich auch in Erwägung ziehen, daß die Hashtable nur Startzeiger auf einfach verkettete Listen sind, wenn malloc/free schnell sind (kannste ja noch mit blockweisem Vorausallokieren und gegebenenfalls Freispeicherliste auf wenige Takte drücken), ist das auch gangbar.

Und wenn die Lese-Zugriffe die Schreibzugriffe *deutlich* überwiegen (wozu sonst Hashtables!) ist eh alles halb so wild. Kuckuck grüßt und behauptet, schnell zu sein.

Die sind aber alle recht fix, aber kacken auch alle unglaublich ab, wenn die benutzerdefinierte Hashfunktion hash(x) kacke ist. Die sollte nicht nur geraten werden, sondern auch gegen ein paar Alternativ-Implemetierungen ausgemessen werden.

Nirvash

Einsatz der Hash-Tabelle soll eine Lookup-Tabelle für Variablen innerhalb eines Parsers sein. Zur Zeit gehe ich davon aus, dass maximal 13 Variablen pro Scope definiert werden können (kleine Sprache).
Damit die Sprache und der Compiler später einfach erweitert werden können, wollte ich mir jetzt schonmal vernünftig Gedanken um eine Hashtabelle machen.

Zur Vermeidung von Kollisionen habe ich bisher auf doppeltes Hashing zurückgegriffen:

Erste\ Hashfunktion: h(k) := (h(k) * 128 + k)\;mod\;HASH\_SIZE \\ Zweite\ Hashfunktion: h'(k) := (h'(k) * 128 + k)\;mod\;HASH\_SIZE - 2 \\ Im\ Falle\ einer\ Kollision: h(k, i) := (h(k) + i * h'(k))\;mod\;HASH\_SIZE

habmichverfahren schrieb:

Die Grösse der Hashtable muss überhaupt keine Primzahl sein.

Es ist die Aufgabe der Hashfunktion die Werte schön zufällig zu verteilen. Die Tashtable kann jede beliebige Grösse nehmen. In der Praxis werden oft Zweierpotenzen genommen ( https://en.wikipedia.org/wiki/Hash_table ). Sobald die Tabelle voll ist (Anzahl Elemente * 2 = Anzahl Buckets oder so) wächst sie geometrisch (oft auch Faktor 2).

Wenn du schon weisst, dass es 20 Elemente werden sollen, dann kannst du gleich die Grösse 20 nehmen. Der Index ist dann hash(wert)%20.

Das leuchtet mir ein, ich muss vorher dann also die Hashfunktion so wählen, dass vernünftige, möglichst kollisionsarme Werte berechnet werden.

volkard schrieb:

Ja. Fast immer. Diese mit den Primzahlenzwillingen haben üblicherweise irgendwo ein globales Array von guten vorberechten Primzahlen und hangeln sich beim Wachsen an dem Array hoch.

Ausgenommen Mersenne-Primzahlen habe ich solche Zwillingspaare auch für mein doppeltes Hashing vorgesehen.

volkard schrieb:

Ich denke, Du solltest "cockoo hashing" anschauen. Und auf der anderen Seite natürlich auch in Erwägung ziehen, daß die Hashtable nur Startzeiger auf einfach verkettete Listen sind, wenn malloc/free schnell sind (kannste ja noch mit blockweisem Vorausallokieren und gegebenenfalls Freispeicherliste auf wenige Takte drücken), ist das auch gangbar.

Und wenn die Lese-Zugriffe die Schreibzugriffe *deutlich* überwiegen (wozu sonst Hashtables!) ist eh alles halb so wild. Kuckuck grüßt und behauptet, schnell zu sein.

Die sind aber alle recht fix, aber kacken auch alle unglaublich ab, wenn die benutzerdefinierte Hashfunktion hash(x) kacke ist. Die sollte nicht nur geraten werden, sondern auch gegen ein paar Alternativ-Implemetierungen ausgemessen werden.

Das "cockoo hashing" scheint mir sehr dem doppelten Hashing zu ähneln. Werde mir das also mal näher anschauen und ein paar Implementierungen testen.

Bezüglich der Größe scheinen sich mir gerade eure beiden Aussagen zu wiedersprechen?

User1291

Nirvash schrieb:

Zur Vermeidung von Kollisionen habe ich bisher auf doppeltes Hashing zurückgegriffen:
Erste\ Hashfunktion: h(k) := (h(k) * 128 + k)\;mod\;HASH\_SIZE \\ Zweite\ Hashfunktion: h'(k) := (h'(k) * 128 + k)\;mod\;HASH\_SIZE - 2

Moment mal, die Hashfunktionen h und h' sind bei dir also rekursiv und ohne Abbruch definiert?
Das kann nicht richtig sein.

wie lassen sich Hashtabellen entwerfen, deren Größe nicht vorbestimmt bzw. an eine gewisse Speichergröße gebunden ist?

Sobald nötig neue (evtl. grössere) Hashtabelle anlegen und rehashen, hätt ich jetzt behauptet.
An dieser Stelle: Wie gehst du denn momentan mit unauflösbaren Kollisionen um?

Nirvash

Der Hashwert wird für Strings berechnet, siehe die Funktion unten.

Die "dritte" Hashfunktion besitzt einen Iterator i. Dieser wird solange hochgezählt, bis ein freier Platz gefunden wurde. Beim Testen konnte bisher die Tabelle immer gefüllt werden. Sollte die Tabelle voll sein, bricht die Schleife ab.

Hier die Funktion zur Generierung eines Hashwertes:

static unsigned genHashKey(HASHTABLE hash, char *s) {
size_t hashval1, hashval2, hashkey, i;

for (hashval1 = hashval2 = 0; *s != '\0'; s++) {
hashval1 = ((hashval1 << 7) + *s) % hash->HASH_SIZE;
hashval2 = ((hashval2 << 7) + *s) % (hash->HASH_SIZE - 2);
}

hashkey = hashval1;

for (i = 0; (hash->table[hashkey] == NULL || strcmp(hash->table[hashkey], s)) && i < hash->HASH_SIZE; i++)
hashkey = (hashval1 + i * hashval2) % hash->HASH_SIZE;

hash->used++;
return hashkey;
}

volkard

for (i = 0; (hash->table[hashkey] == NULL || strcmp(hash->table[hashkey], s)) && i < hash->HASH_SIZE; i++)

Weniger Wolf und viel mehr Knuth. (Man als Fremder mag das nicht lesen. Lieber ein wenig if in den Schleifen. Der Compiler optimiert die ifs schon hoch, keine Bange.) Lass uns die Augen auf den Algo werfen.

Nirvash

volkard schrieb:

for (i = 0; (hash->table[hashkey] == NULL || strcmp(hash->table[hashkey], s)) && i < hash->HASH_SIZE; i++)
Weniger Wolf und viel mehr Knuth. (Man als Fremder mag das nicht lesen. Lieber ein wenig if in den Schleifen. Der Compiler optimiert die ifs schon hoch, keine Bange.) Lass uns die Augen auf den Algo werfen.

Ok, also mein bisheriger Algorithmus mit doppeltem Hashing in Pseudocode:

h(k) = h'(k) = 0
m = Größe Hashtabelle
for (; *s != '\0'; s++) {
    h(k) = ((h(k) * 128) + *s) mod m;            // Hashfunktion 1
    h(k) = ((h'(k) * 128) + *s) mod (m - 2);     // Hashfunktion 2
}

if ist h(k) frei
    return h(k)

for (i = 0; i < Größe Hashtabelle; i++) {
    h(k, i) = (h(k) + i * h'(k)) mod m           // Sondierungsfunktion
    if ist h(k, i) frei
        return h(k, i)
    if *s an stelle von h(k, i)
        return h(k, i)
}

Habe mich mal etwas in das Cuckoo-Hashing eingelesen. Sieht sehr spannend aus, jedoch an manchen Stellen auch problematisch, gerade wegen der Gefahr des unendlichen Zyklus. Alternativen dies durch einen Notfall-Chache oder eine Insert-Queue zu erweitern scheinen da Ablöse zu liefern, doch befürchte ich dann einen gewissen Overhead für eine Symboltabelle zu erzeugen.

volkard

Dein Pseudocode ist irgendwie nicht eindeutig. Kann daraus nicht erkennen, wie der C-Code aussehen würde, obwohl ich sowas jahrelang mache.

Nirvash schrieb:

gewissen Overhead für eine Symboltabelle zu erzeugen.

*zack* !!
Symboltabelle

Aha, darum geht es. Wirst gegen einen normalen Baum keine sichtbare Geschwindigkeit dazukriegen. Dazu sind die Lookups in die Symboltabelle zu selten und die Optimierungen zu schwer. Aber Naja, man gibt sich ja keine Blöße und geht aufs Ganze: Hier hätte ich an einen Baum gedacht (, an einen Drei-Wege-Baum sogar, oder 16-Wege, aber das tut nix zu Sache). Baum, damit der lokale Kontext sich nahtlos auf den Baum pflanzen kann und wenn er verschwindet, dann ist der Restbaum effektiv wie immer. Aus Hashtables kannste da nicht gut löschen. Nur so ein Gedanke.

Nirvash

volkard schrieb:

*zack* !!
Symboltabelle

Aha, darum geht es. Wirst gegen einen normalen Baum keine sichtbare Geschwindigkeit dazukriegen. Dazu sind die Lookups in die Symboltabelle zu selten und die Optimierungen zu schwer. Aber Naja, man gibt sich ja keine Blöße und geht aufs Ganze: Hier hätte ich an einen Baum gedacht (, an einen Drei-Wege-Baum sogar, oder 16-Wege, aber das tut nix zu Sache). Baum, damit der lokale Kontext sich nahtlos auf den Baum pflanzen kann und wenn er verschwindet, dann ist der Restbaum effektiv wie immer. Aus Hashtables kannste da nicht gut löschen. Nur so ein Gedanke.

Das macht mich jetzt etwas stutzig, da mir bisherige Lektüren (Drachenbuch, Compilerbau von Niklaus Wirth) immer Hashtabellen für Symboltabellen empfohlen haben.

Implementationstechnisch hatte ich mir das bisher so vorgestellt:

Pro Scope wird eine Hashtabelle angelegt, welche alle Symbole innerhalb des Scopes speichert. Diese Hashtabellen sind in einem Stack gespeichert. Innerhalb der Hashtabelle werden nur die Referenzen auf die Symbole verwalten, nicht die Symbole selbst. Wird ein neuer Scope betreten, wird eine neue Hashtabelle angelegt und alle neuen Referenzen der Deklarationen wandern in die Hashtabelle. Aufrufe innerhalb des Scopes werden in der oberen Hashtabelle auf Existenz geprüft, sind diese nicht im aktuellen Scope vorhanden, wird eine Stufe darunter gesucht usw. bis zum Main-Scope. Neben dem Parsen wird ein AST angelegt, welcher auf die Symbole bei Vorkommen referenziert. Wird der Scope verlassen, wird die Hashtabelle als Referenzverwalter gelöscht und die Hashtabelle des darunterliegenden Scopes wird nun aktuell.

volkard

Meine Gedanke, daß man aus Bäumen gut löschen könnte, war Quark. Sorry. Dazu müßte man die Knoten pro Scope noch in einem intrusiven doppelt verketteten Ring auffädeln.

Aus Messungen weiß ich, daß allgemein einsetzbare Bäume wie die std::map aus C++ den allgemein einsetzbaren Hashtables kaum nachhinken.
Hier haben die Hashtables wohl die Nase vorn, man kann sie schlagartig löschen, sie sind höflich zum Cache, sie kacken nicht ab, wenn der Benutzer den global scope mit 1000000 Bezeichnern vollmüllt.

Implementationstechnisch hatte ich mir das bisher so vorgestellt:

Pro Scope wird eine Hashtabelle angelegt, welche alle Symbole innerhalb des Scopes speichert. Diese Hashtabellen sind in einem Stack gespeichert. Innerhalb der Hashtabelle werden nur die Referenzen auf die Symbole verwalten, nicht die Symbole selbst. Wird ein neuer Scope betreten, wird eine neue Hashtabelle angelegt und alle neuen Referenzen der Deklarationen wandern in die Hashtabelle. Aufrufe innerhalb des Scopes werden in der oberen Hashtabelle auf Existenz geprüft, sind diese nicht im aktuellen Scope vorhanden, wird eine Stufe darunter gesucht usw. bis zum Main-Scope. Neben dem Parsen wird ein AST angelegt, welcher auf die Symbole bei Vorkommen referenziert. Wird der Scope verlassen, wird die Hashtabelle als Referenzverwalter gelöscht und die Hashtabelle des darunterliegenden Scopes wird nun aktuell.

Das klingt lecker.

Bin aber nicht sicher, daß das das Optimum darstellt. Mit steigender Anzahl der Scopes, wird die Lösung linear langsamer.
Aber eine Funktion kann ja gar nicht in den Scope der aufrufenden Funktion gucken, sondern nur in ihren Datei-Scope und danach in den globalen. Die lokalen werden nicht zum Suchen aneinandergehängt, sondern der neue lokale ersetzt den alten.

(ein wenig tiefer, weil fasrt schon abwegig)
Man könnte das Löschproblem vielleicht per copy-on-write-pages lösen.

Nirvash

volkard schrieb:

Bin aber nicht sicher, daß das das Optimum darstellt. Mit steigender Anzahl der Scopes, wird die Lösung linear langsamer.
Aber eine Funktion kann ja gar nicht in den Scope der aufrufenden Funktion gucken, sondern nur in ihren Datei-Scope und danach in den globalen. Die lokalen werden nicht zum Suchen aneinandergehängt, sondern der neue lokale ersetzt den alten.

(ein wenig tiefer, weil fasrt schon abwegig)
Man könnte das Löschproblem vielleicht per copy-on-write-pages lösen.

Genau das war auch mein Gedanke dabei. Natürlich wird es länger dauern ein Symbol im Main Scope abzufragen, wenn die 10 Scopes dahinter liegt. Jedoch handelt es sich erstmal nur um eine sehr rudimentäre Sprache und selbst bei einer größeren Sprache stelle ich mir das nicht so problematisch vor, da ja nur der Zugriff auf die einzelnen Scopes linear Komplex ist.

Hatte mir vorher viele Gedanken gemacht das optimal gut zu lösen. Denkbar wären auch Bäume gewesen, doch da stellt sich wieder die Frage, wie den Baum aufbauen, wenn die Suche nach Symbolen aus einem Scope linear bis zum Main-Scope verläuft.

volkard schrieb:

Bin aber nicht sicher, daß das das Optimum darstellt. Mit steigender Anzahl der Scopes, wird die Lösung linear langsamer.

Das Optimum wäre eine einzige Wegwerf-Hashtabelle.

Der globale Scope ist eine eigene Hashtabelle, da er sich wenig ändert und schnell verfügbar sein soll.

Im lokalen Scope geht aber mehr:
Erst geben wir jedem Scope eine eindeutige Zahl. Mal als Beispiel:

{ // 1
  { // 2
  }
  { // 3
  }
  { // 5 (es sind alles Primzahlen plus die 1)
    { // 35 = 5*7 (7 ist nächste Primzahl)
    }
  }
  { // 11 (weil 7 schon oben benutzt
    { // 143 (11*13)
      { // 11*13*17
      }
    }
  }
}

Der Trick dabei ist, dass bei gegebenen Scope-Zahlen sofort entschieden werden kann, ob der eine Scope direkt über dem anderen liegt. 1 teilt alles. 5 teilt 35 => 35 ist unter 5 genested. 11 teilt 11*13*17 => 11 ist ein Unterscope von 11*13*17.

Mit dem Trick kann man jedem Eintrag in der Hashtabelle ein Ablaufdatum (ein Tag) zuweisen. Variable x im Scope mit der Zahl y bekommt den Eintrag (x,y) (y wird nicht mitgehasht).

Tritt man in einen neuen Scope ein, wird nur die Scopezahl geändert (=Lookup in Primzahlentabelle). Wird eine Variable eingeführt, schaut man in der Hash-Tabelle unter dem Namen nach, ist die Scopezahl ein Vielfaches des Tags, dann fügen wir den neuen Namen vorher in der Liste ein. Ist die Scopezahl kein Vielfaches, löschen wir sie und suchen weiter.

Bei einer Abfrage machen wir ein Lookup, löschen abgelaufene Namen und nehmen den erstbesten Match. Weil wir tiefer genestete Namen am Anfang einfügen, geht das.

Gibt man jedem Eintrag noch eine Funktions-ID mit kann man eine einzige grosse Tabelle für alle Funktionen nehmen. Man müsste den Speicher nicht einmal löschen, man kann ja überprüfen, ob der Eintrag noch aktuell ist und löscht ihn bei Bedarf.

Sieht für mich nicht nur algorithmisch überlegen aus, sondern auch Cache-effizienter. Es werden wenig halb-leere Hashtabellen erstellt und deshalb muss so gut wie nie Memory allokiert werden.

volkard

Eigentlich kann man aus Hashtables nicht gut löschen. Oder man baut eine, die umständlich und lahm ist, damit man löschen kann.

Aber wenn man genau in umgekehrter Einfügereihenfolge aus einer schlichten Hashtable löscht, macht sie es nicht kaputt.

Nirvash

fasrt schrieb:

volkard schrieb:

Bin aber nicht sicher, daß das das Optimum darstellt. Mit steigender Anzahl der Scopes, wird die Lösung linear langsamer.

Das Optimum wäre eine einzige Wegwerf-Hashtabelle.

Der globale Scope ist eine eigene Hashtabelle, da er sich wenig ändert und schnell verfügbar sein soll.

Im lokalen Scope geht aber mehr:
Erst geben wir jedem Scope eine eindeutige Zahl. Mal als Beispiel:
{ // 1
  { // 2
  }
  { // 3
  }
  { // 5 (es sind alles Primzahlen plus die 1)
    { // 35 = 5*7 (7 ist nächste Primzahl)
    }
  }
  { // 11 (weil 7 schon oben benutzt
    { // 143 (11*13)
      { // 11*13*17
      }
    }
  }
}
Der Trick dabei ist, dass bei gegebenen Scope-Zahlen sofort entschieden werden kann, ob der eine Scope direkt über dem anderen liegt. 1 teilt alles. 5 teilt 35 => 35 ist unter 5 genested. 11 teilt 11*13*17 => 11 ist ein Unterscope von 11*13*17.

Mit dem Trick kann man jedem Eintrag in der Hashtabelle ein Ablaufdatum (ein Tag) zuweisen. Variable x im Scope mit der Zahl y bekommt den Eintrag (x,y) (y wird nicht mitgehasht).

Tritt man in einen neuen Scope ein, wird nur die Scopezahl geändert (=Lookup in Primzahlentabelle). Wird eine Variable eingeführt, schaut man in der Hash-Tabelle unter dem Namen nach, ist die Scopezahl ein Vielfaches des Tags, dann fügen wir den neuen Namen vorher in der Liste ein. Ist die Scopezahl kein Vielfaches, löschen wir sie und suchen weiter.

Bei einer Abfrage machen wir ein Lookup, löschen abgelaufene Namen und nehmen den erstbesten Match. Weil wir tiefer genestete Namen am Anfang einfügen, geht das.

Gibt man jedem Eintrag noch eine Funktions-ID mit kann man eine einzige grosse Tabelle für alle Funktionen nehmen. Man müsste den Speicher nicht einmal löschen, man kann ja überprüfen, ob der Eintrag noch aktuell ist und löscht ihn bei Bedarf.

Sieht für mich nicht nur algorithmisch überlegen aus, sondern auch Cache-effizienter. Es werden wenig halb-leere Hashtabellen erstellt und deshalb muss so gut wie nie Memory allokiert werden.

Die Idee gefällt mir, nur muss ich eine Tabelle mit Primzahlen vorhalten und die Größe dieser Tabelle beschränkt meine maximale Anzahl an Scopes. Das gefällt mir daran nicht so, und selber nachfolgende Primzahlen berechnen zu lassen halte ich ab einer gewissen Größe für zu aufwendig und unpraktikabel.