Ideen gesucht: Hash funktion für vektoren

[Mati]

Ich habe Probleme einen Begin zu starten...vielleicht hat jemand eine gute Idee...
Mein Problem hat sich nun so verändert:

Ich habe immer einen Vektor mit mehreren verschiedenen double werten z.B so:

v1 = [-2.5, 3.0, 0.0, -6.0, 7.3]

und immer einen zugehörigen 2ten vektor der ein einheitsvektor ist. z.B so:

e1 = [0.0, 0.0, 0.0, 1.0, 0.0]

Aus diesen 2 eingaben wird zusätzlich folgendes errechnet:
* aus v1 wird eine qr zerlegung gemacht also v1 wird verändert und hat neue werte
* ein weiterer vektor mit double werten (wie er errechnet wird ist egal) - sieht z.B so aus: t1 = [-3.889, 2.56, 0.0]
* ein 2ter weiterer vektor mit double werten z.B m1 = [-9.004, 8.0]

UNd folgendes wird am Ende gebraucht:
* ein vektor der nur aus 0en und 1en besteht: p1 = [1,0,0,1,0]

Nun zum Hashing:
Am Anfang würde ich gerne testen ob eine Berechnung bereits einmal stattgefunden hat. Wenn also v1 schon mal berechnet wurde UND e1 gleich ist also beide vektoren schonmal für eine berechnung verwendet wurden dann gib mir einfach nur das berechnete m1 und p1 zurück.
Falls aber NUR v1 verwendet wurde aber z.B e2 so aussieht: e2 = [1.0,0.0,0.0,0.0,0.0]
dann gibt mir bitte nur das neue v1 (die qr zerlegung) zurück und zusätzlich t1 und p1. Jetzt wird die berechnung gestartet um m1 zu berechnen.

Nochmal vielleicht in pseudocode:

if v1' == v1:
     if e1' == e1:
             return m1 && return p1
     else:
             return v1 && return t1 && return p1 -> und führe die berechnung weiter mit diesen werten fort um m1 zu berechnen
else:
     berechne erst das neue v1 und t1 und daraus das neue m1 UND speichere alle ergebnisse im hash

Jetzt kommt der Knackpunkt:
Das nachschauen ob etwas berechnet wurde will ich mit einem Hash realisieren.
Nur frage ich mich wie ich das eindeutig ohne kollisionen bewerkstelligen kann?
ich müsste also den schlüssel irgendwie aus den elementen von v1 und e1 bauen???
e1 könnte man einfach nur als reinen integer sehen an welcher stelle sich die "1" befindet!
Dann wüsste ich nicht wie ich mehrere vektoren im hash speichern sollte also der zugriff z.B nur auf t1 ...? also sowas mein ich: t1 = hash[key] und m1 = hash[key] wobei key gleich ist...also unter demselben schlüssel gäbe es ja eine reihe von vektoren die zu speichern wären...??? Evtl. in einer structure speichern und diese structure im hash speichern?

Zusätzlich bräuchte ich Hilfe welches hash ich nehmen sollte....ich glaube nicht dass eine einfach stl::map da ausreicht oder? Ist der zugriff da schnell? Wenn ich eine eigenen hash- funktion haben will was ich ja evtl. brauche um den schlüssel zu generieren sollte ich da nicht evtl. sowas wie hash_map verwenden?
Und wenn ich sogar eine eigene Implementierung eines hashes brauche - (was ich nicht hoffe) welche datenstruktur müsste ich dann hernehmen? ein Array? Evtl. 2-dimensional?

Für Hilfe bin ich sehr dankbar!

EDIT: habe gerade ein hash_map zum laufen gebracht.
wäre folgende variante sinnvoll um vectoren zu speichern?

struct myStruct 
{
       std::vector<double> v1;
       std::vector<double> t1;
       int col;
       int size;
       std::vector<double> m1;
}

hash_map<int, myStruct> hmap;

oder wäre es besser in der structure nur pointer zu speichern? Hab mal gelesen
dass pointer speichern in containern schwachsinn ist.....oder hab ich fehlinformationen?
Aber so würde die structure ziemlich viel speicher fressen....obwohl - käme auf gleiche raus oder?

zusätzlich habe ich gelesen dass es sinnvoll ist laut SGI eine eigene hash funktion zu haben. da wäre wir wieder da wo wir angefangen haben. Könnte ich einfach die von volkard beschriebene funktion fürs irgendwie anwenden?
laut sgi gibts ja sowas:

http://www.sgi.com/tech/stl/hash_map.html

so ganz komm ich mit der hash funktion noch net klar als erstes beispiel von volkard:

h=0 
 for each e in vector 
   h=(h*31)+hash(e) 
 return h

das hash(e) verstehe ich net: ist das der zugriff aufs hash mit dem schlüssel e? also wird hir der wert der im hash unter e gespeichert ist verwendet?

[Jester]

Ne, das ist sozusagen das hashen von Vektoren zurückgeführt auf das hashen von einzelnen doubles. Du brauchst also noch ne hashfunktion für doubles. Sowas dürfte aber dabei sein. Du mußt nur rausfinden wie's heißt.

[volkard]

Mati schrieb:

Das nachschauen ob etwas berechnet wurde will ich mit einem Hash realisieren.
Nur frage ich mich wie ich das eindeutig ohne kollisionen bewerkstelligen kann?

wir verkaufen dir nur was mit "wenigen" kollissionen. kollisionsfreiheit kriegste nur, wenn der hashkey genausolang ist wie die nutzdaten. und dann kann man auch gleich die nutzdaten vergleichen statt zu hashen.

[Mati]

Du brauchst also noch ne hashfunktion für doubles

sorry für meine verwirrung aber Jetzt versteh ichs noch weniger ....
ich habe im Moment folgendes am laufen:

namespace __gnu_cxx
{
    template<> struct hash< std::string >
    {
        size_t operator()( const std::string& x ) const
        {
            return hash< const char* >()( x.c_str() );
        }
    };
}

struct eqint
{
    bool operator()(int d1, int d2) const
    {
        return  d1 == d2;
    }
};

struct MyHash
{
    int operator()(const int key) const
    {
        std::cout << "in der hash-function" << std::endl;
        int ret = 0;
        ret = static_cast<int> (fabs(key));
        return ret;  
    }
};

Class::Class()
{
    __gnu_cxx::hash_map<int, double, MyHash, eqint> hash;

    hash[0] = 3.0;
    hash[1] = 2.5;
    hash[2] = 15.3;

    std::cout << "   -> " << hash[2] << std::endl;
    std::cout << "   -> " << hash[1] << std::endl;
}

so läuft es auch...wobei ich mir unsicher bin ob ich da nicht intern was falsch mache...

ich habe in der hash_map also "int" für die schlüssel.
den schlüssel wollte ich aus dem vektor errechnen über die hash-funktion MyHash...wobei im Moment nur ein fabs drin is.
das eqint dachte ich überprüft eben auf gleiche schlüssel dachte ich...

nur frage ich mich wie ich nun z.B eine funktion wie volkard sie präsentiert hat da mit reinziehen könnte....

so doch nicht:

h=0 
 for each e in vector 
   h=(h*31)+eqint(e) 
 return h

irgendwie verstehe ich da was falsch...
die hash-funktion ist doch die abbildung des schlüssels auf das hash. also sie errechnet mir die stelle wo meine daten drin stehen oder?
Und UM einen schlüssel zu errechnen rufe ich doch AUCH dies hash-funktion auf?
der vergleich müsste doch dann nur über die eqint funktion gehen in diesem fall:
hier mal die Links zu SGI:

http://www.sgi.com/tech/stl/hash_map.html
http://www.sgi.com/tech/stl/hash.html

hier
http://www.astro.uni-wuerzburg.de/~asmaier/usefulthings/c++.pdf
wird auf seite 271 genau dies gemacht....

nur verstehe ich im moment auch net warum überhaupt eine vergleichsfunktion da sein muss...denn entweder der key ist enthalten oder nicht ? er vergleicht doch nicht zuerst jeden hash key mit dem neuen key?

oder ist es so dass ich 2 Hashfunktionen brauche? Eine die mir den doublewert gleichverteilt macht und die eine die dann auf das hash mapped???

kann mir jemand behilflich sein?
Danke

[Mati]

mir fällt gerade auf...wenn ich einen vektor mit double werten als eingabe habe, wie soll ich denn da überhaupt sinnvollerweise ein hashing implementieren...
auf double werten bin ich ja wirklich nur äusserst selten dann auch identisch oder?
müsste ich da nicht auf eine untere schranke testen ob die einträge identisch sind?

[net 0]

Mati schrieb:

mir fällt gerade auf...wenn ich einen vektor mit double werten als eingabe habe, wie soll ich denn da überhaupt sinnvollerweise ein hashing implementieren...

behandle den vector doch als array von longs. müsste aufgehen, wenn doubles aus 8 bytes bestehen. dann brauchste auch keine langsamen double->int konvertierugen (es soll ja schnell sein). für sowas gibt's massenweise fertige implementierungen (such mal bei google nach 'message authentication code'). wenn's wenig kollisionen haben soll könnteste auch auch sowas wie 'sha1' nehmen, aber das ist leider viel langsamer als 'hash = hash*31+x'.

[Mati]

danke net aber um ehrlich zu sein verstehe ich das nicht:

behandle den vector doch als array von longs. müsste aufgehen, wenn doubles aus 8 bytes bestehen.

wie meinst du als long behandeln?

[net 0]

Mati schrieb:

wie meinst du als long behandeln?

etwa so:

// viele doubles...
double d[] = {1.1, 2.2, 3.3, ...};
...
// hashfunktion braucht pointer auf startadresse und anzahl der longs
hashwert = hash_long_vector ((long*)d, sizeof(d)/sizeof(long)); 
...

so 'ner hashfunktion ist es ja egal, ob das mal fliesskommawerte waren oder irgendwas anderes

[Mati]

danke...
aber hmm...
würden dann folgende 2 arrays unterschiedliche schlüssel generieren?

d1= {1.1, 2.2,3.3}
d2 = {1.0,2.2,3.3}

?
sorry...ich blick da noch immer net ganz durch...du castest auf long und berechnest die anzahl der longs im vectors und übergibst beides?

[net 0]

Mati schrieb:

danke...
aber hmm...
würden dann folgende 2 arrays unterschiedliche schlüssel generieren?
d1= {1.1, 2.2,3.3}
d2 = {1.0,2.2,3.3}
?

ja, genau. sobald sich das kleinste bit unterscheidet gibt's (mit hoher wahrscheinlichkeit) einen andere hashwert.

Mati schrieb:

sorry...ich blick da noch immer net ganz durch...du castest auf long und berechnest die anzahl der longs im vectors und übergibst beides?

jo, geht auch mit ints, bytes etc. je nachdem wie's die hashfunktion haben will...

[Mati]

ajajaj...ich schaffe es einfach nicht den transver von deinem vorschlag net auf die von volkard vorgeschlagene hash funnktion zu übertragen...

könnte mir jemand irgendwie behilflich sein?

h=0 
 for each e in vector 
   h=(h*31)+hash(e) 
 return h

ich begreife immer noch nicht genau was dieses hash(e) macht....?

[volkard]

Mati schrieb:

ich begreife immer noch nicht genau was dieses hash(e) macht....?

ich dachte dabei an sowas:

typedef unsigned int uint32;//oder ähnlich, je nach compiler
typedef unsigned long long uint64;//dito

inline uint32 hash(double x){
   uint64* p=reinterpret_cast<uint64*>(&x);
   return *p ^ (*p>>32);
}

in der annahme, daß die hashtable 32-bittige hashwerte mag.

[Mati]

tjoa danke...

Mit einem Apell an eure geduld:

uint64* p=reinterpret_cast<uint64*>(&x);
return *p ^ (*p>>32);

ich werde wohl erstmal einen dicken schinken zum compilerbau lesen demnächst damit ich sowas auch verstehe

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?
Zusätzlich: Sind reinterpret_casts net gefährlich?

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? Also 2 Funktionen um den schlüssel aus einem vektor zu generieren?

Ich versuche es im moment so:

struct MyHash
{
    int operator()(const double key) const
    {        
        int ret = 0; 
        //for each e in vector 
        ret = (ret * 31) + hash_d(key);
        std::cout << "Der key: " << ret << std::endl;
        return ret;
    }

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

struct HASH_DATA
{
    std::vector<double> A_hat;
    std::vector<double> m_k_hat;
    int unit_vec_size;
    int unit_vec_row;   
};

//in einer methode einfach nur testbeispiel
...
    hash_map<double, HASH_DATA, MyHash> hash;

    struct HASH_DATA hd;
    std::vector<double> a;
    a.push_back(2.0);
    a.push_back(2.9);
    std::vector<double> b;
    b.push_back(1.0);
    b.push_back(1.9);
    hd.A_hat = a;
    hd.m_k_hat =b;
    hd.unit_vec_row = 2;
    hd.unit_vec_size = 1;
    hash[3.8] = hd;
    hash[3.7] = hd;

//

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
Aber eigentlich sollten solche werte net auftauchen weil volkard ja mit unsigned arbeitet
oder?
UNd die Zahlen sind ja ziemlich groß...aber immer noch im wertebereich von unsigned int...oder?
Aber irgendwie scheints zu funktionieren...also
2.9999999999
2.9999999999
3.0000000000

ergeben die ersten beiden identische schlüssel und
die 3.0 dann nen völlig anderen...auch wenn die schlüssel gewaltig sind UND eben manchmal negativ...müsste doch passen oder?

Danke für eure geduld

EDIT:
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??

[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

[Plotzenhotz]

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:

1. 1001
2. 1001 0000
3. 0000 1001
4. 0000 1001 ^ 1001 0000 = 1001 1001

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

ich glaube ich versteh hier was falsch oder???