Subject: Re: New hash algorithm - FNV - for use in the kernel
To: None <firstname.lastname@example.org>
From: der Mouse <mouse@Rodents.Montreal.QC.CA>
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@example.com
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B