| The
Math |
|
|
|
|
|
|
|
|
|
|
|
|
|
| • | Beginning: |
|||||||||||
| – | F=0,
S=2. P(i)=0 |
|||||||||||
| • | For
insert with no rehashing |
|||||||||||
| – | C(i+1)=1 |
|||||||||||
| – | P(i+1)-P(i)=2
(added non-empty slot) |
|||||||||||
| • | For
insert with rehashing of N items |
|||||||||||
| – | C(i+1)=1+N |
|||||||||||
| – | P(i+1)-P(i)=2-N
(before, F=N, S=2N. After, S=4N) |
|||||||||||