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.martin_at_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
Received on 2012-03-21 17:13:16 CET