Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

associative array - hash function

by InfiniteLoop (Hermit)
on Apr 15, 2008 at 02:41 UTC ( #680418=perlquestion: print w/replies, xml ) Need Help??

InfiniteLoop has asked for the wisdom of the Perl Monks concerning the following question:

Greetings,
 I'm going back to the roots and studying data structures. I came across an C implementation of hash table, that used a simple way to generate hash for a given key.

 I would like to know what kind of hash function perl uses ? I did a brief search in perl docs, but couldn't find the answer. Any help is appreciated.

Replies are listed 'Best First'.
Re: associative array - hash function
by kschwab (Vicar) on Apr 15, 2008 at 03:20 UTC
Re: associative array - hash function
by ysth (Canon) on Apr 15, 2008 at 04:36 UTC
    From hv.h:
    /* hash a key */ /* FYI: This is the "One-at-a-Time" algorithm by Bob Jenkins * from requirements by Colin Plumb. * (http://burtleburtle.net/bob/hash/doobs.html) */ /* The use of a temporary pointer and the casting games * is needed to serve the dual purposes of * (a) the hashed data being interpreted as "unsigned char" (new since + 5.8, * a "char" can be either signed or unsigned, depending on the com +piler) * (b) catering for old code that uses a "char" * * The "hash seed" feature was added in Perl 5.8.1 to perturb the resu +lts * to avoid "algorithmic complexity attacks". * * If USE_HASH_SEED is defined, hash randomisation is done by default * If USE_HASH_SEED_EXPLICIT is defined, hash randomisation is done * only if the environment variable PERL_HASH_SEED is set. * For maximal control, one can define PERL_HASH_SEED. * (see also perl.c:perl_parse()). */ #ifndef PERL_HASH_SEED # if defined(USE_HASH_SEED) || defined(USE_HASH_SEED_EXPLICIT) # define PERL_HASH_SEED PL_hash_seed # else # define PERL_HASH_SEED 0 # endif #endif #define PERL_HASH(hash,str,len) \ STMT_START { \ register const char * const s_PeRlHaSh_tmp = str; \ register const unsigned char *s_PeRlHaSh = (const unsigned char *) +s_PeRlHaSh_tmp; \ register I32 i_PeRlHaSh = len; \ register U32 hash_PeRlHaSh = PERL_HASH_SEED; \ while (i_PeRlHaSh--) { \ hash_PeRlHaSh += *s_PeRlHaSh++; \ hash_PeRlHaSh += (hash_PeRlHaSh << 10); \ hash_PeRlHaSh ^= (hash_PeRlHaSh >> 6); \ } \ hash_PeRlHaSh += (hash_PeRlHaSh << 3); \ hash_PeRlHaSh ^= (hash_PeRlHaSh >> 11); \ (hash) = (hash_PeRlHaSh + (hash_PeRlHaSh << 15)); \ } STMT_END

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://680418]
Approved by GrandFather
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (3)
As of 2020-06-04 22:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Do you really want to know if there is extraterrestrial life?



    Results (35 votes). Check out past polls.

    Notices?