Message 325870 - Python tracker

➜

This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

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.

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:27	jdemeyer	set	recipients: + jdemeyer
2018-09-20 13:27:27	jdemeyer	set	messageid: <1537450047.43.0.956365154283.issue34751@psf.upfronthosting.co.za>
2018-09-20 13:27:27	jdemeyer	link	issue34751 messages
2018-09-20 13:27:27	jdemeyer	create