2

Just five minutes ago I found out how ArrayList works. It has elementData field which is array with specific type, if we add element and elementData array is full, collection internally create another array by this formula:

(oldCapacity * 3) / 2 + 1

And copy data from old array to new one. I`m just wondering, why is that? why not just double last size? where can i get more theoretical information about internal representation of ArrayList collection with describing this formula. P.S. Sorry for my English, its not my native language.

kirugan
  • 2,514
  • 2
  • 22
  • 41
  • Doubling would be quite big growing steps. – MrSmith42 Jan 03 '13 at 22:00
  • ok doubling is bad, but why this one ? – kirugan Jan 03 '13 at 22:01
  • grow by about 50% is easy to calculate and I do not see why any other formular would be better. – MrSmith42 Jan 03 '13 at 22:03
  • I think it would be better if size is increased by 1 after each insertion like a linked list :D – aacanakin Jan 03 '13 at 22:03
  • Growing is expensive (slow) so you want to avoid it to happen often. – MrSmith42 Jan 03 '13 at 22:04
  • 1
    @aacanakin: With that approach, the cost of each insertion would be proportional to the size of the list; so, for example, starting with an empty list and inserting *n* elements would cost O(*n* ²). This would defeat much of the purpose of having array-backed lists to begin with. – ruakh Jan 03 '13 at 22:14
  • @ruakh: It would indeed. It would also be in direct violation of the `ArrayList` spec. – NPE Jan 03 '13 at 22:17
  • 1
    @aacanakin The idea is to strike a reasonable compromise between wasted memory, and the number of times you have to copy each list. Clearly, copying the list on every insertion to avoid overhead is not a compromise. – millimoose Jan 03 '13 at 22:17
  • @ruakh yeah you're right. But I only looked this problem from a memory-friendly perspective – aacanakin Jan 03 '13 at 22:19
  • 1
    @aacanakin An array-backed list with a growth factor smaller than 2 will still win over a linked list. That's "memory friendly enough". (Or to be more exact, an array-backed list that's filled to at least half capacity, which should be the common case.) – millimoose Jan 03 '13 at 22:27

2 Answers2

2

Actually, the growth policy is unspecified, except that it guarantees that adding an element has a constant amortized cost.

Both the scheme that you propose and the scheme used by your JDK offer such a guarantee. In fact, any multiplicative growth scheme would be compliant. Other languages/libraries increase the size by a factor of two, so that too is a common scheme. A different Java implementation could choose to follow that scheme, and still comply with the spec.

See the discussion in Amortized analysis of std::vector insertion -- it's about C++ but applies equally well to Java.

Community
  • 1
  • 1
NPE
  • 486,780
  • 108
  • 951
  • 1,012
0

There is likely no objective measure. We can avoid copying by wasting more memory, or we can save memory by copying more often. These 2 cannot be objectively measured in one goal function.

irreputable
  • 44,725
  • 9
  • 65
  • 93