Subject: Re: New hash algorithm - FNV - for use in the kernel
To: None <,>
From: Thor Lancelot Simon <>
List: tech-kern
Date: 11/27/2001 23:11:15
On Tue, Nov 27, 2001 at 09:33:38PM -0500, Bill Sommerfeld wrote:
> > 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.

You can think of the problem as "how likely is it that the data I am
running the CRC over will collide with the cache line the part of the
lookup table I need to look at is in"?  You need to know a surprising
amount about the hardware to get it right.