4. ist diese hashfunktion kollisionsfrei?

ist diese hashfunktion kollisionsfrei?

  • N

    guckst ihr: http://www.fantasy-coders.de/projects/gh/html/x435.html

    0
  • T

    also, dein kollisionsbeispiel geht schon mal nicht, c.rackwitz, weil ich ja *genau* 4 Bytes teste. Nicht mehr und nicht weniger.

    Wie soll dann

    char *foo = "hallo welt";
    char *bar = "gegruesst, welJ";

    funktionieren?

    volkard:

    wert = (wert * 31 + ptr[i]);

    ich dachte, die 256 * wert seien dazu da, um den wert "weiter zu shiften" wie beim hornerschema? ich kapiere nicht so ganz den sinn, wenn man das so macht..

    0
  • C

    achso, na dann...

    #include <stdio.h>
#include <string.h>

unsigned long hashing(void *object, unsigned long length, unsigned int size) {
    unsigned long i = 0;
        unsigned long wert = 0;
    unsigned char *ptr = NULL; /* nur auf char gecasted, damit compiler nicht mecker */
    ptr = object;
    for(i = 0; i < length; i++) {
        wert = (wert * 256 + ptr[i]) % size;
    }
    return wert;
}

int main(void)
{
	int irgendwas = 42; // beliebig, echt.
	char *foo = "welt";
	char *bar = "welJ";
	printf("%ld\n", hashing((void*)foo, strlen(foo), irgendwas));
	printf("%ld\n", hashing((void*)bar, strlen(bar), irgendwas));
	return 0;
}

    36
36

    31 statt 256, weil dein `wert` nur 8 bit breit ist und du so die bits mit *256 einfach rausshiftest anstatt sie ordentlich miteinander zu vermischen.

    0
  • V

    the_menace schrieb:

    ich dachte, die 256 * wert seien dazu da, um den wert "weiter zu shiften" wie beim hornerschema? ich kapiere nicht so ganz den sinn, wenn man das so macht..

    31 statt 256, weil dein `wert` nur 8 bit breit ist und du so die bits mit *256 einfach rausshiftest anstatt sie ordentlich miteinander zu vermischen.

    (stell dir vielleicht mal die zahlen binär vor und schau, was bei *256 und was bei *31 passiert.)

    0
  • T

    volkard: ah, okay, kapiert 🙂 Ich hatte die beschreibung im sedgewick so verstanden, dass das rausschieben gewollt war.

    c.rackwitz: in deinem beispiel ist size aber keine primzahl. 41 und 43 wären primzahlen und genau dann gibts mit deinem beispiel keine kollision.

    0
  • C

    int irgendwas = 41; // beliebig, echt.
    char *foo = "welt";
    char *bar = "welK";

    akzeptier es doch bitte. dein algo kollidiert viel zu einfach. ob man dabei die eingabewerte anpassen muss, ist nicht die frage.

    0
  • L
     

    unsigned long hashing(void *object, unsigned long length, unsigned int size) { 
    unsigned long i = 0; 
    unsigned long wert = 0; 
    unsigned char *ptr = NULL; /* nur auf char gecasted, damit compiler nicht mecker */ 
    ptr = (unsigned char*)object; 
    for(i = 0; i < length; i++) { 
        wert = (wert * 31 + ptr[i]); 
    } 
    return wert % size; 
} 

int main(void) 
{ 	
    int irgendwas = 42; // beliebig, echt. 
    char *foo = "welt"; 
    char *bar = "welJ"; 
    printf("%ld\n", hashing((void*)foo, strlen(foo), irgendwas)); 
    printf("%ld\n", hashing((void*)bar, strlen(bar), irgendwas)); 
    return 0;
}

    Ausgabe:

    12
12

    Wenn du von einer größeren Wertemenge in eine Kleinere abbildest, kann es immer zu Kollosionen kommen, egal wie toll die Hashfunktion ist 😣

    0
  • V

    life schrieb:

    Wenn du von einer größeren Wertemenge in eine Kleinere abbildest, kann es immer zu Kollosionen kommen, egal wie toll die Hashfunktion ist 😣

    auch bei

    wert = (wert + ptr[i]) * 31;

    ? ich seh da grad keine kollission (außer bei größe 31, 62, 93...).

    0
  • C

    zwei zahlen muessen nicht gleich sein, nur damit sie auch modulo X gleich sind.

    0
  • L

    volkard schrieb:

    life schrieb:

    Wenn du von einer größeren Wertemenge in eine Kleinere abbildest, kann es immer zu Kollosionen kommen, egal wie toll die Hashfunktion ist 😣

    auch bei

    wert = (wert + ptr[i]) * 31;

    ? ich seh da grad keine kollission (außer bei größe 31, 62, 93...).

    Wenn du behauptest es kann keine Kollisionen geben, behaupteste ja, dass die Hashfunktion injektiv ist. Surjektiv sollte sie weiterhin sinvollerweise sowieso sein. Somit kannst du mir sicherlich eine Umkehrfunktion zu deiner Hashfunktion angeben, die den Hashwert nimmt und das entsprechend gehashte Objekt zurückgibt.

    Dass es eine solche Umkehrfunktion nicht geben kann, sollte klar sein, sofern size kleiner ist als die Anzahl der möglichen unterschiedlichen Objekte die man in die Hashfunktion geben kann. Entsprechend kann deine Hashfunktion unter den gleichen Bedingungen nicht injektiv sein...

    Übrigens führt das gleiche Beispiel von oben auch hier wieder zur Kollision. Weiter wäre die Hashfunktion selbst ohne das Modulo am Ende nicht injektiv..

    0
  • C

    vergiss nicht, es gibt registerbreiten, die wie modulo wirken.

    (ich geh mal davon aus, dass hier keiner ne bignum lib verwendet)

    0
  • L

    c.rackwitz schrieb:

    vergiss nicht, es gibt registerbreiten, die wie modulo wirken.

    (ich geh mal davon aus, dass hier keiner ne bignum lib verwendet)

    Naja dann ist die (hash)-funktion erst recht nicht injektiv und es kann Kollisionen geben.

    Aber einen Überlauf von "wert" sollte imho hier eigentlich nicht stattfinden, da ja immer nur 4 byte aufeinmal gehasht werden sollen (so hab ichs jedenfalls verstanden) und in unsigned long auch "normalerweise" mindestens 4 byte reinpassen sollten. Also gibt es keinen Überlauf bei der *256 Variante und bei der *31 Variante sowieso nicht.

    0
Anmelden zum Antworten