<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=""><div class=""><br class=""></div><div class=""></div><blockquote type="cite" class=""><div class="">On Jan 10, 2017, at 2:31 AM, Chris Lattner <<a href="mailto:sabre@nondot.org" class="">sabre@nondot.org</a>> wrote:</div><div class=""><br class="">As others have pointed out, 37 does have some nice properties (by being prime), but we’ve also had it from the very early days. I wouldn’t say that it has been extremely well considered at all.<br class=""><br class="">-Chris<br class=""></div></blockquote><div class=""><br class=""></div>Thanks for your reply. But I am not sure to understand the last sentence. Does it mean that this hash function has been criticized before? Do you also think that it can be improved?<div class=""><br class=""></div><div class="">I am sorry to insist on that, but I don’t see any advantage of using hash(k) = c * k with c being a primer number. What is important is choosing c such that gcd(c, m) = 1 for any size m of the hash table. This is the case for c = 1. As a consequence, I don’t see any benefit in using c = 37 over c = 1. Moreover, all those hash functions are badly considered for a reason : they behave very poorly when the keys are of the form d * k0 + k1.</div><div class=""><br class=""></div><div class="">I really think that this hash function could be improved. But to know if it's worth it, I would like to know if having a better hash for integer types would benefit LLVM.</div><div class=""><div class=""><div class=""><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=""></div></div></div></body></html>