Subject: Re: New hash algorithm - FNV - for use in the kernel
To: Tom Spindler <>
From: John F. Woods <>
List: tech-kern
Date: 11/27/2001 18:18:43
> Perl uses the following for hashing strings; while it contains a
> multiply (* 33), it could be converted into a shift and an add pretty
> easily.

The FNV multiplications can also be converted into shifts and adds relatively
easily; i.e. the constants in question are relatively sparse in 1 bits
(0x1000193 and 0x100000001B3, if I remember correctly); 6 shifts in the 32-bit
case, with two of the shifts being byte-shifts.  Granted, it's not as fast as
a single shift and add, but multiply-free hardware could still probably do
it with custom assembly code much faster than a general-purpose multiply