Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

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).


Comment on Re: Perl Internals: Hashes
Select or Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (8)
As of 2015-07-30 17:58 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (273 votes), past polls