Subject: Re: New hash algorithm - FNV - for use in the kernel
To: Lennart Augustsson <>
From: Bill Sommerfeld <>
List: tech-kern
Date: 11/27/2001 21:33:38
> Here's the one I usually use when I need a string hash.  The basic
> version only gives an 8 bit hash, this has been tweaked for 16.

[table-lookup-based hash function deleted].

Thor Simon has mentioned some perhaps unintuitive results with
table-lookup based CRC implementations on modern hardware; the memory
lookups are more painful than you might think when hashing is
infrequent enough that the table isn't resident in L1 cache.

I didn't conduct the experiment, but evidently he found that an
algorithm which did two lookups per byte in a 16-entry table was much
faster than one which did a single lookup per byte in a 256-entry

					- Bill