Hash-Funktion für arrays bzw. double-werte

Hallo,

ich habe ein hash-table über hash_map erstellt. Ich benötige eine Hash-funktion
die mir einen möglichst kollisionsfreien eindeutigen schlüssel generiert.

Das Problem: Ich habe Vectoren/Arrays die aus double-werten bestehen.
Ich berechne mir aus jedem array einen eindeutigen schlüssel und speichere das ganze ding mit schlüssel im hash ab.

Meine jetzige Hash-Funktion sieht so aus:

Key Hash::Compute_Key( const double* vec,
                       size_t size) const
{
    Key ret = 0;
    Key mix = Hash_Double(0.13);
    while(size--)
    {
        ret = (ret*31) + mix + Hash_Double(*vec);
        vec++;
    }
    return ret;
}

und mein Hash_Double sieht so aus:

inline Key Hash::Hash_Double(double x)
{
    Key p[2];
    memcpy( p, &x, sizeof p );
    return p[0] ^ p[1];
}

Nur führt das bei mir zu Kollisionen: Z.B: die vektoren [8.0,0.0,0.0,8.0] und
[8.0,-2.0,-2.0,8.0] erzeugen identische schüssel.

Meine Frage: Was wäre eine günstigere Hash-Funktion bzw. eine Kollisionsfreiere? Ich überlege die ganze zeit ob ich die mix-variable oder die primzahl 31 ändern sollte. Habt ihr vorschläge für eine gute Schlüsselerzeugung für double-arrays?

Was ich noch vergessen habe zu erwähnen: Die schlüssel sollten natürlich ganzzahlig sein zum vergleich.

Vielleicht im Inneren der Hash-Funktion sowas berechnen?:

ret = Hash_Double(ret) * 31 + mix + Hash_Double(*vec);

Ethon

Liefern unorderedset/unordered_map nicht eine generische Funktion mit?
Ich würde mir nicht groß trauen sowas selbst zu implementieren, in guten steckt doch eine Menge Mathematik.

In der Uni haben wir diesbezüglich auch nur unperformanten Mist hinbekommen, gut doppelt so langsam oder schlimmer als die Standard-Container (Java in unserem Fall).

Nexus

Eventuell Boost.Hash?

kann den gesamten code jetzt nicht auf boost umstellen.
Außerdem muss ich hier auf c++ stl mist zugreifen. gibts da was? kann ihc irgendwie aus unordered_map was extrahieren und haben die wirklich für double-vektoren hash-funktionen?

314159265358979

Testo schrieb:

kann den gesamten code jetzt nicht auf boost umstellen.

Du brauchst doch bloß deine Hashfunktion übergeben, mehr nicht.

Testo schrieb:

c++ stl mist

Spinnst du?

Ethon

Ohne dir jetzt zu nahe treten zu wollen: Wieso hashst du ein Array?
Eine normale Map, die über einen Baum implementiert ist, sollte da nicht langsamer sein (warscheinlich sogar schneller).

Warum ein Array: Der gesamtalgorithmus hat halt arrays. Ich werde jetzt sicherlich nicht die gesamten datenstrukturen umbauen. stl::vektoren sind ja im grunde arrays.

Du brauchst doch bloß deine Hashfunktion übergeben, mehr nicht.

eh ich will ja eine hash-funktion erstellen - deswegen die frage. wo ich sie übergebe ist ja auch schon egal.

meine frage war ernst gemeint. meine problemstellung ist fix und nicht änderbar. deswegen bitte ich um konstruktive Hilfe: ein double-array und ich suche eine selbst-gestrickte möglichst kollisionsfreie möglichkeit einen ganzzahligen schlüssel zu bauen. oben mein jetziger vorschlag.

mit meinem 2ten post sieht es ganz gut aus. andere meinungen/hilfestellungen?

314159265358979

Wie du deine hash-Funktion erstellen kannst, findest du in der Doku.

Ethon

Warum ein Array: Der gesamtalgorithmus hat halt arrays. Ich werde jetzt sicherlich nicht die gesamten datenstrukturen umbauen. stl::vektoren sind ja im grunde arrays.

Von mir aus kannst du ja Arrays als Keys nehmen. Zwar schlechtes Design, aber soweit egal.

Mir geht es eher darum dass eine Hashtable ein unpassender Container ist, wenn du riesige Keys hast.

Und: Bist du dir sicher, dass die Arrays als SCHLÜSSEL fungieren sollen? Nicht eher als Data?

Nexus

Testo schrieb:

kann den gesamten code jetzt nicht auf boost umstellen.

Ich dachte, es ging nur um eine Hash-Funktion?

Testo schrieb:

gibts da was?

TR1.Hash

Testo schrieb:

Warum ein Array: Der gesamtalgorithmus hat halt arrays. Ich werde jetzt sicherlich nicht die gesamten datenstrukturen umbauen. stl::vektoren sind ja im grunde arrays.

Ja, nur ist es im Allgemeinen dumm, in C++ Arrays zu verwenden. Mindestens std::array sollte schon hin

knivil

Einfach dein double-Array als byte-Array interpretieren und eine der Hashfunktionen von Wikipedia nehmen.

Wie du deine hash-Funktion erstellen kannst, findest du in der Doku.

danke für den kommentar, allerdings kann ich auf solche hilfe verzichten. meine frage war spezifisch und genau. diese antwort dagegen nicht.

Ja, nur ist es im Allgemeinen dumm, in C++ Arrays zu verwenden. Mindestens std::array sollte schon hin

Begründung?

Ich dachte, es ging nur um eine Hash-Funktion?

richtig ja. aber wenn ich NUR die eine einzige hash-funktion auf boost setze und deswegen gleich der gesamte code eine abhängigkeit auf boost hat weiss ich nicht ob das sinnvoll ist. ich schaue mir mal TR1.Hash an

Einfach dein double-Array als byte-Array interpretieren und eine der Hashfunktionen von Wikipedia nehmen.

puh. ist die reihenfolge der elemente gesichert? Also liefert 0.0,1.0 einen anderen schlüssel als 1.0,0.0 ? genau verstehe ich deinen kommentar jetzt nicht?

nd: Bist du dir sicher, dass die Arrays als SCHLÜSSEL fungieren sollen? Nicht eher als Data?

Ja die arrays müssen als schlüssel dienen. Sobald 2 arrays gleich sind passiert etwas. Nur die Überprüfung dass 2 arrays gleich sind ist nicht trivial wie ich finde. Das ganze muss im hash liegen wegen schnellem zugriff.

314159265358979

Testo schrieb:

danke für den kommentar, allerdings kann ich auf solche hilfe verzichten. meine frage war spezifisch und genau. diese antwort dagegen nicht.

Meine Antwort war genau genug. Dazu hat Nexus dir den Link gegeben, damit DU dir das aus der Doku rausliest. Ich habe sie kurz aufgeschlagen, selbst im Inhaltsverzeichnis sieht man schon, wo man hin muss.

Testo schrieb:

Begründung?

Wenn du nach ner Begründung dafür fragst und die STL Mist schimpfst, dann lern erst mal C++.
Ich wette du kommst von Java. Oder vielleicht von C#? Was noch primitiveres? Irgendwas, wo du jeden Scheiß in Form einer Klasse in den Arsch geschoben bekommst.

Ethon

Ja die arrays müssen als schlüssel dienen. Sobald 2 arrays gleich sind passiert etwas. Nur die Überprüfung dass 2 arrays gleich sind ist nicht trivial wie ich finde. Das ganze muss im hash liegen wegen schnellem zugriff.

Und nochmal: Wie sieht es mit einer normalen Map aus?

Angenommen du hast große Arrays. Wenn diese sich innerhalb der ersten Elemente unterscheiden(Was der Regelfall ist), ist ein Vergleichen sehr viel billiger als das Hashen des ganzen Arrays. Vor allem Kollisionen werden bei soetwas richtig teuer.

Probiers doch einfach mal aus was schneller ist, ich tippe gerade stark auf die Lösung ohne Hashtable.

Zu dem Vorschlag TR1.hash.: Einfach container benutzen - aber wie definier ich die hash-funktion? Ähnlich zu hash_map?

Wenn du nach ner Begründung dafür fragst und die STL Mist schimpfst, dann lern erst mal C++.
Ich wette du kommst von Java. Oder vielleicht von C#? Was noch primitiveres? Irgendwas, wo du jeden Scheiß in Form einer Klasse in den Arsch geschoben bekommst.

ich will mich nicht auf das niveau herablassen: java habe ich vor 6 jahren hinter mir gelassen genau wie c#. stl ist natürlich kein mist. aber wir wissen alle dass die STL nicht immer das gelbe vom Ei ist.

Und nochmal: Wie sieht es mit einer normalen Map aus?

ich weiß jetzt nicht ob ich dich richtig verstehe. du meinst die hash-map aussondern und ne normale map verwenden ohne hash-funktion? wie vergleichst du dann die dobule-elemente? über eine epsilon=1e-16 mittels fabs(vec1[i]-vec2[i])< eps oder so?

314159265358979

Mit std::less<double>

Mit std::less<double>

Aha. sehe ich das richtig dass mir std::less binär arbeitet und zurückgibt ob 2 typen identisch bzw. kleiner sind? Also wäre das ja genau ein korrektes hilfsmittel mir zu sagen ob 2 double-werte identisch sind auf binärbasis. ist das so?

314159265358979

Nein, std::less vergleich nicht auf Binärbasis. Allerdings mit einem Epsilonvergleich soweit ich weiß. (korrigiert mich, wenn ich falsch liege)

Edit: Irrtum, scheinbar verwendet std::less<double> den ganz normalen built-in operator <.

SeppJ

314159265358979 schrieb:

Edit: Irrtum, scheinbar verwendet std::less<double> den ganz normalen built-in operator <.

Ja, das ist sozusagen die Definition und der Zweck all dieser Funktionsobjekte.

Überhaupt, was soll ein Epsilon-Vergleich bei "kleiner" sein? Und woher sollte less ein epsion nehmen?