Clever Geek Handbook

Why is the new ability arraylist (oldCapacity * 3) / 2 + 1?

Why does makeCapacity () in Java ArrayList expand capacity with constant 1.5 or (oldCapacity * 3) / 2 + 1?

+3


source to share


2 answers


The main reason is the (asymptotic) difficulty of adding a sequence of items to a list.

Note that the method add

is called internally ensureCapacity(size+1)

. When the size of the internal array grows, all elements must be copied to the new larger array.



If the size was only increased by a constant amount (which will be 1 for each call add

), then adding n elements will have complexity O (n 2 ) .

Instead, the size is always increased by a constant factor. Then adding n elements only has O (n) complexity .

+3


source


Resizing an array is relatively expensive. He wants to try and make sure that if the method is invoked using the ensureCapacity(11)

, ensureCapacity(12)

, ensureCapacity(13)

, ... it does not change the size of the array each time. Thus, it changes to a reasonable chunk (50% increase) instead of the specified minimum.



+6


source






More articles:


All Articles