On 21.03.2012 15:17, Daniel Shahaf wrote: > Philip Martin wrote on Wed, Mar 21, 2012 at 13:00:01 +0000: >> Philip Martin <philip.mar...@wandisco.com> writes: >> >>> So if I have >>> >>> 0, 1 ... X, Y ... N-1 >>> >>> where X and Y collide I would expect changing the seed to give: >>> >>> K, K+1 ... X, Y ... N-1, 0 ... K-1 >>> >>> Is that going to remove the collision? >> Is it something to do with the bins?. If X and Y were originally in the >> same bin the seed change might cause one to move to the next bin so X >> and Y no longer collide but Y and Y+1 collide? > The issue discussed on IRC has to do with the hash buckets, yes --- with > someone intentionally causing most of the hash elements to be in a small > number of buckets, rather than the more even distribution of the > 'average case' analysis.
Yup. And the randomization happens before the hashing, so if the hash function is good enough, a small change of the key will cause a considerably larger and different change in the result of the hash function. APR's default hash function is "good enough" in this respect; it's not cryptographically secure, but that's not what it's intended for. -- Brane
