Ideen gesucht: Hash funktion für vektoren

Mati

Hallo,

ich bin gerade auf der suche nach einer effizienten Hash funktion für folgendes:
Man hat einen vektor gefüllt mit double werten. Wurde der vektor noch nicht in früheren berechnungen einmal benutzt speichere ich ihn ins hash. Wenn doch kann ich
einfach den berechneten wert der unter dem schlüssel zu finden ist hernehmen.
Wichtig: Alle vektoren haben die gleiche grösse z.B 5 Werte. d.h. 5 x 1 Struktur

Bisher bin ich nur auf solch triviale schlüsselerstellung gekommen:

Einfach die summe der elemente nehmen und die als schlüssel speichern. Sehr kollisionsanfällig.
summe aller multiplikationen von element mit index

Diese Ansätze sind natürlich ineffizient und kollisionsanfällig.
Ich brauche einen performanten (vor allem hinsichtlich Zeit) Ansatz.

Wenn jemand evtl. Links oder Ideen hat bin ich sehr dankbar!

Danke

volkard

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

*31 sollte recht fix gehen.

Mati

danke
wären bit-operationen net schneller?
ich hab mal was von zobrist-keys gelesen...die haben da gewaltige datenmengen über 64 bit zufallszahlen die sie geodert haben...
vielleicht irgendwie übertragbar auf mein problem? über eine 64-bit Zufallszahl logisch "ge-odert" z.B. mit der summe der vektor elemente? Oder wäre das zu teuer ...

warum eigentlich 31 ? Primzahl?

volkard

Mati schrieb:

wären bit-operationen net schneller?

+ ist nicht lahmer als ^. ist aber oft ein wenig besser, damit man nicht immer ein X an stelle i und ein X an stelle i+32 sich genau aufheben.

ich hab mal was von zobrist-keys gelesen...die haben da gewaltige datenmengen über 64 bit zufallszahlen die sie geodert haben...

zobrist-hashing hat nen andere zweck. da soll ermöglicht werden, daß in einem großen vektor, sagen wie mal 100 einträgen, der eintrag an stelle 73 einen anderen wert bekommen kann und man kann sofort den neuen hashwert des ganzen vektors neuberechnen. genauer: bei vektoren der größe n muß man auch mit zobrist den hashwert in O(n) berechnen. aber beim ändern nur eines vektor-elements kann man den hashwert dann in O(1) updaten.

vielleicht irgendwie übertragbar auf mein problem? über eine 64-bit Zufallszahl logisch "ge-odert" z.B. mit der summe der vektor elemente? Oder wäre das zu teuer ...

übertragbar isses. aber nicht schneller, würde ich meinen.

warum eigentlich 31 ? Primzahl?

a) speed
weil der compiler aus
i31
lieber
i32-i
und daraus
(i<<5)-i
macht.
stell dir mal i*161 vor, wie schill das mit shiften wäre. und ne integer-multiplikation ist im moment noch zu teuer (oder ich bin zu geizig).

b) ungerade zahl (primzahl ist gar nicht nötig, sie muss nur ungerade sein, um mit 2^32 oder 2^64 relativ prim zu sein und in unserem minizufallszahlengenerator die volle periode aufspannen kann). (eine überlegung, die bei zobrist nicht eingehen würde). und viel wichtiger: ungerade zahl: da plumpsen die bits nicht alle raus.
stell dir nur mal i*256 vor und 32-bittige hashvalues. das wäre eine hashfunktion, die nur die letzten 4 elemente kennt und alle älteren vergessen hat. vom ersten element sind sicher alle bits weg, rausgeshiftet.

c) vermischung
dadurch, daß die alte zahl zweimal auf die neue geworfen wird, weimla mit plus um 5 stellen verschoben und einmal mit minus ohne verschiebung, sind am ende von einem bit im eingang viele bits im ausgang betroffen. das macht gute hashfunktionen aus. die vermischung wäre mit lustigen zahlen wie 0x9E3779B1 noch viel besser, aber das mag ich hier nicht bezahlen.

d) die verschiebungsweite 5 der meisten bits mit <<5 ist relativ prim zur bitbreite der hashkeys (32 oder 64). das bringt wieder alle bits ins spiel. bei nicht selten vorkommenden eingangsfolgen, die nur im letzuten bit wackeln, daß die letzten (und die einig aktiven bits) und lustiger verschiebungsbreite 8 sind nur 4 oder 8 bist im ergebnis betriffen, egal wie lang der vektor ist. wäre schon netter, wenn alle 32 oder 64 bits mitspielen dürfen.

da ich aber nicht weiß, wie du die doubles hasht, kann ich dir nicht sagen, wie ich es machen würde, die vektoren zu hashen.

statt
h=h31+hash(e)
ist vielleicht
h=h+31hash(e)
zu bevorzugen, weil das auch den letzten wert mit *31 ein wenig durchmischt. dann braucht hash(double) nicht mehr so stark zu sein (hauptsache, sie bringt möglichst viele bits mit, sie muß aber nicht so arg schlimm verwürfeln). ich würde mich trauen, u32 hash(double x){return *(u32*)&x;} zu schreiben. bei doch noch kollissionen, die über den bloßen zufall hinausgehen, würde ich aus return h; ein return h*0x9E3779B1; machen. also pro vektor nur einmal ne integer-multiplikation am ende.

Mati

also ohne schleimerisch zu wirken...
Hut ab! So ne Bomben Antwort hab ich nicht erwartet - sie zeigt nur wie wenig ich eigentlich noch weiß *grmpf

Danke volkard - ich bin noch am verstehen deiner antwort bis ich evtl. mehr darauf eingehen kann...:)

EDIT:

ich finde nur spärlich in der sufu und google was zu hash maps unter c++. Ich bin mir im moment unsicher ob es überhaupt einen stl container hash_map nun gibt oder net? Habe auch was mit include <unordered_map> gelesen??? Da sind aber bereits die Hash-funktionen verbaut oder? Also da wir der Zugriff selbst bereits gesteuert und da müsste man keine eigene hash funktion mehr basteln?

Falls ich den schritt selbst wagen wollen würde ...auf was sollte ich dann wohl operieren? ich habe gerade schwierigkeiten mir vorzustellen wie ich eine eigene hash-funktion auf eine datenstruktur anwenden sollte? std::map hat ja wohl ne eigene ?? irgendwie mit nem 2D array?

Danke

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.