<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><blockquote type="cite" class=""><div class="">On Jan 9, 2017, at 1:37 PM, Joerg Sonnenberger <<a href="mailto:joerg@bec.de" class="">joerg@bec.de</a>> wrote:</div><div class=""><br class="">37 is a prime. Multiples of 8 that are otherwise evenly distributed will<br class="">map to different slots in the output space.<br class=""></div></blockquote><div class=""><br class=""></div><div class="">As the hash number is reduced modulo 2^p (the number of slots), if your hash function is of the form hash(k) = c * k, I understand that you want to be able to fill all te slots. One can show that we get this property if c is not a multiple of 2. So it gives a lot of choices: 1, 3, 5, 7, 9, etc. I don’t see any reason not to use c = 1 if you want to use that kind of hash function.</div><div class=""><br class=""></div><blockquote type="cite" class=""><div class="">64bit multiplications are very expensive on many 32bit platforms. It is<br class="">certainly an order of magnitude slower than the existing hash.<br class=""></div></blockquote><div class=""><div class=""><br class=""></div></div><div class="">There is also a 32-bit version of the Knuth hash:</div><div class=""><br class=""></div><div class="">std::uint32_t hash(std::uint32_t val, int p) {</div><div class=""> const std::uint32_t knuth = 2654435769;</div><div class=""> const std::uint32_t y = val;<br class=""> </div><div class=""> return (y * knuth) >> (32 - p);</div><div class="">}</div><div class=""><br class=""></div><div class="">Those numbers come from the following fact. Let alpha = (-1 + sqrt(5)) / 2 which is about 0.618034. Multiply this number by 2^32 (or 2^64 for 64 bit hash), and round this number to the nearest integer. You’ll get 2 654 435 769. alpha has been chosen so that it is an irrational number in between 0 and 1 and that it is very difficult to approach it by rational numbers. One can show that all irrational numbers being a root of a degree 2 polynom with integer coefficients with leading coefficient being 1 have this property (X^2 + X - 1 = 0 for alpha).</div><div class=""><br class=""></div><div class="">I wrote my own hash table using open addressing and quadratic probing. I have tried to insert n = 2^26 keys given as follow: generate a random number in between 0 and 2^(64-3) and multiply it by 8. Then search all those keys in the order they were inserted. Here are the timings I get:</div><div class="">- hash(x) = x : insertion 7.42s, searching 4.09s</div><div class="">- hash(x) = 37 * x : insertion 7.49s, searching 5.50s</div><div class="">- Knuth hashing: insertion 6.04, searching 2.54s</div><div class=""><br class=""></div><div class="">So using Knuth hashing is really worth it if the keys happen to be in the form 2^k * u + v. And multiply by 37 is not a good idea here. And I am still very puzzled and don’t really understand the situations where it could be useful.</div><div class=""><br class=""></div><div class="">
<div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">François Fayard<br class=""></div></div>
</div>
<br class=""><br class=""></body></html>