Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw

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 making s'mores by the fire in the courtyard of the Monastery: (4)
As of 2017-09-21 05:17 GMT
Find Nodes?
    Voting Booth?
    During the recent solar eclipse, I:

    Results (242 votes). Check out past polls.