From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of [EMAIL PROTECTED] Sent: 27 September 2006 16:43 To: [email protected] Subject: keys(%hash) rounding vs. hash sizing
> This question is primarily for Gisle Aas and Martin Thurn, the Lady and Lord Wizards of All Things Hash-ly, but > all are welcome to contribute wisdom... > > In an article I was linked to by Martin (http://www.perl.com/lpt/a/679) the author, Abhjit Menon-Sen, > recommends that hashes be given bucket counts "Using a prime number that is not too close to a power of > two..." Well, that's all well and fine but, according to perldoc, the keys(%hash) function, when used to > preallocate buckets, rounds its assigned value up to the nearest power of two. That is: > > keys( %baz) = 191; > > will allocate 256 buckets (the next nearest 2n) to %baz. So how do I follow Menon-Sen's recommendation when > the behavior of keys() blatantly contradicts it? Is there nothing to be done? That is the documented behaviour, see 'perldoc -f keys'. The page you refer to above has a link to http://burtleburtle.net/bob/hash/doobs.html which states "The best hash table sizes are powers of 2.", which may explain the reason for the documented behaviour. Also, from http://en.wikipedia.org/wiki/Hash_table, "Some older hashes are even worse, requiring table sizes to be a prime number rather than a power of two, again computing the bucket index as the hash value modulo the table size. In general, such a requirement is a sign of a fundamentally weak function; using a prime table size is a poor substitute for using a stronger function." HTH -- Brian Raven ================================= Atos Euronext Market Solutions Disclaimer ================================= The information contained in this e-mail is confidential and solely for the intended addressee(s). Unauthorised reproduction, disclosure, modification, and/or distribution of this email may be unlawful. If you have received this email in error, please notify the sender immediately and delete it from your system. The views expressed in this message do not necessarily reflect those of Atos Euronext Market Solutions. L'information contenue dans cet e-mail est confidentielle et uniquement destinee a la (aux) personnes a laquelle (auxquelle(s)) elle est adressee. Toute copie, publication ou diffusion de cet email est interdite. Si cet e-mail vous parvient par erreur, nous vous prions de bien vouloir prevenir l'expediteur immediatement et d'effacer le e-mail et annexes jointes de votre systeme. Le contenu de ce message electronique ne represente pas necessairement la position ou le point de vue d'Atos Euronext Market Solutions. _______________________________________________ ActivePerl mailing list [email protected] To unsubscribe: http://listserv.ActiveState.com/mailman/mysubs
