Perlはどのようなハッシュ関数/アルゴリズムを使用していますか？

Question

文字列をインデックスにマッピングするためにPerlが使用するハッシュ関数/アルゴリズムについて、あなたは誰かに光をあててもらえますか？関連する読書は？ hv.hで定義された

Answer 1

PERL_HASH_INTERNAL_ は、以下のコピー：

/* 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 compiler) 
* (b) catering for old code that uses a "char" 
* 
* The "hash seed" feature was added in Perl 5.8.1 to perturb the results 
* 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()). 
*/ 

#define PERL_HASH_INTERNAL_(hash,str,len,internal) \ 
    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 = (internal ? PL_rehash_seed : 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