John M. Dlugosz has asked for the wisdom of the Perl Monks concerning the following question:

Is anybody familiar with the code to cite what hash algorithm perl uses to generate the look-up key from a string?

Replies are listed 'Best First'.
Re: How does perl implement Perl's hash?
by Bird (Pilgrim) on Aug 12, 2002 at 22:18 UTC
    I can't say it means much to me, but you might want to try looking through "hv.h" in the CORE directory of your perl distribution. This, as far as I know, is where the "hash value" variable type is defined. Also, "av.h" and "sv.h" will probably be necessary reading to understand what hashes are built from. Wish I could be more help, but most of that code is far beyond me.

    -Bird

    ...Just took a closer look at your question and the code I was pointing you to. Looks like the PERL_HASH macro (if my C terminology is correct) in "hv.h" is the implementation of the algorithm you're looking for. Hope this helps (Also hope I'm right. If not, sorry!).

    Update: Turns out I was right, according to saouq's perl 5 porters link below. (for anyone who was doubting me, myself included ;)

[reply]
Re: How does perl implement Perl's hash?
by sauoq (Abbot) on Aug 13, 2002 at 05:25 UTC
    I found this URL by Googling. It isn't authoritative but I think it is correct. The hash function did change in 5.8 to provide better worst-case behavior. I don't know the details but they've gotta be in the source somewhere. ;-)

    Update: You might also find this one useful. 

    -sauoq
"My two cents aren't worth a dime.";
[reply]
      Interestingly, the two links give different functions. I suppose the meaning of "current" in the Perl Porter's summary refers to the 5.8 version. If that's the new one, it looks much simpler.

      It also mentions 8 buckets. Exactly 8? I thought it used a dynamic number.

[reply]
Re: How does perl implement Perl's hash?
by Cybercosis (Monk) on Aug 13, 2002 at 08:10 UTC
    *grin* As much as I hate to toot my own horn (right...), it looks like the new hashing algorithm is the same one I chose for perllib's hashes.

    Speaking of, that project isn't dead, it's just limping.

    ~Cybercosis

    nemo accipere quod non merere

[reply]
Re: How does perl implement Perl's hash?
by jmcnamara (Monsignor) on Aug 13, 2002 at 16:28 UTC

    This is defined in hv.v of the perl5.005_03 source. It looks like a variation on Daniel J. Bernstein's comp.lang.c "Times 33 with addition" hash function: 
    #define PERL_HASH(hash,str,len) \
     STMT_START    { \
    register char *s_PeRlHaSh = str; \
    register I32 i_PeRlHaSh = len; \
    register U32 hash_PeRlHaSh = 0; \
    while (i_PeRlHaSh--) \
        hash_PeRlHaSh = hash_PeRlHaSh * 33 + *s_PeRlHaSh++; \
    (hash) = hash_PeRlHaSh; \
    } STMT_END

    [download]

    This is defined in hv.v of the perl-5.7.2 source. The article mentioned in the comment is here. 

    /* FYI: This is the "One-at-a-Time" algorithm by Bob Jenkins */
/* from requirements by Colin Plumb. */
/* (http://burtleburtle.net/bob/hash/doobs.html) */
#define PERL_HASH(hash,str,len) \
     STMT_START    { \
    register const char *s_PeRlHaSh = str; \
    register I32 i_PeRlHaSh = len; \
    register U32 hash_PeRlHaSh = 0; \
    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

    [download]

    For anyone who is interested, these hashing functions are also implemented in Ralf Engershall's Str library.

    --
    John.

[reply]
[d/l]
[select]
      Thanks for the clear answers, jmcnamara.

      So where is the stuff that sauoq referred to?

      FWIW, the one I decided on for my project is similar, but uses a prime close to the golden ratio.

      I don't see how Jenkins' hash can be any faster on machines that have multiplication as a fast instruction.

[reply]

Back to Seekers of Perl Wisdom