Bug#206416: dpkg package hash table insufficient
Daniel Silverstone <email@example.com> 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