Alphabetisch sortierende Hashfunktion

[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.