Sortierreihenfolge von Hashes

[Meillo]

Abgespalten von viewtopic.php?f=32&t=180697

Assoziative Arrays (-A) sind hash-basiert, die haben keine vorgegebene Reihenfolge.

Ich weiß. Aber irgendeine implizite Sortierung hätte ich beim Output schon erwartet (fifo, lifo, alphabetisch - keine Ahnung, irgendwas halt).

Da musst du dich in die technische Implementierung von Hashes einlesen, dann wirst du verstehen, warum sie keine Sortierung in der Art, wie du sie erwartest, haben koennen. Wenn sie diese haetten, dann sind sie entweder nachtraeglich sortiert oder es sind eben technisch keine Hashes (und verlieren damit all deren Vorteile).

Du denkst an Linked Lists und Trees zur Datenspeicherung, was auch relevante Datenstrukturen sind. Hashes (Hashmaps) sind aber nochmal eine ganz andere Datenstruktur, die andere Vorteile gegenueber Listen und Baeumen hat. Ein Nachteil ist ihre Unsortiertheit.


(Btw: Eine Sortierung haben die Eintraege ja schon, nur ist die fuer dich halt kryptisch: Sie sind nach den erzeugten Hashwerten der internen Hashfunktion sortiert. Deren Ziel ist es aber moeglichst randomisierend zu sein, weshalb du eben gerade keine Reihenfolge nachvollziehen kannst. )

[hikaru]

(Btw: Eine Sortierung haben die Eintraege ja schon, nur ist die fuer dich halt kryptisch: Sie sind nach den erzeugten Hashwerten der internen Hashfunktion sortiert.

Eben das meine ich. Ich erwarte hier keine klar sortierte Ausgabe in irgendeiner Form. Ich habe keine Erfahrung mit Hashes in bash, aber in Perl lässt sich meiner Erfahrung nach zumindest irgendein Muster erahnen. Das ist nicht stringent, so dass man damit arbeiten könnte, aber meist kann man beim Draufschauen sowas sagen wie: "Oh, das war jetzt (im Wesentlichen) fifo." (kann beim nächsten Beispiel anders sein)

Vielleicht unterscheiden sich die Implementierungen zwischen den Sprachen. Vielleicht ist auch die Stichprobe in diesem Beispiel zu klein um eine Tendenz zu erkennen.

[Meillo]

(Btw: Eine Sortierung haben die Eintraege ja schon, nur ist die fuer dich halt kryptisch: Sie sind nach den erzeugten Hashwerten der internen Hashfunktion sortiert.

Eben das meine ich. Ich erwarte hier keine klar sortierte Ausgabe in irgendeiner Form. Ich habe keine Erfahrung mit Hashes in bash, aber in Perl lässt sich meiner Erfahrung nach zumindest irgendein Muster erahnen. Das ist nicht stringent, so dass man damit arbeiten könnte, aber meist kann man beim Draufschauen sowas sagen wie: "Oh, das war jetzt (im Wesentlichen) fifo." (kann beim nächsten Beispiel anders sein)

Vielleicht unterscheiden sich die Implementierungen zwischen den Sprachen. Vielleicht ist auch die Stichprobe in diesem Beispiel zu klein um eine Tendenz zu erkennen.

Je nach Sprache und Implementierung kann sich das unterscheiden, moeglicherweise wechseln manche Sprachen auch dynamisch zwischen Liste und Hash, je nachdem wie viele Werte drinstecken -- keine Ahnung.

Meines Wissens ist eine Hashfunktion dann besser wenn sie die Hashwerte zufaelliger und gleichmaessiger ueber den Wertebereich verteilt. Das widerspricht einem erkennbaren Muster jeglicher Art. Soweit das was ich zur Theorie und technischen Realisierung von Hashes weiss.

... aber bezueglich des Threads ist das eh alles OT ... und ich sollte das besser mal abspalten in einen separaten Thread. Erledigt.

[Meillo]

Siehe auch diesen und den darauf folgenden Abschnitt:
https://en.wikipedia.org/wiki/Associati ... Comparison

[dakuan]

Soweit ich das verstanden habe ist es nicht erwünscht, dass da irgendein Muster erkennbar ist. Wenn ich Herrn N. Wirth (Algorithmen und Datenstrukturen) damals richtig verstanden habe, geht es darum, Datensätze (Indexwerte) möglichst gleichmäßig über einen gegebenen Wertebereich zu verteilen.

Aktuell befasse ich mich mit Thumbnail Dateien (Vorschaudateien für Dateibrowser). Da werden die Dateinamen der Thumbs aus der MD5 Summe (Hash) des Pfades der Originaldatei gebildet. Da ist kein erkennbares Muster vorhanden. Schon kleine Änderungen im Dateinamen erzeugen völlig andere Hash Werte.

[eggy]

Soweit ich das verstanden habe ist es nicht erwünscht, dass da irgendein Muster erkennbar ist. Wenn ich Herrn N. Wirth (Algorithmen und Datenstrukturen) damals richtig verstanden habe, geht es darum, Datensätze (Indexwerte) möglichst gleichmäßig über einen gegebenen Wertebereich zu verteilen.

Jein, das gilt bei "guten" Hashfunktionen. Eine Hashfunktion, die alles auf "A" abbildet, ist ebenfalls ne Hashfunktion, wenn auch eine mit relativ wenig praktischem Nutzen. Für Krypto brauchst Du die "guten", die u.a. zufällige nicht prädiktive Gleichverteilung mitbringen etc.

[wanne]

Speziell zur Bash: In Debian sind assoziative Arrays eher eine nach Hashes sortierte Liste. Ähnliches
Siehe auch: https://savannah.gnu.org/patch/?9850 (apparently, I'm not the first bezieht sich vermutlich auf mich )

Für Krypto brauchst Du die "guten", die u.a. zufällige nicht prädiktive Gleichverteilung mitbringen etc.

Für ne gute Hash Funktion (wie du sie für hashtables haben willst) willst du, dass sie schnell zu berechnen ist und wie du gesagt hast, dass sie die Hashes "wild" über den Raum verteilt. (Siehe avalanche Effect.)


Für crypto willst du cryptografische hash funktionen. die wollen noch ein bisschen mehr:
1. Ohne den key zu kennen soll es nicht schneller als in exponentieller laufzeit möglich sein den key zu einem value zu finden. (Da fällt z.B. LM durch oder crc, die sonst als gute Hash-funktionen gelten)
2. Es soll nur mit ϴ(2^(n/2)) möglich sein zwei Values mit dem gleichem Hash zu finden.