Ein B-Baum ist kein Hashalgorithmus, sondern eine Datenstruktur, die ähnlich wie ein Hash zur Implementation assoziativer Arrays verwendet werden kann.
Perl verwendet zur Implementation seiner Hashes meines Wissens tatsächlich gewöhnliche Hashtables mit verlinkten Listen als Datenstruktur der Buckets. Ein kurzer Blick in
hv.h und
hv.c aus der Quellcodedistribution von Perl 5.12.1 bestätigt diese Hypothese.
Die verwendete Hashfunktion ist eine einfache Bitpermutation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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
Der Wert
PERL_HASH_SEED wird beim Start des Interpreters in der Regel zufällig gewählt und dient dazu, die Hashfunktion zu randomisieren um Komplexitätsattacken auf Perls Hashes zu erschweren.
When C++ is your hammer, every problem looks like your thumb.