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

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
Replies are listed 'Best First'.
Re^2: Minimum Hash keys allocated?
by flexvault (Prior) 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?

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

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (6)
As of 2016-05-31 19:43 GMT
Find Nodes?
    Voting Booth?