Bug#206416: dpkg package hash table insufficient
Scott James Remnant <scott@netsplit.com> writes:
> Falk Hueffner <falk.hueffner@student.uni-tuebingen.de> wrote:
>
> > Daniel Silverstone <dsilvers@digital-scurf.org> writes:
> >
> > > *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
>
> All well and good, except the replacement FMV code is at least 20%
> faster.
I don't know FMV, but if it is a reasonable hash, it shouldn't depend
on prime table sizes. Maybe you could just also benchmark it with a
power-of-two table size?
--
Falk
Reply to: