4

Why does Java grow a full array by a factor of 3/2 instead of 2?

"The choice of a depends on the library or application: some textbooks use a = 2, but Java's ArrayList implementation uses a = 3/2 and the C implementation of Python's list data structure uses a = 9/8."

source wikipedia

Abimaran Kugathasan
  • 31,165
  • 11
  • 75
  • 105
George Newton
  • 3,153
  • 7
  • 34
  • 49
  • It is research result it seams. So if you want make your inherit `AbstractList` and override corresponding your requirements. – Ashot Karakhanyan Feb 07 '14 at 10:00
  • 2
    Because doubling the size at will eat memory faster than increasing by 1.5 or 1.1 . You have a tradeoff between how often you resize and how large the size will be. Probably 1.5 was a good one. – Stefano Sanfilippo Feb 07 '14 at 10:01
  • @StefanoSanfilippo Further, they can compute 1.5 pretty fast with an addition and a right shift compared to 1.1 – Michael Schmeißer Feb 07 '14 at 10:09
  • Possible duplicate http://stackoverflow.com/questions/1100311/what-is-the-ideal-growth-rate-for-a-dynamically-allocated-array – leventov Feb 07 '14 at 10:39

2 Answers2

5

In general, the choice of the growth factor depends mostly on experience and a good educated guess. You have to find the right balance between unecessary memory usage (for unused array space) and unecessary runtime usage (if the array has to be enlarged often). You also have to do this without knowing how big the list will be. The reason why it's 3/2 in Java is simply because someone thought it was the best.

André Stannek
  • 7,773
  • 31
  • 52
0

I've recorded some theoretical results about grow factor which could help you to choose a grow factor for your own data structure here: Magic Factors#Grow Factor. Higher grow factor leads to higher memory footprint and lower "reinsertions per element during construction" metric on average, when the size of the collection is unknown in advance.

I agree with André Stannek that 1.5 grow factor doesn't have any special properties and it is just someone's "final decision".

leventov
  • 14,760
  • 11
  • 69
  • 98