@Taulmarill

Quote

ah, ok. da hab ich wohl bei der diskussion um hashing-algorythmen was falsch verstanden.

Eigentlich hat das mit Hashing-Algorithmen nicht viel zu tun: unabhängig vom spezifischen Hashing-Algorithmus, muß sowohl bei "keys" als auch bei "values" die Hash-Tabelle traversiert werden (gleichgültig über welchen Algorithmus gehasht wird). Und ob ich dann bei jeder bei der Traversierung erreichten Zelle auf den Key oder auf den Value zugreife ist relativ wurscht. Jedenfalls würde es es keinen Sinn machen, eine Hash-Tabelle einmal so und das andere mal so zu traversieren. Daher ist die Reihenfolge bei "keys" und "values" identisch (es würde sogar extra-Aufwand erfordern, dies anders zu realisieren).

Hope this helps.

Gruß, Doc\n\n

<!--EDIT|docsnyder|1160584951-->

Es wird aber ein Extraaufwand dazu verwendet, dass bei zwei verschiedenen Perl-Läufen die Reihenfolgen (fast immer) verschieden sind. Innerhalb eines Laufes bleibt sie aber natürlich gleich.

@Crian

Nein, ein extra-Aufwand wird nicht verwendet, damit die Reihenfolge der Hashtraversierung bei verschiedenen Perl-Läufen (ich nehme an, Du meinst damit Aufrufe eines Skriptes) verschieden ist. Das kann an verschiedenen Dingen liegen, z.B. wird die Grösse einer Hash-Tabelle (Anzahl Slots) aufgrund einer Heuristic ermittelt (man braucht eine gewisse Anzahl an Slots, auch wenn der Hash noch leer ist, um Kollisionen gering zu halten). Diese Heuristic kann von der Anzahl der zu erwartenden Einträgen, dem zur Verfügung stehenden Systemspeicher oder anderen Dingen abhängen (und sollte eine Primzahl sein). Und wenn die Grösse der Hash-Tabelle unterschiedlich ist, werden die Slots (bei gleichen Daten! ) in der Regel auch unterschiedlich belegt, und es gibt an unterschiedlichen Stellen Kollisionen, usw. All das bewirkt, daß bei gleicher Traversierung Hash-Elemente an unterschiedlichen Stellen im Hash gefunden werden, von Lauf zu Lauf.

Gruß, Doc\n\n

<!--EDIT|docsnyder|1160665007-->

Quote

Since Perl 5.8.1 the ordering is different even between different runs of Perl for security reasons (see "Algorithmic Complexity Attacks" in perlsec).

Quote

Since Perl 5.8.1 the ordering is different even between different runs of Perl for security reasons (see "Algorithmic Complexity Attacks" in perlsec).

Oops, da hab ich wohl wieder mal was dazugelernt! *grins*

Gruß, Doc

[quote=Taulmarill,12.10.2006, 17:28]

Quote

Since Perl 5.8.1 the ordering is different even between different runs of Perl for security reasons (see "Algorithmic Complexity Attacks" in perlsec).

[/quote]
Das scheint bei mir irgendwie nicht zu funktionieren.

Die Ausgabe von

ist immer dieselbe (wxefabmnstyzuvcdklqrghijop). Unabhängig davon, ob PERL_HASH_SEED auf irgend etwas gesetzt ist oder nicht. Auch wenn ich %h in einer Schleife fuelle, kommt immer dieselbe Ausgabe (wenn auch eine andere als oben), und die Ausgabe von Data::Dumper ändert sich auch nie.

Ich habe perl-5.8.8, und in perl -V steht auch nicht USE_HASH_SEED_EXPLICIT (davon habe ich in perlrun gelesen).

das ist ganz schön seltsam. ich hab hier den selben effekt. zusätzlich habe ich mit der shell-variable PERL_HASH_SEED_DEBUG=1 mit noch den gerade aktiven seed ausgeben lassen. der ändert sich auch mit jedem lauf von perl, nur die reienfolge des hash bleibt immer die selbe.

ich hab mal bei perlmonks gesucht, und diese diskussion gefunden http://perlmonks.com/?node_id=557616. es scheint so, als ob der zufallsfaktor nur dann benutzt wird, wenn es viele kollisionen innerhalb eines hashes gibt.

Würde man das Hashing von der Anzahl der auftretenden Kollisionen abhängig machen, müsste man ja im voraus wissen, wieviele Kollisionen auftreten werden (und vor allem bei welchen Keys). Enthält eine Hash-Tabelle mind. ein Element, kann die Hash-Methode nicht mehr geändert/randomisiert werden, denn dann würden die bereits enthaltenen Elemente nicht mehr gefunden werden.

Ich habe die Postings bei den Perlmonks so verstanden, daß die Randomisierung einfach beim Kompilieren ausgeschaltet wurde.

Gruß, Doc