3 ms·
Kenneth A. Ross mentions it in passing in his 2006 IBM research report (a great paper btw): "We can interpret a 32-bit hash value v as a binary fraction, i.e.,
by eternalban 5y ago
Kenneth A. Ross mentions it in passing in his 2006 IBM research report (a great paper btw):
"We can interpret a 32-bit hash value v as a binary fraction, i.e., the representation of a number between zero and one whose digits after the (binary) decimal point are given by v. Given a hash table size s, we can obtain a slot number by multiplying s and v and shifting right 32-bits. This way, arbitrary table sizes are possible without using expensive division or modulus operations. Computing s∗v can be performed with one 32-bit multiplication (generating a 64- bit result). If s is a 16-bit number, as might be expected for a small hash table, then two 16-bit multiplications, a shift, and a 32-bit addition suffice."
Kenneth A. Ross, Efficient Hash Probes on Modern Processors, IBM Research Report RC24100 (W0611-039) November 8, 2006
https://dominoweb.draco.res.ibm.com/reports/rc24100.pdf https://dominoweb.draco.res.ibm.com/reports/rc24100.pdf