Why does dynamic array always double by a factor of 2?

I was wondering how does one decide the resizing factor by which dynami开发者_JAVA技巧c array resizes ? On wikipedia and else where I have always seen the number of elements being increased by a factor of 2? Why 2? Why not 3? how does one decide this factor ? IF it is language dependent I would like to know this for Java.

---

Actually in Java's ArrayList the formula to calculate the new capacity after a resize is:

newCapacity = (oldCapacity * 3)/2 + 1;

This means roughtly a 1.5 factor.

About the reason for this number I don't know but I hope someone has done a statistical analisys and found this is a good compromise between space and computational overhead.

---

Quoting from Wikipedia:

As n elements are inserted, the capacities form a geometric progression. Expanding the array by any constant proportion ensures that inserting n elements takes O(n) time overall, meaning that each insertion takes amortized constant time. The value of this proportion a leads to a time-space tradeoff: the average time per insertion operation is about a/(a−1), while the number of wasted cells is bounded above by (a−1)n. The choice of a depends on the library or application: a=3/21 and a=2[citation needed] is commonly-used.

Apparently it seems that it is a good compromise between CPU time and memory wasting. I guess the "best" value depends on what your application does.

---

Would you waste more space than you actually use?
If not, the factor should be less than or equal to 2.
If you want it to be an integer so it is simple to work with, there is only one choice.

---

There is another difference between a growth rate of 2X and a growth rate of 1.5X that nobody here has discussed yet.

Each time we allocate a new buffer to increase our dynamic array capacity, we are building up a region of unused memory preceding the array. If the growth rate is too high, then this region cannot ever be reused in the array.

To visualize, let "X" represent memory cells used by our array, and "O" represent memory cells that we can no longer use. A growth rate of 2X looks like so:

[X] -> [OXX] -> [OOOXXXX] -> [OOOOOOOXXXXXXXX]

... notice that the preceding O's keep growing! In fact, with a 2X growth rate, we can never use that memory again in our array.

But, with a 1.5X growth multiplier (rounded down, but at least 1), the usage looks like:

[X] -> [OXX] -> [OOOXXX] -> [OOOOOOXXXX] -> [XXXXXX]

Wait a sec, we were able to reclaim the old space! That's because the size of the unused space caught up with the size of the array.

If you work out the math, the limit growth factor is Phi (or about 1.618). Anything larger than Phi, and you cannot reclaim the old space.