### Re^2: When does Perl double the number of buckets in hash?

by ikegami (Pope)
 on Dec 01, 2011 at 00:36 UTC ( #940976=note: print w/replies, xml ) Need Help??

As shown by the code the OP posted, it actually happens when the number of elements (including the newly inserted element) is equal to the number buckets. What the OP missed is that it only happens if there's a collision.

```1  :  1/8
2  :  2/8
3  :  2/8           ## hash colision
4  :  2/8           ## hash colision
5  :  3/8
6  :  4/8
7  :  5/8
8  :  6/16         ## 8 == 8 => split
9  :  6/16
10  :  7/16
11  :  7/16        ## hash colision
12  :  8/16
13  :  9/16
14  :  9/16        ## hash colision
15  :  9/16        ## hash colision
16  :  10/16       ## 16 == 16 => split
17  :  15/32
18  :  15/32       ## hash colision
19  :  16/32
20  :  16/32       ## hash colision
21  :  16/32       ## hash colision
22  :  17/32
23  :  17/32       ## hash colision
24  :  18/32
25  :  19/32
26  :  19/32       ## hash colision
27  :  20/32
28  :  20/32       ## hash colision
29  :  20/32       ## hash colision
30  :  20/32       ## hash colision
31  :  21/32
32  :  25/64       ## 32 == 32 => split
...
60  :  40/64
61  :  40/64       ## hash colision
62  :  40/64       ## hash colision 5/8ths
63  :  41/64
64  :  51/128      ## 64 == 64 => split
...
128  :  85/128
129  :  106/256    ## 128 == 128 => split
130  :  107/256

There's a second condition that causes a split: A degenerate hash is detected. A degenerate hash is one that has a bucket with so many element as to make it slow to find keys in that bucket. I didn't try to determine the exact condition for when this occurs.

Replies are listed 'Best First'.
Re^3: When does Perl double the number of buckets in hash?
by BrowserUk (Pope) on Dec 01, 2011 at 00:54 UTC

Indeed. Thank you for the correction. I guess I was concentrating on the wrong column.

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
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.

The start of some sanity?

Create A New User
Node Status?
node history
Node Type: note [id://940976]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (5)
As of 2018-03-23 02:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (287 votes). Check out past polls.

Notices?