Message326435
> 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? |
|
Date |
User |
Action |
Args |
2018-09-26 09:06:52 | jdemeyer | set | recipients:
+ jdemeyer, tim.peters, rhettinger, mark.dickinson, eric.smith, sir-sigurd |
2018-09-26 09:06:52 | jdemeyer | set | messageid: <1537952812.84.0.545547206417.issue34751@psf.upfronthosting.co.za> |
2018-09-26 09:06:52 | jdemeyer | link | issue34751 messages |
2018-09-26 09:06:52 | jdemeyer | create | |
|