Author jdemeyer
Recipients eric.smith, jdemeyer, mark.dickinson, rhettinger, sir-sigurd, tim.peters
Date 2018-09-26.09:06:52
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1537952812.84.0.545547206417.issue34751@psf.upfronthosting.co.za>
In-reply-to
Content
> There are _two_ hash functions at play in that collision:  the tuple hash function, and the integer hash function.  Regardless of whether the _tuple_ hash function does [anything involving just `t`], that only directly affects the result of the _int_ hash function

...which is what you want here. The collision hash((3,3)) == hash((-3,-3)) is due a specific structure in the input to the FNV algorithm. The operation t ^= t << 7 that you suggested (and which I approve, except for the shift amount) is meant precisely to destroy that structure.

> If you feel you just have to mess with low-order bits, do it instead on the _tuple_ hash intermediate results, not on its inputs. It's x you care about directly, not t.

That would not be a good solution, because that destroys the structure of the has algorithm. For Bernstein for example, each loop iteration should do something like

    x = (x * m) + t

for *some* value t depending on the input. If you mess with x, then it really becomes a different hash algorithm. That is far more dangerous than simply applying a permutation on t.

> Mucking with t to avoid the nested-tuple catastrophes is worth it, but I prefer to do that with as little damage to t's desirable properties as reasonably possible.

Which "desirable properties" of t does the operation t ^= (t << 1) damage?
History
Date User Action Args
2018-09-26 09:06:52jdemeyersetrecipients: + jdemeyer, tim.peters, rhettinger, mark.dickinson, eric.smith, sir-sigurd
2018-09-26 09:06:52jdemeyersetmessageid: <1537952812.84.0.545547206417.issue34751@psf.upfronthosting.co.za>
2018-09-26 09:06:52jdemeyerlinkissue34751 messages
2018-09-26 09:06:52jdemeyercreate