[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

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


Reply to: