Subject: Re: New hash algorithm - FNV - for use in the kernel
To: None <>
From: der Mouse <mouse@Rodents.Montreal.QC.CA>
List: tech-kern
Date: 11/27/2001 06:54:26
> There is a potential issue however; FNV uses multiply (*) and xor
> (^), whereas a lot of the existing hashes on strings and buffers just
> use addition (+).

Given how disastrously bad the current default hash is (just add all
the bytes, yeek), maybe some other hash algorithms should be tried
before going to one as expensive as a full-word multiply per byte?
Even if it is by a constant, it's still comparatively expensive.

One that I've often found worth trying is a simple CRC - cheap to
compute on approximately all platforms and usually does a decent job of
spreading the hash values around.  If keeping a full CRC table around
is too much, then often doing one bit's worth of CRC but XORing in a
whole byte of data - effectively XORing the data bytes together shifted
by one bit each, and doing a CRC of the result - is a workable

/~\ The ASCII				der Mouse
\ / Ribbon Campaign
 X  Against HTML
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B