Perl hash and rehash seeds; deterministic hash ordering

Discussion in 'Perl Misc' started by ozgune@gmail.com, Jan 19, 2007.

  1. Guest

    Hi -

    I just upgraded to Perl 5.8.6, and am evaluating the effect of random
    hash ordering on my systems. Surprisingly, I seem *unaffected* by Perl
    hash seeds (The following is a RHEL 3 box).

    % perl -v
    This is perl, v5.8.6 built for Linux-2.4c2.3-i686-64int

    % perl -le '@a="a".."z";@a{@a}=();print keys %a'
    HASH_SEED = 10308426221955932222
    wraxdjyukhgftienvmslcpqbzo

    % perl -le '@a="a".."z";@a{@a}=();print keys %a'
    HASH_SEED = 2190859344420079461
    wraxdjyukhgftienvmslcpqbzo

    I tried this on a Fedora 3 box (5.8.6), and got the same behavior. On
    OSX, the ordering is random as expected.

    Looking into the source a little deeper, I see two different hash seeds
    and two hash functions: PL_hash_seed (used by PERL_HASH) and
    PL_rehash_seed (used by PERL_HASH_INTERNAL). PL_rehash_seed is
    initialized in perl.c, but PL_hash_seed isn't.

    "hv.c" seems to be calling PERL_HASH which relies on the uninitialized
    seed. I added some printfs to the code, and ran perl:

    % ./perl5.8.8 -le '@a="a".."z";@a{@a}=();print keys %a'
    PL_hash_seed = 0
    PL_rehash_seed = 17891139134198775779
    IN HASH (NOT INTERNAL): PL_hash_seed = 0
    IN HASH (NOT INTERNAL): PL_hash_seed = 0
    ..........
    wraxdjyukhgftienvmslcpqbzo


    Why are there two different hash seeds and hash functions? How can I
    know for sure which one is going to be called?

    Thanks,

    Ozgun.
     
    , Jan 19, 2007
    #1
    1. Advertising

  2. On 01/19/2007 04:01 PM, wrote:
    > Hi -
    >
    > I just upgraded to Perl 5.8.6, and am evaluating the effect of random
    > hash ordering on my systems. Surprisingly, I seem *unaffected* by Perl
    > hash seeds (The following is a RHEL 3 box).
    >
    > % perl -v
    > This is perl, v5.8.6 built for Linux-2.4c2.3-i686-64int
    >
    > % perl -le '@a="a".."z";@a{@a}=();print keys %a'
    > HASH_SEED = 10308426221955932222
    > wraxdjyukhgftienvmslcpqbzo
    >
    > % perl -le '@a="a".."z";@a{@a}=();print keys %a'
    > HASH_SEED = 2190859344420079461
    > wraxdjyukhgftienvmslcpqbzo
    > [...]


    FWIW, I'm getting the same behavior on Debian 3.1 i386 and Perl 5.9.4.


    --
    Windows Vista and your freedom in conflict:
    http://www.regdeveloper.co.uk/2006/10/29/microsoft_vista_eula_analysis/
     
    Mumia W. (NOSPAM), Jan 20, 2007
    #2
    1. Advertising

  3. Guest

    Any ideas if there is a better group to post this?

    From
    http://www.xray.mpe.mpg.de/mailing-lists/perl5-porters/2003-06/msg00584.html
    on DoS attacks:

    >> The neat effect is that now this:


    ../perl -le '@a="a".."z";@a{@a}=();print keys %a'

    gives a different result for each run. That _really_ should teach
    people
    not to expect any particular ordering of hash keys...

    On our systems however:

    % perl -le '@a="a".."z";@a{@a}=();print keys %a'
    wraxdjyukhgftienvmslcpqbzo

    % perl -le '@a="a".."z";@a{@a}=();print keys %a'
    wraxdjyukhgftienvmslcpqbzo


    wrote:
    > Hi -
    >
    > I just upgraded to Perl 5.8.6, and am evaluating the effect of random
    > hash ordering on my systems. Surprisingly, I seem *unaffected* by Perl
    > hash seeds (The following is a RHEL 3 box).
    >
    > % perl -v
    > This is perl, v5.8.6 built for Linux-2.4c2.3-i686-64int
    >
    > % perl -le '@a="a".."z";@a{@a}=();print keys %a'
    > HASH_SEED = 10308426221955932222
    > wraxdjyukhgftienvmslcpqbzo
    >
    > % perl -le '@a="a".."z";@a{@a}=();print keys %a'
    > HASH_SEED = 2190859344420079461
    > wraxdjyukhgftienvmslcpqbzo
    >
    > I tried this on a Fedora 3 box (5.8.6), and got the same behavior. On
    > OSX, the ordering is random as expected.
    >
    > Looking into the source a little deeper, I see two different hash seeds
    > and two hash functions: PL_hash_seed (used by PERL_HASH) and
    > PL_rehash_seed (used by PERL_HASH_INTERNAL). PL_rehash_seed is
    > initialized in perl.c, but PL_hash_seed isn't.
    >
    > "hv.c" seems to be calling PERL_HASH which relies on the uninitialized
    > seed. I added some printfs to the code, and ran perl:
    >
    > % ./perl5.8.8 -le '@a="a".."z";@a{@a}=();print keys %a'
    > PL_hash_seed = 0
    > PL_rehash_seed = 17891139134198775779
    > IN HASH (NOT INTERNAL): PL_hash_seed = 0
    > IN HASH (NOT INTERNAL): PL_hash_seed = 0
    > .........
    > wraxdjyukhgftienvmslcpqbzo
    >
    >
    > Why are there two different hash seeds and hash functions? How can I
    > know for sure which one is going to be called?
    >
    > Thanks,
    >
    > Ozgun.
     
    , Jan 20, 2007
    #3
  4. Bo Lindbergh Guest

    There's a flag in each hash that controls whether the random or the
    non-random hash seed is used. Hashes start out non-random and switch to
    random if and when the hsplit function thinks it's a good idea. Search for
    "Pathological data" in hv.c for the details.

    /Bo Lindbergh
     
    Bo Lindbergh, Jan 21, 2007
    #4
  5. Guest

    Thanks, that clears it; I wrongfully thought the original post on the
    issue (Patch #22371) cited the final implementation behavior.

    In summary, Perl gives no guarantees about the ordering of an hash's
    key value pairs, and documents this behavior. Perl 5.8.8's
    implementation will give a deterministic order until the hash split
    can't redistribute the entries evenly. (More specifically, after a
    split, if the longest chain in the hash still has a lot of entries,
    Perl switches to random seeds.)

    Ozgun.

    Bo Lindbergh wrote:
    > There's a flag in each hash that controls whether the random or the
    > non-random hash seed is used. Hashes start out non-random and switch to
    > random if and when the hsplit function thinks it's a good idea. Search for
    > "Pathological data" in hv.c for the details.
    >
    > /Bo Lindbergh
     
    , Jan 22, 2007
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. jt

    larger seeds for Mersenne

    jt, Feb 5, 2004, in forum: Python
    Replies:
    0
    Views:
    335
  2. jt

    larger seeds for Mersenne

    jt, Feb 6, 2004, in forum: Python
    Replies:
    0
    Views:
    331
  3. Replies:
    8
    Views:
    337
    Kevin Walzer
    Sep 5, 2006
  4. nbigaouette

    Z-Ordering (Morton ordering) question

    nbigaouette, Nov 5, 2009, in forum: C Programming
    Replies:
    2
    Views:
    2,220
  5. Andreas Habel

    Can I rehash during execution ?

    Andreas Habel, Aug 29, 2003, in forum: Ruby
    Replies:
    5
    Views:
    115
    Charles Hixson
    Sep 1, 2003
Loading...

Share This Page