Hash-Table - Fehler abfangen

Dravere

Hallo zusammen,

Ich habe bisher Hash-Tables immer eher gemieden. Und zwar aus einem einfachen Grund. Ich wusste in den meisten Fällen nicht, wie ich reagieren soll, wenn zwei verschiedene Schlüssel den gleichen Hashwert liefern. Und ich weiss heute noch nicht, wie man dies am besten angehen sollte, wodurch für mich Hash-Tables recht wertlos erscheinen.
Trotzdem werden sie anscheinend sehr oft verwendet, wodurch mir hier offenbar irgendwelches Wissen zu fehlen scheint. Und da ich aktuell gerade ein Fall habe, wo ich durch das Ersetzen eines binären Baumes mit einer Hash-Table eine mehr als doppelte Geschwindigkeit erreiche, wollte ich diesbezüglich mal nachfragen.

Wie sichert man sich ab gegen gleiche Hashwerte bei unterschiedlichem Schlüssel? Kann man das überhaupt? Und wenn nicht, gibt es dann so viele tickende Zeitbomben da draussen?

Ich kann kein Lotto spielen, ich muss für die Korrektheit des Programmes garantieren. Wenn zwei unterschiedliche Schlüssel den gleichen Hashwert haben, dann hätte das äusserst unangenehme folgen, welche womöglich erst sehr verzögert im Arbeitsprozess (Monate oder gar Jahre später) bemerkt würden.

Grüssli

volkard

Dravere schrieb:

Wie sichert man sich ab gegen gleiche Hashwerte bei unterschiedlichem Schlüssel? Kann man das überhaupt? Und wenn nicht, gibt es dann so viele tickende Zeitbomben da draussen?

Einfach den nächsten freien Platz nehmen. Wo ist das Problem?
Ok, es gibt eins: Hat man einen kleinen Cluster mit vollen Feldern, steigt die Wahrscheinlichkeit für das Feld genau nach dem Cluster, belegt zu werden. Die Cluster wachsen. Das ist doof. Muss vermieden werden.

a) double hashing. günstig als tabellengröße einen oberen primzahlenzwilling nehmen. der platz ist hash(key)%size. ist da aber voll, wird weiter gesucht mit schrittweite hash(key)%(size-2). knuth hat nachgemessen, daß es dabei praktisch zu keiner clusterbildung kommt. Nicht voller als 80% machen, dann hat man ca 2 Zugriffe pro Suche.

b) die hashtable ist einfach ein vector<forward_list>. Ebenfalls nicht zu voll machen, man will ja kurze Listen haben.

c) cockoo-hashing ist auch recht lecker.Ebenfalls nicht zu voll machen.

Dravere schrieb:

Ich kann kein Lotto spielen, ich muss für die Korrektheit des Programmes garantieren. Wenn zwei unterschiedliche Schlüssel den gleichen Hashwert haben, dann hätte das äusserst unangenehme folgen, welche womöglich erst sehr verzögert im Arbeitsprozess (Monate oder gar Jahre später) bemerkt würden.

Die Hashtables sind alle sicher. Kein Lotto. Kein Wert geht verloren oder wird verwechselt. hashen ist nur für schnelles vermuten, wo der datensatz steckt. es wird dann nochmal echt der ganze key verglichen.
Aber die hashtable hat normalerweise einen sehr guten average case und dafür einen schrecklichen worst case.

Dravere

volkard schrieb:

es wird dann nochmal echt der ganze key verglichen.

Dann stimmt diese Aussage nicht?
"Der Schlüssel muss in eienr Hash-Table keine Implementierung für den Vergleich haben. Es muss nur eine Funktion existieren, welche aus dem Schlüssel einen Hashwert erzeugt."

Grüssli

volkard

Dravere schrieb:

volkard schrieb:

es wird dann nochmal echt der ganze key verglichen.

Dann stimmt diese Aussage nicht?
"Der Schlüssel muss in eienr Hash-Table keine Implementierung für den Vergleich haben. Es muss nur eine Funktion existieren, welche aus dem Schlüssel einen Hashwert erzeugt."

Grüssli

So ist es. Man braucht eine hash(key) und einen op==(key,key).

Wikipedia sagt auf http://de.wikipedia.org/wiki/Hashtabelle

Bei einer Suche in der Hashtabelle wird nun ähnlich vorgegangen. Zunächst wird aus einem Suchschlüssel wieder ein Hashwert berechnet, der den Bucket des gesuchten Datenobjektes bestimmt. Falls es zu einer Kollision gekommen ist, muss jetzt nur noch durch direkten Vergleich des Suchschlüssels mit den Objekten das gesuchte Ziel bestimmt werden.

Dravere

*alte Vorlesungsunterlagen wegwirft*

ok ... danke

Grüssli

volkard

Der Worst-Case mit Zeit O(n) macht einem natürlich Angst.

Und dann kann man auch schonmal abweichen und eine Hashtable mit "Zeitbombe" bauen. Aber ganz bewußt. Und nur ganz speziell. Und das sind dann nicht mehr die normalen Hashtables, die man in Algorithmen&Datenstrukturen-Büchern findet.

Ich nehme solche als Cache vor teuren Berechnungen. Das Key-Value-Paar wird nach der Berechnung in Position hash(key)%size reingeschrieben und fertig. Und falls es von einem Neueren Paar überschreiben wird, kein Problem. Beim Aufsuchen wird mit dem op== geschaut, ob der key wirklich trifft und falls nicht, wird gerechnet.

Und beim Schach benutzt man tatsächlich die Zeitbombenversion. Es wird nur hash(stellung) und die Bewertung der Stellung gespeichert. Eventuelle Kollissionen mit Fehlurteilen werden in Kauf genommen.

Dravere schrieb:

*alte Vorlesungsunterlagen wegwirft*

Jo, Du wurdest gewolft.

Hashtables sind supi empfindlich gegen schwache hash-Funktionen.
Mal ein schnell hingekotztes

hash(){
   uint32_t result=0;
   for(auto x:v)
      result=2*result+x;//damit jedes x-bit woanders im result erscheint, 
         //je nachdem, wo im array es war. für bessere durchwürfelung. 
   return x;
}

und man ist bei O(n).

Diese doofe hash-Funktion schubst nämlich mit << einfach alle zu alten Bits hinaus aus dem result, es sind nur die 32 letzten x überhaupt wirksam. wenn jetzt auch noch fast alle keys gleich enden (z.B. Spielgeschehen auf der linken Brettseite und rechts bleibt es gleich), haben alle keys den selben hashwert. Und schwupps, hat man nicht mehr 1000 Antworten pro Sekunde, sondern nur noch eine Antwort pro Minute. Muss natürlich beim Kunden passieren, wie sich das gehört.
Deswegen ist

#define map unordered_map

keine extrem gute Idee.

hustbaer

Den Fehler dass du die falsche Variable zurückgibst (x statt result) findet der Compiler netterweise noch.