Re: [Chicken-hackers] On Hash Collisions (28C3)

[John Cowan]

Peter Bex scripsit:

> Agreed.  Changing datastructures is not an option.

Why not?  It's a matter of replacing a datastructure whose worst-case
cost is quadratic with one whose worst-case cost is linear.  Do we even
know what the break-even point is between a-lists with their higher
algorithmic complexity vs. hash tables with their higher constant
factors?  I tried writing a little benchmark to determine this, but so
far without success.

> The patch ensures no two hash tables use the same offset, so even
> if the hash value of a given table were to leak out (which the user
> still should take every precaution to avoid!), it won't compromise the
> randomization of other hash tables.

What you are doing is imposing an additional cost on *all* users of hash
tables so as to make them more resistant to malicious attack.  The vast
majority of hash tables do not need to deal with malicious data.

> > Once I know, I'll estimate the cost to fix it to save my brain
> > from remebering that I'm not supposed to use hash tables where
> > appropriate because they could degenerate into an issue.
>
> Indeed.  If other languages have fixed it transparently, so can we.

We aren't Perl or Python, where hash tables are deeply embedded in
the implementation.  Using a hash table in Scheme should always be an
informed choice, not a default one.  Right now the information is lacking.

-- 
John Cowan   address@hidden    http://ccil.org/~cowan
I am he that buries his friends alive and drowns them and draws them
alive again from the water. I came from the end of a bag, but no bag
went over me.  I am the friend of bears and the guest of eagles. I am
Ringwinner and Luckwearer; and I am Barrel-rider.  --Bilbo to Smaug