This is more about C and hash tables than perl. (I have not looked at the source, but the name "hash", would strongly imply that they are implemented using a hash table in C.)

Maps from the C++ STL -- which are like perl hashes, and are very high performance --- are done using red black trees. Red black trees are based on Bayer trees with a limit of 2 keys per node and have a big O of log(n) for lookups. Fast databases commonly use Bayer trees for hash like operations. I've written a hash table in C for large data sets that performs comparably to the STL's "map" using Bayer trees with 4+ keys per node. The idea there is that you have a hash table of trees, and this works very well -- I am certainly not the only person to do it.

So unless anyone knows more specifically exactly what kind of data structure is used in the perl source, keep in mind those three possibilities:

In reply to Re: Perl's hash table implementation by halfcountplus
in thread Perl's hash table implementation by jc

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!
  • 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, details, 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, summary, 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.