Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re: Minimum Hash keys allocated?

by BrowserUk (Pope)
on Sep 26, 2010 at 18:25 UTC ( #862105=note: print w/ replies, xml ) Need Help??


in reply to Minimum Hash keys allocated?

The first time you assign a value to a new hash, it gets allocated 8 slots. When the number of slots used reaches 6 (which may be more than 6 keys if you get hash collisions), it expands to 16 slots. And it doubles again when 3/4s of the slots (12/16) are used. And so on.

You can see this if you run the following code:

perl -wE"my %h;$h{$_}=$_, say $_, ':',scalar %h for 1 .. 1025" | more 1:1/8 2:2/8 3:3/8 4:3/8 ## collision 5:4/8 6:5/8 7:6/8 8:7/16 9:8/16 10:9/16 11:10/16 12:10/16 ## collision 13:10/16 ## collision 14:11/16 15:11/16 ## collision 16:14/32 17:14/32 ## collision ...

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.


Comment on Re: Minimum Hash keys allocated?
Download Code
Re^2: Minimum Hash keys allocated?
by flexvault (Parson) on Sep 26, 2010 at 21:32 UTC
    WOW . . .

    That was even a better answer than I expected!

    For the interactive application I've written/using, pre-allocating the hashes, has improvements of 8-24% using hashes with 256 to 2048 keys on AIX and even better on Linux. But I didn't know about how the algorithm worked on smaller hashes. With your great and simple script, I can test larger combinations as well.

    Thank you very much...Ed

    PS: Is the algorithm the same on perl 5.8.8?
      PS: Is the algorithm the same on perl 5.8.8?

      To my knowledge, it hasn't changed since before 5.6 days. Possibly never, but that's as far as I go back with Perl.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (2)
As of 2014-09-17 02:42 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (56 votes), past polls