Hashcode berechnen

Wissenschaft Informatik
#1

Hallo, wie kann ich aus einer Zeichenfolge (ca. 10-30 Zeichen) einen Hashcode berechnen. Meine Anforderungen an den Algorithmus sind, dass er erstens unwahrscheinlich schnell ist und zweitens möglichst gut sich auf möglichst viele Hash-Felder verteilen lässt.

Ich habe mal einen primitiven Ansatz mir ausgedacht, weiss aber nicht ob der so ideal ist. Ich zähl einfach den Ascii-Code jedes Zeichens zusammen und mach dann ein Modulo durch die Feldanzahl.

Hier der Code:

#define HASH\_HEIGHT 1000
char\* string = "Dies ist der Text";
int key = 0;
char\* iterate = string;
while (\*iterate != '\0')
{
 key += \*iterate;
 iterate++;
}
key %= HASH\_HEIGHT;
#2

Hi Bruno :wink:))

Gerade für Zeichenfolgen gibt es hervorragende Hash-Funktionen aus dem Bereich des Compilerbaus. Du kannst sie im sog. „Drachenbuch“ (weil auf dem Einband ein Drache drauf ist) nachlesen:

A.V. Aho, R. Sethi, J.D. Ullman, „Compilerbau Teil 1“, ISBN 3-89319-150-x Buch anschauen

Dort steht auf Seite 535 die allerbeste, bisher bekannte Hash-Funktion in Form eines C-Source. Diese ist jedoch relativ langsam. Daher hat sich eine andere Hash-Funktion, die nur minimal schlechter, dafür aber um einiges schneller ist, als Standard durchgesetzt:

unsigned long h= 0;
for (i=0; string[i]; ++i)
 h= 65599 \* h + string[i];

Der 32-Bit-Überlauf wird ignoriert. Am Ende musst du h noch modulo-dividieren durch die Größe hashsize deiner Hash-Tabelle, also

h= h % hashsize;

Es gibt übrigens die besten Resultate, wenn hashsize die erste Primzahl über einem vollen Hunderter ist, also die erste Primzahl über 100, 200, 300, 400, …

Ich hoffe, ich konnte dir weiterhelfen …

cu Stefan.

#3

Ich hoffe, ich konnte dir weiterhelfen …

Klaro, vielen Dank für deine Tips :smile:
Aber ich weiss nicht ob ich dieser Funktion so recht trauen kann. Wie ist das denn mit diesem Überlauft, also wenn die Zahl zu gross wird? Ist das nicht compilerabhängig ob dann auf die kleinste Zahl zurückgesprungen wird oder ob es einen Fehler gibt? Nicht dass ich den Code dann nicht gescheit compiliert kriege oder sogar runtime-Fehler erhalte.

Bruno

#4

Hi Bruno :wink:))

Aber ich weiss nicht ob ich dieser Funktion so recht trauen
kann. Wie ist das denn mit diesem Überlauft, also wenn die
Zahl zu gross wird? Ist das nicht compilerabhängig ob dann auf
die kleinste Zahl zurückgesprungen wird oder ob es einen
Fehler gibt? Nicht dass ich den Code dann nicht gescheit
compiliert kriege oder sogar runtime-Fehler erhalte.

Alle Compiler und Maschinen, die ich kenne, ignorieren bei einem Überlauf einfach die Bits, die links zu viel sind, und rechnen mit den untersten 32-Bit weiter. Daher sollte es wunderbar klappen :wink:))

cu Stefan.

#5

Alle Compiler und Maschinen, die ich kenne, ignorieren bei
einem Überlauf einfach die Bits, die links zu viel sind, und
rechnen mit den untersten 32-Bit weiter. Daher sollte es
wunderbar klappen :wink:))

OK :smile: alle ist zufriedenstellend :wink: mir langt MS VC++ und gcc auf Linux

Bru

#6

Hi,
hier ist zusätzlich eine Beschreibung des MD5-Algorithmus’:
http://www.ece.arizona.edu/~medenis/hw2/sem_pro.htm#D

Gruß

J.

#7

Hi Bru :wink:))

Ja, die beiden kenne ich auch :wink:))
Sie arbeiten garantiert so, dass die Hash-Funktion wunderbar funktioniert.

cu Stefan.