Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot

comment on

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

My experience is largely with Other Languages that perhaps don't have such clever internals as Perl and where the underlying data structures can make the difference between terrible and acceptable performance speeds for extremely heavily loaded hash tables.

Im guessing that you mean scenarios where you have to hand code your own hash table implementations. Im also guessing that you mean scenarios where you have to work with statically sized hash tables. In such a scenario I could see your point for sure. A hash table of small threaded binary trees sounds like a good design to me.

However, just for your edification ill outline in general how perls hashes work: first, the size of the hash table is always a power of 2, starting at 8 elements large. When the bucket chain length starts getting too long (calculated I beleive by determining the ratio of the number of keys to the number of buckets) the size of the hash array is doubled and the keys of the original are remapped into the new hash array. The hash values are not recalculated as the power of two rule implies that the remapping can occur simply by anding a different bit mask with the hash values to determine the new slot in the array. In normal circumstances the actual keys are stored only once, in a master hash, with pointers from the buckets of the actual hash buckets to the master hashes buckets (which actually contain the key string). This key sharing is important as hashes are the most common way of representing objects which will by-and-large tend to have many keys in common.


In reply to Re^6: RFC on Inline::C hack: Hash_Iterator by demerphq
in thread RFC on Inline::C hack: Hash_Iterator by tlm

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!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • 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
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            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?

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

    How do I use this? | Other CB clients
    Other Users?
    Others imbibing at the Monastery: (2)
    As of 2020-12-05 06:31 GMT
    Find Nodes?
      Voting Booth?
      How often do you use taint mode?

      Results (63 votes). Check out past polls.