Subject: Re: New hash algorithm - FNV - for use in the kernel
To: Luke Mewburn <email@example.com>
From: Lennart Augustsson <firstname.lastname@example.org>
Date: 11/27/2001 11:10:56
Luke Mewburn wrote:
> I recently added <sys/fnv_hash.h> (from FreeBSD), which provides an
> implementation of the Fowler / Noll / Vo (FNV) hash, as described at:
> I've done some initial investigation and testing of the effectiveness
> of this hash algorithm, and I'm getting similar improvements that
> Peter Wemm (of FreeBSD) found when he switched parts of FreeBSD over
> to using the FNV hash.
> 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.