Hashfunktion für einen String

[mekakic]

Hi,

ich habe eben für ein C Programm, was ich nutze und dessen Quelltext ich habe, den Zugriff von einem linearen Array auf eine Hash-Tabelle umgestellt. Die Laufzeit ist damit über 4x besser geworden. Als Hash-Key hatte ich mir überlegt ich verwende einen String, dessen ASCII Werte ich aufsummiere und dort Modulo durch eine Primzahl teile. Gibt es einen flotten aber besseren Weg um einen String zu einem Index zu hashen?

Bei meiner Hashtable sind 60% aller Slots belegt bei im Schnitt 3, aber auch mehrfach mal ~20 Kollisionen. Wie könnte ich für Strings eine bessere Verteilung erreichen?

[Shink]

Ich bin mal faul und sage: Du könntest es einfach so wie in der JRE-Klasse machen; irgendwas werden sich die Typen wohl gedacht haben dabei.
for (int i = 0; i < len; i++) {
h = 31*h + val[off++];
}

[DocEW]

Vielleicht mal in ganzer Schönheit, sonst weiß man nicht was h, val und off sind. ;)
/** The value is used for character storage. */
private final char value[];

/** The offset is the first index of the storage that is used. */
private final int offset;

/** The count is the number of characters in the String. */
private final int count;

/** Cache the hash code for the string */
private int hash; // Default to 0

public int hashCode() {
int h = hash;
if (h == 0) {
int off = offset;
char val[] = value;
int len = count;

for (int i = 0; i < len; i++) {
h = 31*h + val[off++];
}
hash = h;
}
return h;
}

[mekakic]

Danke, das hat die Auslastung der Slots zwar herabgesetzt (nur noch 51% Auslastung), aber die Verteilung ist wesentlich besser - im schlimmsten Fall sind es gerademal 4 Kollisionen (vorher 21). Das hat zwar praktisch nichts mehr für die Laufzeit gebracht (1.3% besser), aber evtl. eben wenn die Eingabedaten noch größer werden.