Subject: Re: New hash algorithm - FNV - for use in the kernel
To: John F. Woods <>
From: Reinoud Zandijk <>
List: tech-kern
Date: 11/28/2001 02:48:29
On Tue, Nov 27, 2001 at 06:18:43PM -0500, John F. Woods wrote:
> > 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.

Yet another Hash algoritm as found in `Brinch on Pascal Compilers' (ISBN 
0-13-083098-4) that just adds the values of the chars :

function Key(Text : String; Length : integer) : integer;
const W = 32641; N=MaxKey;
var Sum, i : integer;
  Sum := 0; i := 0;
  while (i<=Length) do
      Sum := (Sum + ord(Text[i]) mod W;
      i := i + 1;
  Key := Sum mod N+1;

Now this looks a bit expensive due to the `mod' but as we all should know a
simple `if' does the trick ... its an increasing line of numbers and when
we cross the value `W' we just slash off `W' ... i think it was even just
done to keep `W' in a 16 bits really.... and this `W' is 2^15-127 just for
this reason too; we can easily drop this .... unless we are really doing
wierd things...

I've tried this extremely simple hash function and its pretty good really
... i got significant sped ups in my ModulaII compiler project for the
average lookup time was just 1.3/1.7 comparisations per search (this way
way ago ...  dont ask :P)

just my $0.02,