Author jdemeyer
Recipients jdemeyer
Date 2018-09-20.13:27:27
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1537450047.43.0.956365154283.issue34751@psf.upfronthosting.co.za>
In-reply-to
Content
It's not hard to come up with a hash collision for tuples:

>>> hash( (1,0,0) )
2528505496374819208
>>> hash( (1,-2,-2) )
2528505496374819208

The underlying reason is that the hashing code mixes ^ and *. This can create collisions because, for odd x, we have x ^ (-2) == -x and this minus operation commutes with multiplication.

This can be fixed by replacing ^ with +. On top of that, the hashing code for tuples looks needlessly complicated. A simple Bernstein hash suffices.
History
Date User Action Args
2018-09-20 13:27:27jdemeyersetrecipients: + jdemeyer
2018-09-20 13:27:27jdemeyersetmessageid: <1537450047.43.0.956365154283.issue34751@psf.upfronthosting.co.za>
2018-09-20 13:27:27jdemeyerlinkissue34751 messages
2018-09-20 13:27:27jdemeyercreate