Bug#206416: dpkg package hash table insufficient
Daniel Silverstone <dsilvers@digital-scurf.org> writes:
> On Wed, Aug 20, 2003 at 09:09:50PM +0200, Falk Hueffner wrote:
> > There is no reason to make the number of buckets a prime number unless
> > either your hash function really sucks or you use double hashing. In
> > fact, it is a bad idea to do so, since modulo powers of two is a lot
> > faster than general modulo.
>
> Let's have a look...
>
> *hauls out...
> (a) Practical Algorithms for Programmers, Binstock & Rex
> (b) The Art of Computer Programming Vol 3. "Sorting and Searching", Knuth
> (c) Introduction to algorithms, Cormen, Leiserson & Rivest
Those all fall into "hash functions that really suck". IMHO it should
be intuitively obvious that your hash function sucks when it is
affected by the bucket size being a power of two, since that means the
input value affects upper bits more than lower bits. See also
http://burtleburtle.net/bob/hash/doobs.html
--
Falk
Reply to: