Opened by pope at 2010-06-30 13:59
User since
2004-07-19
1776 Artikel
HausmeisterIn
![[Homepage]](/battie/theme/default/homepage.gif)
2004-07-19
1776 Artikel
HausmeisterIn
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:
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.
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:
Code (C): (dl
)
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.