Subject: Re: New hash algorithm - FNV - for use in the kernel
To: Lennart Augustsson <>
From: Luke Mewburn <>
List: tech-kern
Date: 11/27/2001 22:02:01
On Tue, Nov 27, 2001 at 11:10:56AM +0100, Lennart Augustsson wrote:
> > There is a potential issue however; FNV uses multiply (*) and xor (^),
> > whereas a lot of the existing hashes on strings and buffers just use
> > addition (+). Whilst FNV has much better distribution than the latter,
> > it will be slower on platforms without hardware multiply. The question
> > is as to whether the reduction in hash collisions (and the subsequent
> > following of collision list chains) is effective on these systems.
> There are other good string hashing algorithms that do not use multiply.

Please elaborate or provide pointers to information on these!

It's quite obvious to me that the existing mechanism used by
nfs_hash() (and possibly others) is very bad.