THE DJB2 HASH h = h × 33 + c, and nobody knows why 33
Dan Bernstein’s djb2: start at 5381, and for each byte do h = h·33 + c — written as (h«5)+h+c so it is two adds and a shift. Five lines, famously fast, and the constants 5381 and 33 are folklore that just work. Here “hi” hashes to 5863446, and the shift form equals the multiply form exactly.
THE TECHNIQUE h = ((h « 5) + h) + c
The demo shows (h«5)+h is identical to h·33, then hashes “hi”: live demo
HISTORY & CREDIT D. J. Bernstein · comp.lang.c
“33 was chosen for a proven reason.” — Bernstein himself said the magic of 33 (vs any other odd constant) was never adequately explained; it just tests well. cited
the seed · 5381, a prime, folklore. the step · (h«5)+h+c = 33h+c — shift-add, no multiply needed. djb · Daniel J. Bernstein, posted to comp.lang.c (late 1980s/1991).
The most-copied string hash in C. arithmetic
RECOMMEND FOR I-13 shift == multiply, on the compiler
On i-13, (5381«5)+5381 equals 5381·33, and “hi” hashes to 5863446 (32-bit stays exact):
$ i13 run hs_djb2.i13
RUN OK · 78 step(s) · peak stack 7
h_hi = 5863446
shift_form = 177677
mul_form = 177677
same = 1 -- (h<<5)+h == h*33
Recommend as a NULL — an identity (B39) + arithmetic (B40). That (h«5)+h == 33h is a theorem, not a same-function difference; the shift form and the multiply form are the identical function, cheaper on one path (B40). NULL — folklore that works.