Subject: Re: New hash algorithm - FNV - for use in the kernel
To: Lennart Augustsson <email@example.com>
From: Bill Sommerfeld <firstname.lastname@example.org>
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