Alphabetisch sortierende Hashfunktion

[implementation]

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?

[Namenloser]

Ich versteh ehrlich gesagt den Sinn nicht so ganz – Wenn du einen Hash willst, der die gleichen Sortiereigenschaften hat wie der Originalwert, dann brauchst du eine 1:1-Abbildung. Das widerspricht aber der Logik eines Hashs, da beim Hash eine größere Menge auf eine kleinere Menge abgebildet wird.

Imo ist das, was du vorhast, nicht machbar.

Vielleicht führst du mal ein bisschen aus, wofür du das glaubst zu brauchen.

[Sailor]

Nein, Du brauchst keine 1:1-Abbildung, sondern eine eineindeutige. Das heißt, die Hashwerte unterschiedlicher Schlüssel müssen unterschiedlich sein, ansonsten gibt es Kollisionen. Das ist das Problem, mit dem sich Hash-Funktionen rumschlagen. Bis jetzt ist m.E. keine Funktion gefunden worden, die das vom Vorposter gewünschte im allgemeinen Fall leistet. Siehe dazu die entsprechende Abhandlung im Band "Sorting and Searching" von Knuth.

[mkinzler]

Zitat:

Nein, Du brauchst keine 1:1-Abbildung, sondern eine eineindeutige.

Man setzt aber Hashes ( z.B. in der Cryptographie) gerade ein, weil sie den Vorteil haben nicht eineindeutig zu sein.

Zitat:

Das heißt, die Hashwerte unterschiedlicher Schlüssel müssen unterschiedlich sein, ansonsten gibt es Kollisionen. Das ist das Problem, mit dem sich Hash-Funktionen rumschlagen.

Das ist kein Problem, sonderm ein Grundprinzip von Hashes.

[Furtbichler]

Zitat von Sailor:

Nein, Du brauchst keine 1:1-Abbildung, sondern eine eineindeutige.

Eine eindeutige Funktion existiert genau dann, wenn der Wertebereich der Hashfunktion mehr oder genausoviele Werte enthält, wie der Wertebereich des Schlüssels (also des zu hashenden Wertes).

Zitat von NamenLozer:

Vielleicht führst du mal ein bisschen aus, wofür du das glaubst zu brauchen.

Der Frage schließe ich mich an.

[implementation]

Gut, ihr habt natürlich recht. Das kann für den Allgemeinen Fall gar nicht gehen. Das sehe ich leicht ein.

Zitat von NamenLozer:

Vielleicht führst du mal ein bisschen aus, wofür du das glaubst zu brauchen.

Ich habe einen Rot-Schwarz-Baum aus Zuordnungen: Der Schlüssel ist ein String, der Wert ein Objekt.
Nun wäre es ein wenig blöd, immer vollständige String-Vergleiche zu machen, daher ist der Schlüssel eigentlich ein Hash des Strings.
So, und angenommen der Hash hat jetzt genannte Eigenschaft - dann kommt beim InOrder-Traversieren ohne zusätzlichen Aufwand ganz automatisch eine sortierte Liste raus

Je länger ich mir meine Funktion anschaue, desto mehr denke ich: Eigentlich ist sie schon alles, was ich will. Die Beschränkung auf 11 Buchstaben ist für mich völlig verkraftbar; dann jage ich halt hinterher noch ein Sort() über die Liste, das geht dann ja schnell, die ist dann ja schon stark vorsortiert.

Das Problem (eigentlich mehr eine Spielerei) ist damit wohl schon gelöst. Danke trotzdem an euch!

[Furtbichler]

Wenn deine Implementierung eines RB-Baums eine (wichtige) Spielerei ist, würde ich mich nicht mit diesen Kinkerlitzchen à la "wie kann ich einen Stringvergleich schneller machen". Hierbei vergisst Du vollkommen, das ein Stringvergleich hochoptimiert ist. Dein Int64-Vergleich vergleicht ja -so gesehen- auch 8 Bytes und ob Du do sooo viel rausholst, sei mal dahingestellt.

Wichtiger ist hier eher der richtige Algorithmus bzw. die Struktur. Wenn es um derartige Strukturen geht (schnelles einfügen, suchen, löschen etc.) dann würde ich mich neben RB-Baumen auch mit Hashmaps, Tries und B-Baumen beschäftigen. "Als Spielerei".

[implementation]

Zitat von Furtbichler:

eine (wichtige) Spielerei

Wichtig definitiv nicht.

Zitat:

Hierbei vergisst Du vollkommen, das ein Stringvergleich hochoptimiert ist.

Ich werde mir die Implementierung mal anschauen. Könnte durchaus sein, dass der Unterschied vernachlässigbar ist. Mal gucken.

Zitat:

dann würde ich mich neben RB-Baumen auch mit Hashmaps, Tries und B-Baumen beschäftigen.

Hashmaps hatte ich rausgestrichen, weil sie nicht sortieren (und mein Int64 ist wohl zu lang dafür ).
B-Bäume eignen sich - wie ich das sehe - ja eher für mehrere Schlüssel pro Knoten, oder? Sehe da sonst nichts wirklich anderes
Die Tries sehen aber interessant aus. Damit werde ich mich nochmal auseinandersetzen. Danke für den Tipp!



// Add: Hab mal String- und Hashvergleich verglichen: (für Stringlängen, wie sie bei mir etwa vorkommen; Zeiten gemessen für 16 verschiedene Strings, x100000 Durchläufe)

Code:

CRC64 Digest Calculation:  863
Alphabetical Digest Calculation:  999
Digest Comparison:  8
String Comparison:  266

So wie ich das sehe, ist die Hashnutzung erst dann schneller, wenn er mindestens fünfmal verglichen wird. Ich habe momentan im Schnitt ca. 8 Vergleiche pro Suche, daher dürfte das erfüllt sein. Aber ein Elefant steckt da echt nicht zwischen. Aber erstmal schauen, wie das mit dem Trie aussieht.

[Furtbichler]

Wenn Du sortieren willst, ist eine Hashmap ungeeignet. Dafür verwendet man z.B. den RB-Baum, oder eben B-Bäume für sehr sehr große Datenmengen bzw. dann, wenn die Daten/Indexe persistent gehalten werden sollen.

Du kannst Dir auch mal eine Skip List anschauen.

Allerdings solltest Du dir genau überlegen, weshalb Du die Daten unbedingt sortiert vorhalten musst. Zum schnellen Suchen gibt es nichts Besseres als eine Hashmap. In fast allen Fällen ist da sortierte Ausgeben/Anzeigen sekundär.