Hash Werte

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