Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery

Re: hash collision DOS (patch)

by tye (Sage)
on Jun 02, 2003 at 04:53 UTC ( #262302=note: print w/ replies, xml ) Need Help??

in reply to hash collision DOS

Interesting timing. Just a couple of weeks back p5p accepted my resubmission of a patch I originally submitted years ago that never went anywhere.

So in Perl 5.8.0 and earlier (and perhaps a version of two after 5.8.0), it isn't hard at all to come up with a space of keys that will all get stuck into the same bucket when you put them in a hash. In fact, you can use 1/8th of all possible strings and end up with a hash that contains 8 buckets, 7 of which are empty, and the 8th of which contains as large of a linear linked list as you want.

In versions of Perl that have my patch applied, the more keys you add, the harder it is to find keys that fall into the same bucket. If you want 1,000 keys to fall into the same bucket, then you have to be very picky, only using 0.1% of possible strings. So it is like picking out 1,000 keys out of 1,000,000 keys. If you want 1,000,000 keys in the same bucket, then you can only use 1/1,000,000 of strings so it is like picking out your 1M keys from a space of 1,000,000,000,000 strings.

It looks like the slashdot article isn't even aware of this problem, however. They actually go to the work of finding keys that will get thrown into the same bucket no matter how many buckets get allocated. So they could greatly simplify their work.

                - tye

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://262302]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (7)
As of 2016-06-30 08:31 GMT
Find Nodes?
    Voting Booth?
    My preferred method of making French fries (chips) is in a ...

    Results (389 votes). Check out past polls.