Author jdemeyer
Recipients eric.smith, jdemeyer, mark.dickinson, rhettinger, sir-sigurd, tim.peters
Date 2018-09-24.09:45:54
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1537782354.87.0.956365154283.issue34751@psf.upfronthosting.co.za>
In-reply-to
Content
> Has anyone figured out the real source of the degeneration when mixing in negative integers?

The underlying reason for the collisions is the following mathematical relation:

x ^ -x = -2 << i

where i is the index of the smallest set bit of x. In particular, x ^ -x = -2 for odd x.

Now consider two consecutive hash iterations:

y = (x ^ a) * m1
z = (y ^ b) * m2

and suppose that x ^ a is odd. Now if we replace a by a ^ -2, then x ^ a will be replaced by -(x ^ a) and y will be replaced by -y. If we also replace b by b ^ -2, then y ^ b will be replaced by y ^ b. In other words, we have a collision.

This kind of bad interaction between ^ and * only happens with the FNV-style hashing. The Bernstein hash using + instead of ^ does not suffer from this problem. That makes it a better choice in my opinion.
History
Date User Action Args
2018-09-24 09:45:54jdemeyersetrecipients: + jdemeyer, tim.peters, rhettinger, mark.dickinson, eric.smith, sir-sigurd
2018-09-24 09:45:54jdemeyersetmessageid: <1537782354.87.0.956365154283.issue34751@psf.upfronthosting.co.za>
2018-09-24 09:45:54jdemeyerlinkissue34751 messages
2018-09-24 09:45:54jdemeyercreate