Hash Werte

Nackenspoiler_Joe

Wie berechne ich Hash Werte ? Wir sollen sie mit dem Horner Schema berechnen. Wir sollen sie in unsigned Arithmetik erechnen und dann war da noch was mit Modulo Ergebnis... weiß leider nicht wie man das macht. Kann mir hier einer helfen ? Das wäre super

beim Horner Schema soll das x immer 125 sein. Es soll z.B. ein Wort "abcd" berechnet werden nach folgendem Schema:

'a' * 125^4 + 'b' * 125³ + 'c' + 125² + 'd' * 125

CStoll

Klammere doch mal stückweise die 125 (bzw. x) aus, dann wird dir die Rechnung eventuell klarer:
f = (((('a')*125+'b')*125+'c')*125+'d')*125

Nackenspoiler_Joe

ok, aber es muss ja dynamisch nach der Wortlänge gehen... der Grad verändert sich dadurch

CStoll

dann versuch's mal mit einer for()-Schleife:

f=0;
for(i=0;i<strlen(input);++i)
  f=x*f+input[i];

Nackenspoiler_Joe

Wenn man das so multipliziert ergibt f=x*f+input[i]; f*x doch immer 0 oder nicht ?
oder ist das das Priinzip des Hash werst ?

CStoll

rechnen wir mal diese Schleife mit der Eingabe "abcd" (und x=125) durch, dann wird es eventuell klarer:

i  falt  fneu
0  0       0*125+'a'=97 ('a'=0x61=97)
1  97     97*125+'b'=12223=191 ('b'=98, char-Rechnung kappt höherwertige Bytes)
2  191   191*125+'c'=23974=166
3  166   166*125+'d'=20850=114
4  -> Schleifenende

Nackenspoiler_Joe

ok, das habe ich verstanden

Mein Quelltest im moment:

unsigned hash(const char word[], int maxtab)
{
    printf("\nHASH");
	puts(word);

	int i, grad, x = 125, j, result;
	for(i=0;word[i] != '\0';i++)
		;
	printf("\nWortlaenge: %i", i);
	grad = i-1;

	printf("\nGrad: %i",grad);

	for(j=0;j <= grad; j++)
	{
		printf("\n%i", word[j]);
		result = 0;
		result =  125 * result + word[j];
	}
	printf("\nErgebnis: %i", result);
	return result;
}

Ist das Ergebnis "114" nun der Hashwert ?

Nackenspoiler_Joe

Mein Ergebnis ist immer der 'a'-Wert des letzten Zeichens des WOrts... das ist doch nicht ganz richtig oder ?

CStoll

Du solltest die Zeile "result=0;" vor die Schleife ziehen, dann klappt das auch

Nackenspoiler_Joe

upsala... nu gehts.. nu sieht es so aus:

unsigned hash(const char word[], int maxtab)
{
    printf("\nHASH");
	puts(word);

	int i, grad, x = 125, j, result;
	for(i=0;word[i] != '\0';i++)
		;
	printf("\nWortlaenge: %i", i);
	grad = i-1;
	printf("\nGrad: %i",grad);
	result = 0;

	for(j=0;j <= grad; j++)
	{
		printf("\n%i", word[j]);
		result =  125 * result + word[j];
	}
	printf("\nErgebnis: %i", result);
	return result;
}

jetzt kommt für "abcd" der Wert 190996850 raus... sorry das ich da nicht durchsteige...

Nackenspoiler_Joe

Bist du noch da ? Ich finde den Fehler nicht

CStoll

am besten deklarierst du result als char, dann werden die extrem hohen Werte bei jedem Schleifendurchlauf auf 1 Byte abgeschnitten.

Nackenspoiler_Joe

ok, nu kommt das richtige raus... hoffe das mein Prof das leiden mag ... Vielen Dank