AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Alphabetisch sortierende Hashfunktion

Ein Thema von implementation · begonnen am 2. Mär 2013 · letzter Beitrag vom 3. Mär 2013
Antwort Antwort
Benutzerbild von implementation
implementation

Registriert seit: 5. Mai 2008
940 Beiträge
 
FreePascal / Lazarus
 
#1

Alphabetisch sortierende Hashfunktion

  Alt 2. Mär 2013, 15:39
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?

Geändert von implementation ( 2. Mär 2013 um 15:50 Uhr)
  Mit Zitat antworten Zitat
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#2

AW: Alphabetisch sortierende Hashfunktion

  Alt 3. Mär 2013, 00:03
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.
  Mit Zitat antworten Zitat
Sailor

Registriert seit: 20. Jul 2008
Ort: Balaton
112 Beiträge
 
Delphi 2010 Professional
 
#3

AW: Alphabetisch sortierende Hashfunktion

  Alt 3. Mär 2013, 09:52
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.
  Mit Zitat antworten Zitat
mkinzler
(Moderator)

Registriert seit: 9. Dez 2005
Ort: Heilbronn
39.851 Beiträge
 
Delphi 11 Alexandria
 
#4

AW: Alphabetisch sortierende Hashfunktion

  Alt 3. Mär 2013, 10:34
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.
Markus Kinzler
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#5

AW: Alphabetisch sortierende Hashfunktion

  Alt 3. Mär 2013, 10:39
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).

Vielleicht führst du mal ein bisschen aus, wofür du das glaubst zu brauchen.
Der Frage schließe ich mich an.
  Mit Zitat antworten Zitat
Benutzerbild von implementation
implementation

Registriert seit: 5. Mai 2008
940 Beiträge
 
FreePascal / Lazarus
 
#6

AW: Alphabetisch sortierende Hashfunktion

  Alt 3. Mär 2013, 11:40
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!
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#7

AW: Alphabetisch sortierende Hashfunktion

  Alt 3. Mär 2013, 11:46
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".
  Mit Zitat antworten Zitat
Benutzerbild von implementation
implementation

Registriert seit: 5. Mai 2008
940 Beiträge
 
FreePascal / Lazarus
 
#8

AW: Alphabetisch sortierende Hashfunktion

  Alt 3. Mär 2013, 12:08
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.

Geändert von implementation ( 3. Mär 2013 um 21:42 Uhr)
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#9

AW: Alphabetisch sortierende Hashfunktion

  Alt 3. Mär 2013, 13:52
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.
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 08:36 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz