[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: Hash Table Collisions (n.runs-SA-2011.004)
- From: Gé Weijers <ge@...>
- Date: Fri, 6 Jan 2012 18:14:47 -0800
On Friday, January 6, 2012, Jay Carlson wrote:
I wonder if combining a secret seed with the contents of the
accumulated hash to choose how far to jump ahead each time is
sufficiently annoying. Instead of jumping ahead stepsize, jump ahead
stepsize+(h%stepsize) and mix a few bytes in. We don't need to always
use the same number of samples for a given length either, right?
If the string is long enough (say >= 100 chars) you have a 50% chance of not hitting any 32 indices if you randomly choose 4 positions. So it's easy enough to create collisions by trying until the victim grinds to a halt.
Using a combinations of a secret seed (or better: a universal hashing scheme, which would be a small # of secret seeds) and using on-demand-only hashing for long strings is the best approach I've heard so far.
Gé
--
Gé
- References:
- Re: Hash Table Collisions (n.runs-SA-2011.004), Vladimir Protasov
- Re: Hash Table Collisions (n.runs-SA-2011.004), Leo Razoumov
- Re: Hash Table Collisions (n.runs-SA-2011.004), Vladimir Protasov
- Re: Hash Table Collisions (n.runs-SA-2011.004), Miles Bader
- Re: Hash Table Collisions (n.runs-SA-2011.004), Ashwin Hirschi
- Re: Hash Table Collisions (n.runs-SA-2011.004), Miles Bader
- Re: Hash Table Collisions (n.runs-SA-2011.004), David Kolf
- Re: Hash Table Collisions (n.runs-SA-2011.004), Miles Bader
- Re: Hash Table Collisions (n.runs-SA-2011.004), Alexander Gladysh
- Re: Hash Table Collisions (n.runs-SA-2011.004), Roberto Ierusalimschy
- Re: Hash Table Collisions (n.runs-SA-2011.004), Roberto Ierusalimschy
- Re: Hash Table Collisions (n.runs-SA-2011.004), Jay Carlson