Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW

Re: Perl Internals: Hashes

by ambrus (Abbot)
on Apr 14, 2004 at 21:25 UTC ( #345211=note: print w/replies, xml ) Need Help??

in reply to Perl Internals: Hashes

This is not a full answer, just some points.

As for the size of a hash, when a new hash with one element is created, it has 8 hash buckets initially. I don't know how it is grown, but you can check it by experimenting: evaluate a hash in scalar context, and you'll get a string containing eg "3/8" if it has 8 hash buckets of which 3 is not empty. As for the actual implementation, I can't say anything, but you can try to read perl's source, esp. hv.c.

For the bonus question, the C++ standard library implements associative arrays (they call it map) as tree structures, specifically red-black trees. Other implementations then gcc's library can use other kind of trees, but they can't use a hash table as the keys can be anything, and all the functions get about the keys is a comparision function. Ruby uses a hash table. Some lisps have balanced trees too. Gcc has functions for balanced trees too.

Question: does awk use hash-tables or trees or it depends on version.

Only slightly related to your question is that the linux kernel itself uses red-black trees for some memory-management functions; it might use hashes too somewhere. Reiserfs has a balanced-tree structure (where the key itself is the hash-key of the filename).

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://345211]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (7)
As of 2018-06-19 05:36 GMT
Find Nodes?
    Voting Booth?
    Should cpanminus be part of the standard Perl release?

    Results (111 votes). Check out past polls.