Branko ÄŒibej wrote on Wed, Mar 21, 2012 at 17:13:07 +0100:
> 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.
APR's default hash function is linear in the last byte of the key.
(Incrementing key[klen-1] by X increments the hash by X.)
13:33:55 @stefan2 | hash = 33**0 * x[n-1] + 33**1 * x[n-2] + 33**2
| * x[n-3] + ... + 33**(n-1) * x[0] + 33**n * seed
>
> -- Brane
>
Received on 2012-03-21 17:29:45 CET