[C++] Hashcode

[Verwijderd]

Ik ben nu hashing aan het bestuderen, na eerst wat met int's te hebben gewerkt, om het te begrijpen. Ben ik nu bezig om woorden in een hash table op te slaan. Voor de hashcode heb ik de volgende functie:

code:

int Hash::hash_code(char *v)
{   int k=0;
    unsigned long r=0, s=1;

    while (k!=strlen(v))
    {   r=r+*(v+k)*s;
        s*=128;
        k++;
    }
    return r%size;
}

Als je een beetje lange woorden wilt opslaan, wordt r al snel heel groot, zo groot dat r buiten zijn waarde bereik valt en bij 0 verder gaat rekenen. Mijn vraag is, kan dit kwaad? En zijn er andere oplossingen mogelijk? En zijn er andere methoden om de hashcode te berekenen van strings?

[PiepPiep]

Ik ben nog net niet wakker genoeg om het precies te zien, maar volgens mij is het bij deze hash erg makkelijk om een collision te vinden.
Teneerste zie ik dat je s met 128 vermeningvuldigd, dit is effectief 7 bits naar links schuiven, je begint met 1, bit 1 op 1 dus, de volgende waarde zal dan bit 8 op 1 zijn, dus 0x100 daarna bit 8+7=15 op 1, dat is 0x8000, daarna 0x400000 daarna 0x20000000 en daarna blijft de waarde op 0.
Ander nadeel is dat je r = r + 'iets' doet, de waarde die al in r zat maakt niet uit. Goede hashes verwerken de waarde die al in r zat weer in het nieuwe deel.
Ik raad je aan eens te lezen over bijvoorbeeld md5, dan zie je dat er best wat nodig is om een goede hash te schrijven.

[ Voor 35% gewijzigd door PiepPiep op 05-08-2006 13:32 ]

[NMe]

Lekker duidelijk, al die variabelenamen van één teken.

Wat je ook kan doen is die s buiten beschouwing laten. Tel gewoon alle bytewaarden van alle characters in je string bij elkaar op. Je zal dan niet zo snel aan het maximum van een unsigned long komen. Wat je ook kan doen, is r meteen al modden met size, in plaats van bij het returnen. In dat geval overflowt die waarschijnlijk ook nooit.

Er zijn trouwens vast nog wel meer/betere oplossingen.

[Ivo]

De vraag is wat de eisen aan je hash zijn. Ik heb al een eens hash die ``mod N'' deed gebruikt en dat was prima voor die toepassing. Wil je echter een veilige password hash maken dan komt er een stuk meer bij kijken. Dus leg even uit wat je met je hashfunctie wil doen.

[Soultaker]

PiepPiep schreef op zaterdag 05 augustus 2006 @ 13:32:
Ik ben nog net niet wakker genoeg om het precies te zien, maar volgens mij is het bij deze hash erg makkelijk om een collision te vinden.
[..]
Ik raad je aan eens te lezen over bijvoorbeeld md5, dan zie je dat er best wat nodig is om een goede hash te schrijven.

Deze analyse klopt wel, maar het gaat om een hash table implementatie, dus het is niet echt belangrijk of er collisions te construeren zijn. Wat wél belangrijk is (voor elke hash functie) is dat elke uitkomst even waarschijnlijk is. De huidige functie is in ieder geval erg slecht; het wordt al een stuk beter als je die 128 vervangt door een of ander priemgetal.

-NMe- schreef op zaterdag 05 augustus 2006 @ 13:35:
Lekker duidelijk, al die variabelenamen van één teken.

Ik kan me er niet echt aan storen. Dan vind ik het kwalijker dat strlen() in de while-lus wordt aangeroepen! Maak daar maar v[k] van.

Wat je ook kan doen is die s buiten beschouwing laten. Tel gewoon alle bytewaarden van alle characters in je string bij elkaar op. Je zal dan niet zo snel aan het maximum van een unsigned long komen.

Dat is juist een nadeel: er is dan heel weinig spreiding in hashcodes. Er zijn bovendien veelvoorkomende collisions; bijvoorbeeld: hash("abcd") == hash("dcba") == hash("aadd") == hash("aaag"), enzovoort.

Ik denk zelf dat de TS gewoon het wiel opnieuw aan het uitvinden is, op een slechte manier. Neem gewoon een bestaande hashfunctie, die zich bewezen heeft, en bespaar jezelf veel werk. Een redelijk goede, snelle hashfunctie is de FNV hash.

[Verwijderd]

Op dit moment gaat het om het principe van hashing te begrijpen, als je het in de praktijk moet brengen ga je natuurlijk op zoek naar een goede hash functie.

maar volgens mij is het bij deze hash erg makkelijk om een collision te vinden.

Een collision wordt opgelost door gebruik te maken van gelinkte lijsten (en in het boek dat ik gebruik wordt ingegaan op lineair en quadratic probing).

Wat je ook kan doen is die s buiten beschouwing laten. Tel gewoon alle bytewaarden van alle characters in je string bij elkaar op. Je zal dan niet zo snel aan het maximum van een unsigned long komen.

Zou ook een idee zijn. Maar de vraag is, of het problemen oplevert als het maximum van de unsigned long wordt en bij 0 verder gaat.

De vraag is wat de eisen aan je hash zijn. Ik heb al een eens hash die ``mod N'' deed gebruikt en dat was prima voor die toepassing. Wil je echter een veilige password hash maken dan komt er een stuk meer bij kijken.

Op het moment wil ik alleen het principe goed begrijpen

[NMe]

Soultaker schreef op zaterdag 05 augustus 2006 @ 16:50:
Ik kan me er niet echt aan storen.

Ik wel. Ik kan het in dit geval wel begrijpen, maar dat maakt het nog niet logisch. Ik vind het in elk geval geen duidelijk gekozen namen voor variabelen.

Dat is juist een nadeel: er is dan heel weinig spreiding in hashcodes. Er zijn bovendien veelvoorkomende collisions; bijvoorbeeld: hash("abcd") == hash("dcba") == hash("aadd") == hash("aaag"), enzovoort.

Kans op collisions is er sowieso erg veel dankzij die modulo-operatie in het return statement. Afhankelijk van de inhoud van size kan dat zelfs een aardig grote kans zijn.

Verwijderd schreef op zaterdag 05 augustus 2006 @ 17:38:
Zou ook een idee zijn. Maar de vraag is, of het problemen oplevert als het maximum van de unsigned long wordt en bij 0 verder gaat.

In principe levert dat geen probleem op, in die zin dat je algoritme gewoon zou blijven werken, zij het met een verschuiving van waarden, om nog niet te spreken over een grote kans op duplicatie van hashcodes. Maar die had je door je modulo-berekening toch al.

Op het moment wil ik alleen het principe goed begrijpen

Daarbij moet je wel oppassen dat "het principe" kan verschillen bij het doel waarvoor de hash bedoeld is. Voor de ene applicatie kan een simpel algoritme met veel kans op dezelfde hashes voldoende zijn, voor de andere absoluut niet.

[MSalters]

Modulo size geeft nog niet zo heel veel collisions; je hebt gemiddeld 1 element per bucket. Nou dacht ik dat optimaal e^-1 element per bucket was, maar de theorie daarachter ben ik kwijt.