Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??

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

In reply to Re: hash collision DOS (patch) by tye
in thread hash collision DOS by kschwab

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others making s'mores by the fire in the courtyard of the Monastery: (3)
    As of 2014-07-12 21:36 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      When choosing user names for websites, I prefer to use:








      Results (241 votes), past polls