Font
[thread]8405[/thread]

Hashes verbinden (page 2)



<< |< 1 2 >| >> 19 entries, 2 pages
docsnyder
 2006-10-11 20:40
#70682 #70682
User since
2005-09-08
300 articles
BenutzerIn
[Homepage] [default_avatar]
@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-->
Crian
 2006-10-12 14:06
#70683 #70683
User since
2003-08-04
5866 articles
ModeratorIn
[Homepage]
user image
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.
s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite
docsnyder
 2006-10-12 18:55
#70684 #70684
User since
2005-09-08
300 articles
BenutzerIn
[Homepage] [default_avatar]
@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-->
Taulmarill
 2006-10-12 19:28
#70685 #70685
User since
2004-02-19
1750 articles
BenutzerIn

user image
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).
$_=unpack"B*",~pack"H*",$_ and y&1|0& |#&&print"$_\n"for@.=qw BFA2F7C39139F45F78
0A28104594444504400 0A2F107D54447DE7800 0A2110453444450500 73CF1045138445F4800 0
F3EF2044E3D17DE 8A08A0451412411 F3CF207DF41C79E 820A20451412414 83E93C4513D17D2B
docsnyder
 2006-10-12 20:23
#70686 #70686
User since
2005-09-08
300 articles
BenutzerIn
[Homepage] [default_avatar]
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
betterworld
 2006-10-13 01:00
#70687 #70687
User since
2003-08-21
2613 articles
ModeratorIn

user image
[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
Code: (dl )
perl -le '%h = ("a".."z"); print %h'

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).
Taulmarill
 2006-10-13 12:54
#70688 #70688
User since
2004-02-19
1750 articles
BenutzerIn

user image
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.
$_=unpack"B*",~pack"H*",$_ and y&1|0& |#&&print"$_\n"for@.=qw BFA2F7C39139F45F78
0A28104594444504400 0A2F107D54447DE7800 0A2110453444450500 73CF1045138445F4800 0
F3EF2044E3D17DE 8A08A0451412411 F3CF207DF41C79E 820A20451412414 83E93C4513D17D2B
Taulmarill
 2006-10-13 13:07
#70689 #70689
User since
2004-02-19
1750 articles
BenutzerIn

user image
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.
$_=unpack"B*",~pack"H*",$_ and y&1|0& |#&&print"$_\n"for@.=qw BFA2F7C39139F45F78
0A28104594444504400 0A2F107D54447DE7800 0A2110453444450500 73CF1045138445F4800 0
F3EF2044E3D17DE 8A08A0451412411 F3CF207DF41C79E 820A20451412414 83E93C4513D17D2B
docsnyder
 2006-10-13 14:28
#70690 #70690
User since
2005-09-08
300 articles
BenutzerIn
[Homepage] [default_avatar]
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
<< |< 1 2 >| >> 19 entries, 2 pages



View all threads created 2006-10-11 17:19.