hastable

Lenja

Hallo,

ich möchte eine Hashtabelle erstellen, weiß aber nicht so genau wie ich das mache.
So richtig habe ich auch leider hier nix weiter gefunden, was mir weiterhilft.

Ich habe eine Zahlenfolge als String und einen dazugehörigen berechneten Wert.
Nun möchte ich beide (also Folge und Wert) jeweils in die Tabelle speichern und abfragen, ob der die Zahlenfolge schon vorhanden ist (sodass ich den Wert nicht nochmal berechnen muss).

Kann mir vielleicht jemand (wenigstens ansatzweise) sagen, wie ich das anstelle?
Wäre echt nett

Schau dir doch mal std::map und dazu die Methode find() an!

__Stefan__

Mach ein Array von Kübeln. Um den richtigen Kübel zu berechnen, machst du Hashwert % anzahlKübel.

Stefan schrieb:

Mach ein Array von Kübeln. Um den richtigen Kübel zu berechnen, machst du Hashwert % anzahlKübel.

wobei Anzahl der Kübel eine Primzahl ist

Wenn er richtiges Hashing betreiben will, brauch er keine Kübel, sondern errechnet Ersatzpositionen

Warum gibt es eigentlich so viele Anhänger von Hashtables?

Ich persönlich bevorzuge eigentlich immer, wenn ich eine Ordnung habe oder die Adressen als Vergleich ausreichen, einen Baum...

So teuer ist der Vergleich ja i. d. R. nicht...

EDIT: Außerdem hat er in seinem Fall ja (scheinbar) eine konstant steigende Größe...

brotbernd

class NachGucker
{
public:
value_type GetValue(const std::string& s)
{
  Iter i = maeppchen.lower_bound(s);
  if(s == maeppchen.end() || i->first!= s)
    i = maeppchen.insert(i, make_pair(s, Value(s)));
  return i->second;
}
std::unordered_map<std::string, value_type> maeppchen;
};

Oder so ähnlich (nicht getestet, kann voller Fehler sein ;))...

volkard

CSpille schrieb:

Stefan schrieb:

Mach ein Array von Kübeln. Um den richtigen Kübel zu berechnen, machst du Hashwert % anzahlKübel.

wobei Anzahl der Kübel eine Primzahl ist

Nö! Natürlich eine Zweierpotenz, um keine Division zu erleiden.

Wenn er richtiges Hashing betreiben will, brauch er keine Kübel, sondern errechnet Ersatzpositionen  :clown:

Naja, je nach dem. Nur mit Ersatzpositionen fühlt es sich nur irgendwie "eleganter" an. Aber die Größe darf dann gerne ein oberer Primzahlenzwilling sein, denn Knuth hat gezeigt, daß bei Einsprung h%size und Suchsprungweite h%(size-2) praktisch keine Kollissionshäufung auftritt. Aber nur auf den Anfang einer verketteten Liste zu springen, ist auch extrem nett. Mit dem Ziel, die Tabelle so um 80% voll zu machen und mit gelegentlichen Überläufern zu leben. Die Überlaufknoten ruhig per new anlegen, lahmer als der Baum kann's nicht werden, solange die Hashfunktion hübsch ist.

Warum gibt es eigentlich so viele Anhänger von Hashtables?

Weil sie, wenn richtig angewandt, schon schweineschnell sind. Mir scheint, Du würdest eine bestimmte Weise stark bevorzugen. Schau Dir mal Cuckoo-Hashing an.

Ich persönlich bevorzuge eigentlich immer, wenn ich eine Ordnung habe oder die Adressen als Vergleich ausreichen, einen Baum...

Alle Generalisierungen sind falsch. (paradox)

So teuer ist der Vergleich ja i. d. R. nicht...

Wenn man mit Hashtables nicht schon ein paar mal auf die Nase gefallen ist, sollte man sie nicht benutzen. (paradox)

EDIT: Außerdem hat er in seinem Fall ja (scheinbar) eine konstant steigende Größe...

Weiß er ungefähr, wieviele es am Ende sein werden oder kann er eine gute Max-Anzahl wählen? Manche Hashtables haben auch nur geringe Wachstumsschmerzen.

@volkard:
Da ich dich persönlich für sehr kompetent halte, werde ich zukünftig wohl eher
eine hashmap in betracht ziehen.

Welche hashtables bzw. hashmap(s) verwendest du denn?
http://www.boost.org/doc/libs/1_35_0/doc/html/boost/intrusive/hashtable.html
???

Oder hast du Eigenimplementierungen?

Bezüglich Cuckoo-Hashing:
Klingt interessant!
Aber was passiert (theoretisch) wenn 3 Objekte exakt die gleichen Hashwerte
für beide Funktionen hätten. Dann geht ja gar nichts mehr, oder?

volkard

CSpille schrieb:

@volkard:
Da ich dich persönlich für sehr kompetent halte, werde ich zukünftig wohl eher
eine hashmap in betracht ziehen.

Vielen Dank.
Aber sei gewarnt. Es gibt Sachen, die sich prinzipiell gut hashen lassen, sagen wir mal IP-Adressen, und Sachen, wo es trotz bester Hash-Funktion auch mal unlecker wird. Strings sind da so eine Sache, sie müssen bis zum letzten Byte durchgerechnet werden von der Hashfunktion und dann bei Fund nochmal bis zum letzten Byte mit dem Suchstring verglichen.

CSpille schrieb:

Welche hashtables bzw. hashmap(s) verwendest du denn?
http://www.boost.org/doc/libs/1_35_0/doc/html/boost/intrusive/hashtable.html
???
Oder hast du Eigenimplementierungen?

Eigene, weil ich das wohl nur für recht spezielle Dinge mache. Und naja, um bestimmte Probleme drücke ich mich gerne. Manche Hashtables mögen es gar nicht gerne, wenn man Elemente rauslöscht. Da baue ich mir eine minimale Hashtable, die auch gar nicht löschen kann.

Für Settop-Boxes habe ich mal eine Hashtable gebaut, die zu integer-Zahlenfolgen einen integer speichern mußte und alle Ressourcen waren unglaublich knapp. Da habe ich nur ein Array von Tripeln aus Endzahl, Wert und Zeiger auf Präfix gespeichert, der Zeiger von 1.4.3.2 zeigt auf 1.4.3 und beim Hashen gehe ich durch die Zahlenfolge, finde den Wert in der Tabelle hangle mich zum Testen an den Zeigern zurück, dabei mit der Zahlenfolge vergleichend. Bei Nichttreffer normal mit Sprungweite hash%(size-2) und dem Primzahlenzwillingtrick.

Oder Lenja kann vielleicht auch vereinfachen. Immerhin sollen ja nur Berechnungen gespeichert werden! Die können zur Not erneut berechnet werden. Also vielleicht eine vereinfachte Hashtable nehmen, wo noich nichtmal beim Einfügen Kollissionen bereinigt werden, sondern ganz platt nur überschrieben wird. Also ein Cache-Speicher. Und bei Nichfinden wird halt doch neuberechnet.

Manchmal mache ich auch Kombinationen, zum Beispiel ist das erste Byte bei Anfragen recht gleichverteilt, während es danach wirr wird. Dann könnte ich 256 Bäume nehmen und am ersten Byte nur schauen, welchen Baum ich nehme. Ein schnelles Nachguckerchen und die Baumtiefen sind um 8 Stufen reduziert.

CSpille schrieb:

Bezüglich Cuckoo-Hashing:
Klingt interessant!
Aber was passiert (theoretisch) wenn 3 Objekte exakt die gleichen Hashwerte
für beide Funktionen hätten. Dann geht ja gar nichts mehr, oder?

Gute Frage.
Ich schätze da greift dann leider "In the latter case, new hash functions are chosen, and the whole data structure is rebuilt (“rehashed”)." aus
http://www.it-c.dk/people/pagh/papers/cuckoo-undergrad.pdf

Danke dir volkard!

Da ich (bisher) C++ nur für den Privatgebrach progge, hab ich solche Ressourcen-
Probleme eher weniger. Ansonsten kommt das MacBook Pro mit 16GB RAM bestimmt bald.
Aber trotzdem interessant zu wissen!

volkard schrieb:

Manchmal mache ich auch Kombinationen, zum Beispiel ist das erste Byte bei Anfragen recht gleichverteilt, während es danach wirr wird. Dann könnte ich 256 Bäume nehmen und am ersten Byte nur schauen, welchen Baum ich nehme. Ein schnelles Nachguckerchen und die Baumtiefen sind um 8 Stufen reduziert.

Naja...
Das klingt eher nach Bucket(sort) als nach Hashing

Hashtables sind (richtig betrieben) nicht einfach schneller als Bäume, sie skalieren besser. Wenn du das ganze vernünftig umsetzt, hast du damit effektiv amortisiert konstante (!) Laufzeitkomplexität; Bäume dagegen skalieren logarithmisch. Je größer die zu behandelnde Datenmenge, desto mehr kann sich der Einsatz einer Hashtable lohnen.

Allerdings ist Hashing nicht trivial; der Effekt steht und fällt mit der Wahl einer guten Hashfunktion, und die Frage, welche Hashfunktion für die zu erwartende Datenmenge gut ist, kann mitunter recht schwierig sein. Volkard hat IP-Adressen als Beispiel genannt, und er hat damit insofern recht, dass IP-Adressen als 32-bit-Integer in einer Hash-Funktion einfach zu behandeln sind - eine übliche Hash-Funktion sieht hier beispielsweise etwa so aus:

size_type hash(uint32_t ip) { return ip; }

Und das ist eine ideale Hashfunktion, wenn ip völlig zufällig ist. In der Realität ist das aber nicht zwingend der Fall - angenommen, du betreibst beispielsweise einen Webservice in einem internen Firmennetzwerk, und darin sind verschiedene Abteilungen in eigene Subnetze gesteckt, deren Desktops immer im gleichen Subnetzbereich stecken. Etwa erwartest du Anfragen aus 192.168.(1-5).(1-50). Hat deine Hashtable jetzt eine Größe von beispielsweise 257 (Primzahl), so nehmen die IPs (modulo Größe der Hashtable) aus Subnetz 192.168.1.* Werte von 233-256 und 0-25 an, Adressen aus 192.168.2.* Werte von 232-256 und 0-24 etc - der Bereich zwischen 25 und 229 wird nie getroffen, und du hast einen großen Haufen Kollisionen, was die Performance der Hashtable stark beeinträchtigt.

Cuckoo hashing hilft an dieser Stelle etwas, aber letztendlich muss dir klar sein, dass die Benutzung einer Hashtable nicht einfach daraus bestehen kann,

std::tr1::unorderet_set<ip_type> clients;

zu schreiben und zu erwarten, dass das schon das Richtige machen wird.

Volkards Bedenken bei Strings teile ich nicht uneingeschränkt; zwar muss für einen Stringvergleich nicht notwendigerweise der ganze String ausgelesen werden, aber die Hashfunktion muss beim Lookup in einer Hastable nur einmal ausgeführt werden, wogegen man bei großen Bäumen eine ganze Menge Stringvergleiche haben kann. Auch hier kommt es aber auf die zu erwartende Datenmenge an - lange Strings sind aufwändiger zu hashen, und erwartet man beispielsweise Strings der Form "EINS_VON_MEHREREN_LANGEN_PRAEFIXEN_eigentliche_daten" (wie etwa Bezeichner für OpenGL-Erweiterungen), ist abzusehen, dass Stringvergleiche überdurchschnittlich lange dauern werden und ein binärer Baum dementsprechend an Effizienz einbüßt.

mazal

Zu erwähnen wären vielleicht noch dynamische Hashverfahren wie zum Beispiel Extendible Hashing oder Linear Hashing. Die wurden eigentlich als Index für Datenbanken entwickelt. Aber vielleicht taugen die auch für Hauptspeicher? Müsste man mal ausprobieren.

Lenja

So, ich wieder...
ich habe es jetzt einfach über std::map gemacht und es scheint zu funktionieren Danke an alle