Daniel J Bernstein's "Multiply 33 and add" simple hash is surprisingly hard to find the original reference to. Googling provides descriptions in language implementations such as PHP internals book and Python PEP 456, but no reference. Performance of the most common non-cryptographic hash functions by Estébanez et al. doesn't cite Bernstein either. Is it one of those "folklore" algorithms that has been in circulation for a long time? http://www.cse.yorku.ca/~oz/hash.html says comp.lang.c from "many years ago". The origin of the magic numbers 33 and 5381 isn't explained either; see this answer by Mark Johnson on SO.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
The original post to comp.lang.c may be forgotten to history, or it may still be available on a Usenet archive somewhere.
But there have been some explanations from Bernstein. In this thread, he said:
we're talking about string hash functions, and typical strings (a) are concentrated on a few character values, not spread evenly over the entire character set; (b) do not all have the same high byte; (c) do not all have the same length.
And:
The profiling statistics I've saved from various compressors form a much more realistic sample. They show 33 as slightly better than random hashing on typical files, 37 as slightly worse. I've never tried 261 or 31, but I'll bet 261 does worse than 33 on text files.
And:
Again, practically any good multiplier works. I think you're worrying about the fact that 31c + d doesn't cover any reasonable range of hash values if c and d are between 0 and 255. That's why, when I discovered the 33 hash function and started using it in my compressors, I started with a hash value of 5381. I think you'll find that this does just as well as a 261 multiplier.
Looking at his contributions to the thread, the underlying point seems to be that "simple string hashing", as you would find in a compiler, or linker/loader, or text compressor, is its own thing, and can only be evaluated by testing.
Strings generated by humans do not have a "flat" frequency distribution. Over half of all English text is about 100 words none of which contain the letters "j", "q", "x", or "z". And programmers like using identifiers like x1, x2, y1, y2, etc.
That is the set of strings that he needed good performance for. And that's the sort of thing where only building a corpus and testing will do.
-
$\begingroup$ I see. I am designing a hash function for byte pairs for a compressor that will run binary files and text. In (English) text almost all bytes are printable ASCII characters, and in ELF binaries there are large runs of NUL bytes for padding, making them both nicely compressible. $\endgroup$– qwrCommented Aug 26 at 16:09