<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto">Hi Luciano,<div dir="ltr"><br>On Nov 26, 2018, at 2:34 AM, Luciano Notarfrancesco <<a href="mailto:luchiano@gmail.com">luchiano@gmail.com</a>> wrote:<br><br></div><blockquote type="cite"><div dir="ltr"><div dir="ltr"><div>Perhaps it is best to change Set>>scanFor:, as I suggested in other mail. I think it might be best because: 1) adheres better to KISS principles, keeping Integer>>hash unchanged and simple; 2) it might address similar performance problems with other types of objects, not only SmallIntegers; 3) leaves the responsibility of 'mixing' the hash bits to the hashed collections where it seems to belong.</div><div><br></div><div>If we do this, then we can have simpler requirements for hash; it has to be a SmallInteger, equal objects must have equal hash, and ideally it has to be well distributed. But it doesn't need to look random, so similar objects can have similar hashes (as it is currently the case with SmallInteger, and maybe with Strings too? it might be even desirable for similar Strings to have similar hashes). Then the only required change is in Dictionary and Set scanFor:</div><div> start _ (anObject hash \\ array size) + 1.</div><div>should be changed to:</div><div> start _ (anObject hash hashMultiply \\ array size) + 1.</div><div>(or something similar, anything that 'mixes' the bits of the hash, perhaps with a primitive that does this and the modulus all at once). This would ensure that lookup for hashed collections is done in constant time and doesn't degenerate into linear searches, at a very small cost (the lookup time is increased slightly due to the extra hashMultiply).</div></div></div></blockquote><div><br></div>I find this much more compelling. I have no objection to this and it suggests an obvious extension to the hashMultiply primitive, which is to support large Integer receivers.<div><br></div><div>(p.s. _ in place of := is deprecated).<div><br><blockquote type="cite"><div dir="ltr"><div dir="ltr"><div>And there's always the alternative of PluggableSet / PluggableDictionary for the cases when a custom hash is desired.</div></div></div></blockquote><br><blockquote type="cite"><div dir="ltr"><div dir="ltr"><div><br></div><div>My other 2 cents,</div><div>Luciano<br></div><div><br></div><div> <br></div></div><br><div class="gmail_quote"><div dir="ltr">On Mon, Nov 26, 2018 at 4:14 AM Luciano Notarfrancesco <<a href="mailto:luchiano@gmail.com">luchiano@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">On Mon, Nov 26, 2018 at 4:05 AM Luciano Notarfrancesco <<a href="mailto:luchiano@gmail.com" target="_blank">luchiano@gmail.com</a>> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">1 to 254 have probability 1/254 while 0 has probability 2/254</div></blockquote><div> </div></div><div class="gmail_quote">Oops, that should be 1/256 and 2/256, sorry.</div><div class="gmail_quote">When probabilities don't sum 1, unexpected things can happen ;)<br></div></div>
</blockquote></div>
</div></blockquote><blockquote type="cite"><div dir="ltr"><span></span><br></div></blockquote></div></div></body></html>