In Dan Bernstein's famous Djb2 hash function I see it's preferred to use the bitwise operator, but why use it over a simple multiplication ? Is it faster ?
(hash << 5) + hash = hash * 33
// Hashes word to a number
unsigned int hash(const char *word)
{
// Djb2 hash function by Dan Bernstein
unsigned long hash = 5381;
int c;
while ((c = *word++))
{
hash = ((hash << 5) + hash) + tolower(c); /* hash * 33 + c */
}
return hash % N;
}
Why use bitwise operator when we can just multiply by 33?
but why use it over a simple multiplication ? Is it faster ?
BITD, compilers were not as smart and so it was often faster. @that other guy
Today, code for clarity unless your situation demonstrates otherwise (e.g. using a weak compiler). A good compiler will emit efficient code either way.
hash = ((hash << 5) + hash) + tolower(c);
// or
hash = hash * 33u + tolower(c);
As this is a hash, either is just as clear.
Pedantic
If c < 0, islower() is not so well defined.
Alternative, with some casts to quiet pedantic warnings and perhaps a tad faster unsigned code.
unsigned hash(const char *word) {
const unsigned char *uword = (const unsigned char *) word;
unsigned long hash = 5381u;
int c;
while ((c = *uword++))
hash = hash*33u + (unsigned)tolower(c);
}
return (unsigned) (hash % N);
}