http://perldoc.perl.org/5.10.0/perlguts.htmlより引用
The hash algorithm is defined in the PERL_HASH(hash, key, klen) macro:
hash = 0; while (klen--) hash = (hash * 33) + *key++; hash = hash + (hash >> 5); /* after 5.6 */The last step was added in version 5.6 to improve distribution of lower bits in the resulting hash value.
ふむ。
値hashに対して33倍というのは、hash=(hash<<5)+vと同等なので、乗算を使わない形に出来ます。
値を決めるときにhashにhash>>5を加算するのは、計算でシフトしておいた分を加算することで、
"より混ざった値"にする意味合いがあるんだと思います。
/* 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()). */ #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
コンパイル次第で初期値としてPL_hash_seedを使って好きなシード値を決められ、式も複雑になっていた。
コメント分に含まれるURL先にhashについての検証をしているようだけど、英語が読めないので雰囲気で読んでます。
ビットシフト使いまくって値をかき混ぜている事には違いないけども、
最初にあげたやり方ではなぜいけないんだろう。
衝突しやすい値を作りやすく、衝突した時の再計算の時間を考慮したのかな?