Growth Policy of ArrayList in Java 6SE

I was wondering if anyone knows the growth policy of ArrayList in Java 1.6? The java doc says

The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

But I just wonder the details because I know the size I'm targeting to start but I want to make sure I'm making the initial size big enough to not cause an instant resize. I know with HashMap you can set a load factor is there something similar happening in the back ground? Or is it always growing when space is out?

Answer1:

ArrayList doesn't need a loadFactor as it always grows when it is 100% filled, so you can create it with exactly the size you know in advance and it won't grow if you fill that many elements in later. Hashtables on the other hand become ever more inefficient the more they are filled, and thus you can ajust the tradoff between performance and wasted space with the loadFactor, but this isn't the case for growable Arrays like ArrayList.

Answer2:

This is what I see when I look at the source of ensureCapacity:

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

Answer3:

You can read the source for yourself. Every copy of the Sun JDK comes with a src.zip that contains the source.

Answer4:

int newCapacity = oldCapacity + (oldCapacity >> 1);

It is 50% increment .

if 100 elements are there ensureCapacityInternal() will increase to size of 150 .

Please check source code in JDK 7

人吐槽 人点赞

Recommend

Comment

用户名: 密码:
验证码: 匿名发表

你可以使用这些语言

查看评论:Growth Policy of ArrayList in Java 6SE