Bug#206416: dpkg package hash table insufficient
On Wed, Aug 20, 2003 at 11:35:52PM +0200, Falk Hueffner wrote:
> 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".
<snip>
> See also http://burtleburtle.net/bob/hash/doobs.html
I quote from that document:
FNV Hash
I need to fill this in. Search the web for FNV hash. It's faster than my
hash on Intel (because Intel has fast multiplication), and preliminary
tests suggested it has decent distributions.
B.
--
Rob Kendrick, Pepperfish Limited http://www.pepperfish.net/
PGP signed or encrypted mail welcome Key ID: 3651D17A
Reply to: