Ideen gesucht: Hash funktion für vektoren

Shade Of Mine

hab irgendwie ne handvoll posts ueberlesen, sorry

Mati

kein problem - ich bin ja froh dass mir jemand hilft

volkard

Mati schrieb:

EDIT: ich nehme an dass *p >> 32 das mappen des 64 bit schlüssel auf einen uint 32 bit ist oder? aber warum XOR mit dem ausgangsschlüssel? Um den wert definitiv eideutig zu halten?

einfach ein return *p; würde von dem 64-bittigen *p nur die unteren 32 bits nehmen für den returnwert, der nur 32 bit hat.
deswegen haben ich mit *p>>32 auch noch die oberen 32 bits dazugemixt.

Zusätzlich: Sind reinterpret_casts net gefährlich?

undefiniertes verhalten. jo. musst halt testen, ob das auf deinem compiler geht.

Nur so damit ich mal das grobe verstehe...verstehe ich das richtig das im grunde die hash-funktion jetzt die funktion "hash" für double werte aufruft?

jo.

Also 2 Funktionen um den schlüssel aus einem vektor zu generieren?

jo.

davon ist einer der hash werte so : -644612093
dumme frage aber hash werte - können die negativ sein? bin gerade etwas durcheinander weil bei arrays gehts ja net

du hast den hashcode in einen int gesteckt statt in einen unsigned int vor dem ausgeben. ist aber nicht schlimm, es sind ja alle bits da. nur die anzeige ist komisch.

Aber irgendwie scheints zu funktionieren...also

na, das ferut mich jetzt.

müsste die schlüsselberechnung net evtl. so aussehen:
uint32 operator()(const double key) const
    {        
        uint32 ret = 0; 
        //for each e in vector 
        ret = (ret * 31) + hash_d(key);
        std::cout << "Der key: " << ret << std::endl;
        return ret;
    }
also den rückgabewert des operators auf uint32??

jo, das sieht ganz lecker aus.

Mati

An dieser Stelle großes Dankeschön - v.a. auch an volkard!
Es haut jetzt so hin

undefiniertes verhalten. jo. musst halt testen, ob das auf deinem compiler geht.

implementation defined != undefined
Das Erbebnis eines reinterpret_cast ist in den meisten Fällen soweit ich mich erinnere implementation defined und nicht undefined.

Oder irre ich mich jetzt?

volkard

Plotzenhotz schrieb:

implementation defined != undefined

ja, reinterpret_cast ist implementation-defined.
ok, es kommt ein implementation-defined pointer to uint64 raus.

mal gucken, on der zugriff auf diese adresse dann undefined oder implementation-defined oder noch was anderes ist.

Mati

Hallo,
ich bin es noch einmal

je mehr ich darüber nachdenke desto weniger verstehe ichs - sorry an der stelle nochmal aber ich will den code wirklich auch verstehen.

von volkard diese funktion um double werte zu hashen:

inline U_Int32 
    hash_d(double x) const
    { 
        U_Int64* p = reinterpret_cast< U_Int64* > (&x); 
        return *p ^ (*p >> 32); 
    }

ich verstehe die bearbeitung nicht.
* WIr nehmen die Adresse von x was doch ein 32 Bit Typ ist Oder?
* Dann casten wir durch reinterpret cast auf 64 Bit Pointer...d.h unser p ist ein Pointer
auf die zu 64 BIt erweiterte Adresse von p ?
* Und dann schieben wir die ersten 32 Bit (waren das die 32 Bit vom anfang? Also werden durch den cast 0er angehängt?) wieder nach hinten
* Und anschließend XOR mit dem geschobenen wert damit wir 2mal sozusagen die Bits hintereinander bekommen? Also ein kurzbeispiel:

1001
1001 0000
0000 1001
0000 1001 ^ 1001 0000 = 1001 1001

Aber der rückgabewert ist doch ein 32 Bit Typ?

ich glaube ich versteh hier was falsch oder???

volkard

Mati schrieb:

* Dann casten wir durch reinterpret cast auf 64 Bit Pointer...d.h unser p ist ein Pointer

nee. wie casten auf einen 32-bittigen pointer auf einen 64-bittigen integer.

p hat 32 bit.

aber *p hat 64 bit.

ich mach mal ne zwischenvariable rein. aus

inline U_Int32 
    hash_d(double x) const
    { 
        U_Int64* p = reinterpret_cast< U_Int64* > (&x); 
        return *p ^ (*p >> 32); 
    }

wird

inline U_Int32 
    hash_d(double x) const
    { 
        U_Int64* p = reinterpret_cast< U_Int64* > (&x); 
        U_Int64 pseudodouble=*p;
        return pseudodouble ^ (pseudodouble >> 32); 
    }

. so besser?

Mati

hmm...
tut mir leid für meine Erfahrungslosigkeit in dieser Hinsicht ...mir würde es sehr helfen wenn Du mir einmal etwas genauer zu den einzelnen operationen was sagen könntest.

Wäre sehr nett
danke

volkard

Mati schrieb:

hmm...
tut mir leid für meine Erfahrungslosigkeit in dieser Hinsicht ...mir würde es sehr helfen wenn Du mir einmal etwas genauer zu den einzelnen operationen was sagen könntest.
Wäre sehr nett
danke

nö, jetzt fehlen mir weiteren die worte. sorry. ich bitte darum, wenn jemand noch etwas dazu beitragen kann, selbst wenn es schon mehrmals gesagt wurde, daß er das tut. Mati weiß ganz bestimmt schon alles, nur fällt es ihm gerade nicht ein und ein klitzekleiner schubs würde reichen. nur welcher?

Nanyuki

Mati schrieb:

hmm...
tut mir leid für meine Erfahrungslosigkeit in dieser Hinsicht ...mir würde es sehr helfen wenn Du mir einmal etwas genauer zu den einzelnen operationen was sagen könntest.

Wäre sehr nett
danke

Dein erster Fehler war, dass du angenommen hast, dass x 32 bit lang ist.
doubles sind aber 64 bit lang.
Jetzt schau dir den Code mit diesem Wissen nochmal an...

Mati

hmm...
ich bin einfach ehrlich jetzt:
ist denn die adresse eines double-typs auch 64 Bit lang? Ich dachte alle adressen hätten 32 Bit.

also folgende zeile:

U_Int64* p = reinterpret_cast< U_Int64* > (&x);

legt mir einen 64 Bit Pointer an der auf die speicherzelle von x zeigt? also er zeigtauf die adresse von x - richtig oder falsch?

und hier:

U_Int64 pseudodouble=*p;

hole ich mir den wert der an der adresse von x steht und speichere ihn in pseudodouble? ja?

und

return pseudodouble ^ (pseudodouble >> 32);

macht das was im vorigen post versucht habe nachzuvollziehen?

Danke aber ein anstoß war das nicht wirklich...

hole ich mir den wert der an der adresse von x steht und speichere ihn in pseudodouble? ja?

Ja, und der WERT der an der Adresse von x steht ist 64 Bit lang (U_Int64), NICHT der Zeiger darauf (U_Int64*). Wie lange der Zeiger (die Adresse) ist spielt überhaupt keine Rolle.

Mati

*grmpf irgenwie bin ich banane,
warum holen wir uns dann net gleich den wert von x und returnen ihn?
ich verstehe im moment einfach nicht was genau die funktion mit den bits macht.
erst 1001 auf 0000 10001 (so ungefähr) ...was ich bräuchte ist einfach ne genaue beschreibung was genau mit den bits im speicher passiert shifting etc....
wenn jemand noch nerven hat...