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