Hi,
Ich war auf der Suche nach einer Hashfunktion mit der folgenden Eigenschaft: Wenn String A alphabetisch vor String B kommt, soll auch hash(A) < hash(B) sein, und umgekehrt.
Die Folge ist: Wenn man nach den Hashes sortiert, bekommt man die gleiche Reihenfolge, wie wenn man alphabetisch sortiert.
Konkret anwenden würde ich das in einem hashenden Binären Suchbaum.
Ich habe ein wenig gesucht, und nichts gefunden. Da habe ich mir dann schnell selbst einen Algo zusammengestrickt, der die ersten 11 Buchstaben einfach "hintereinanderstopft"
Delphi-Quellcode:
// Alphabetically ordering hash
function Hash(const key: AnsiString): Int64;
(*
63-59 char 1
58-54 char 2
53-49 char 3
48-44 char 4
43-39 char 5
38-34 char 6
33-29 char 7
28-24 char 8
23-19 char 9
18-14 char 10
14-9 char 11
8-1 CRC 8
*)
var CRC: byte; i,j: integer; h: int64;
begin
// CRC 8
CRC := -1;
for i := 1 to length(key) do
begin
CRC := CRC xor byte(key[i]);
for j := 0 to 7 do
if (CRC and 1)<>0 then
CRC := (CRC shr 1) xor $AB
else CRC := CRC shr 1
end;
Result := CRC;
// 11 characters (each one 5 bits)
j := 0;
for i := 1 to length(key) do
if j<11 then
case key[i] of
'a'..'z': begin
Result := Result or ((byte(key[i])-byte('a')) shl (58-j*5));
inc(j);
end;
'A'..'Z': begin
Result := Result or ((byte(key[i])-byte('A')) shl (58-j*5));
inc(j);
end;
'0'..'9': begin
Result := Result or ((byte(key[i])-byte('0')) shl (58-j*5));
inc(j);
end;
end;
end;
Die Funktion reduziert die ersten 11 Buchstaben und Zahlen auf je 5 Bit (Case Insensitive, 0..9 = A..J = a..j; alles andere wird ignoriert) und schiebt sie hintereinander an das höherwertige Ende des Int64. Hinten dran kommt eine CRC-8 über den gesamten String, damit sich auch Strings unterscheiden, bei denen die ersten 11 Buchstaben gleich sind. Die Sortierung funktioniert also nur für die ersten 11 Buchstaben/Zahlen, dahinter wird's mehr oder weniger zufällig -- das ist für mich aber nicht weiter schlimm.
Da ich mit solchen Funktionen nicht allzu viel Erfahrung habe, frage ich mal hier:
- Wie könnte man das weiter optimieren?
- Könnte ich irgendwo Probleme bekommen?
- Gibt es vielleicht auch schon andere Algorithmen, die die gewünschte Eigenschaft auch haben?