Sortierreihenfolge von Hashes

Vom einfachen Programm zum fertigen Debian-Paket, Fragen rund um Programmiersprachen, Scripting und Lizenzierung.
Antworten
Benutzeravatar
Meillo
Moderator
Beiträge: 8782
Registriert: 21.06.2005 14:55:06
Wohnort: Balmora
Kontaktdaten:

Sortierreihenfolge von Hashes

Beitrag von Meillo » 30.03.2021 11:05:47

Abgespalten von viewtopic.php?f=32&t=180697
hikaru hat geschrieben: ↑ zum Beitrag ↑
30.03.2021 10:58:12
tobo hat geschrieben: ↑ zum Beitrag ↑
30.03.2021 10:33:41
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. ;-) )
Use ed once in a while!

Benutzeravatar
hikaru
Moderator
Beiträge: 13559
Registriert: 09.04.2008 12:48:59

Re: Youtube-dl script

Beitrag von hikaru » 30.03.2021 11:44:10

Meillo hat geschrieben: ↑ zum Beitrag ↑
30.03.2021 11:05:47
(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.

Benutzeravatar
Meillo
Moderator
Beiträge: 8782
Registriert: 21.06.2005 14:55:06
Wohnort: Balmora
Kontaktdaten:

Re: Youtube-dl script

Beitrag von Meillo » 30.03.2021 11:52:07

hikaru hat geschrieben: ↑ zum Beitrag ↑
30.03.2021 11:44:10
Meillo hat geschrieben: ↑ zum Beitrag ↑
30.03.2021 11:05:47
(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.
Use ed once in a while!

Benutzeravatar
Meillo
Moderator
Beiträge: 8782
Registriert: 21.06.2005 14:55:06
Wohnort: Balmora
Kontaktdaten:

Re: Sortierreihenfolge von Hashes

Beitrag von Meillo » 30.03.2021 13:59:18

Siehe auch diesen und den darauf folgenden Abschnitt:
https://en.wikipedia.org/wiki/Associati ... Comparison
Use ed once in a while!

dakuan
Beiträge: 97
Registriert: 28.04.2011 22:09:39

Re: Sortierreihenfolge von Hashes

Beitrag von dakuan » 30.03.2021 19:29:42

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
Beiträge: 3331
Registriert: 10.05.2008 11:23:50

Re: Sortierreihenfolge von Hashes

Beitrag von eggy » 31.03.2021 10:45:28

dakuan hat geschrieben: ↑ zum Beitrag ↑
30.03.2021 19:29:42
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
Moderator
Beiträge: 7448
Registriert: 24.05.2010 12:39:42

Re: Sortierreihenfolge von Hashes

Beitrag von wanne » 31.03.2021 12:17:24

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.
rot: Moderator wanne spricht, default: User wanne spricht.

Antworten