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

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: