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

[ikegami]

in reply to Re: When does Perl double the number of buckets in hash?
in thread When does Perl double the number of buckets in hash?

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.

Using your numbers:

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.

[BrowserUk]

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