ArrayList: how does the size increase?
I have a basic question on Java ArrayList.
When ArrayList is declared and initialized using the default constructor, memory space for 10 elements is created. Now, when I add an 11th element, what happens? Will new memory space be created with 20 (or more) element capacity (this requires copying elements from 开发者_Python百科1st memory location to new location) OR some thing else?
I checked the ArrayList API documentation for Java 1.4.2. But I didn't find an answer.
Please share the knowledge. Thanks.
Edit: New links:
ArrayListin the Java 11 API documentation- Java(TM) 2 SDK, Standard Edition Documentation 1.4.2
A new array is created and the contents of the old one are copied over. That's all you know at the API level. Quoting from the docs (my emphasis):
Each
ArrayListinstance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.
In terms of how it actually happens with a specific implementation of ArrayList (such as Sun's), in their case you can see the gory details in the source. But of course, relying on the details of a specific implementation isn't usually a good idea...
Sun's JDK6:
I believe that it grows to 15 elements. Not coding it out, but looking at the grow() code in the jdk.
int newCapacity then = 10 + (10 >> 1) = 15.
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
From the Javadoc, it says this is from Java 2 and on, so its a safe bet in the Sun JDK.
EDIT : for those who didn't get what's the connection between multiplying factor 1.5 and int newCapacity = oldCapacity + (oldCapacity >> 1);
>> is right shift operator which reduces a number to its half.
Thus,
int newCapacity = oldCapacity + (oldCapacity >> 1);
=> int newCapacity = oldCapacity + 0.5*oldCapacity;
=> int newCapacity = 1.5*oldCapacity ;
It will depend on the implementation, but from the Sun Java 6 source code:
int newCapacity = (oldCapacity * 3)/2 + 1;
That's in the ensureCapacity method. Other JDK implementations may vary.
Up to JDK 6 the the capacity grow with formula newCapacity = (oldCapacity * 3/2) + 1.
In JDK 7 and above the formula changes to newCapacity = oldCapacity + (oldCapacity >> 1).
So if initial capacity is 10 then new capacity will be 16 in JDK6 and 15 in above JDK7
When we try to add an object to the arraylist,
Java checks to ensure that there is enough capacity in the existing array to hold the new object. If not, a new array of a greater size is created, the old array is copied to new array using Arrays.copyOf and the new array is assigned to the existing array.
Look at the code below (taken from Java ArrayList Code at GrepCode.com).
Edit:
public ArrayList() Constructs an empty list with an initial capacity of ten.
public ArrayList(int initialCapacity) we can specify initial capacity.
public ArrayList(Collection c) Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.
Now when we use ArrayList() constructore we get a ArrayList with Size=10 On adding 11th element in the list new Arraylist is created inside ensureCapacity() method.
Using following formula:
int newCapacity= (oldCapacity * 3)/2 +1;
Lets look at this test case (jdk1.8)
@Test
public void testArraySize() throws Exception {
List<String> list = new ArrayList<>();
list.add("ds");
list.add("cx");
list.add("cx");
list.add("ww");
list.add("ds");
list.add("cx");
list.add("cx");
list.add("ww");
list.add("ds");
list.add("cx");
list.add("last");
}
1)Put break point on the line when "last" is inserted
2)Go to the add method of ArrayList
You will see
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
Go to ensureCapacityInternal method, this method calls
ensureExplicitCapacityprivate void ensureExplicitCapacity(int minCapacity) { modCount++;
// overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } return true;
In our example minCapacity is equal to 11 11-10 > 0 therefore grow method will be called
5)
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
Lets describe each step:
oldCapacity= 10 by default, in java 8 arraylist's capacity is 10 , you can override it by passing another value in constructorint newCapacity = oldCapacity + (oldCapacity >> 1);Here newCapacity is equal to oldCapacity plus oldCapacity with right shift by one (oldCapacity is 10this is the binary representation00001010moving one bit to right will make00000101which is 5 in decimal thereforenewCapacityis10 + 5 = 15)if (newCapacity - minCapacity < 0) newCapacity = minCapacity; For example your initial capacity was 1(
new ArrayList<>(1)), when you add the second elementnewCapacitywill be equal to1(oldCapacity) + 0 (moved to right by one bit) = 1In this case newCapacity is less than minCapacity andelementData( objects arrayObject[]inside arrayList that stores the data) can't hold new element therefore newCapacity will be equal to minCapacityif (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);
Check if array size reached MAX_ARRAY_SIZE (which is Integer.MAX - 8) Why the maximum array size of ArrayList is Integer.MAX_VALUE - 8?
- Finally it copies old values to the newArray with length 15
when a ArrayList is declared and initialized using default constructor, memory space for 10 elements will be created. now, when i add 11 th element, what happens is
ArrayList create a new object with the following size
i.e OldCapacity*3/2+1 = 10*3/2+1 =16
Typically, the memory for ArrayList type containers is increased by doubling it. Thus, if you initially had space for 10 items and you added 10, the eleventh item will be added to a new (internal) array of 20 items. The reason for this is that the incremental cost of adding items is reduced from O(n^2) if the array had been incremented in fixed size increments to a nice O(n) when doubling the size each time the internal array is full.
Context java 8
I give my answer here in the context of Oracle java 8 implementation, since after reading all the answers, I found that an answer in the context of java 6 has given by gmgmiller, and another answer has been given in the context of java 7. But how java 8 implementes the size increasement has not been given.
In java 8, the size increasement behavior is the same as java 6, see the grow method of ArrayList:
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
the key code is this line:
int newCapacity = oldCapacity + (oldCapacity >> 1);
So clearly, the growth factor is also 1.5, the same as java 6.
When ArrayList is declared and initialized using the default constructor, memory space for 10 elements is created.
NO. When ArrayList is initialized, memory allocation is made for an empty array. Memory allocation for default capacity (10) is made only upon addition of first element to ArrayList.
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
* DEFAULT_CAPACITY when the first element is added.
*/
private transient Object[] elementData;
P.S. Don't have enough reputation to comment on question, so I am putting this as an answer as nobody pointed out this incorrect assumption earlier.
static int getCapacity(ArrayList<?> list) throws Exception {
Field dataField = ArrayList.class.getDeclaredField("elementData");
dataField.setAccessible(true);
return ((Object[]) dataField.get(list)).length;
}
use the above method to check the size when the arraylist is being modified.
ArrayList does increases the size on load factor on following cases:
- Initial Capacity: 10
- Load Factor: 1 (i.e. when the list is full)
- Growth Rate: current_size + current_size/2
Context : JDK 7
While adding an element into the ArrayList, the following public ensureCapacityInternal calls and the other private method calls happen internally to increase the size. This is what dynamically increase the size of ArrayList.
while viewing the code you can understand the logic by naming conventions, because of this reason I am not adding explicit description
public boolean add(E paramE) {
ensureCapacityInternal(this.size + 1);
this.elementData[(this.size++)] = paramE;
return true;
}
private void ensureCapacityInternal(int paramInt) {
if (this.elementData == EMPTY_ELEMENTDATA)
paramInt = Math.max(10, paramInt);
ensureExplicitCapacity(paramInt);
}
private void ensureExplicitCapacity(int paramInt) {
this.modCount += 1;
if (paramInt - this.elementData.length <= 0)
return;
grow(paramInt);
}
private void grow(int paramInt) {
int i = this.elementData.length;
int j = i + (i >> 1);
if (j - paramInt < 0)
j = paramInt;
if (j - 2147483639 > 0)
j = hugeCapacity(paramInt);
this.elementData = Arrays.copyOf(this.elementData, j);
}
From JDK source code, I found below code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
ArrayList in Java grows by 50% of its original capacity once it is full.
What happens is a new Array is created with n*2 spaces, then all items in the old array are copied over and the new item is inserted in the first free space. All in all, this results in O(N) add time for the ArrayList.
If you're using Eclipse, install Jad and Jadclipse to decompile the JARs held in the library. I did this to read the original source code.
Size of ArrayList increases with n+n/2+1 always.
Default capacity of ArrayList is 10. Once the Capacity reaches its maximum capacity, Size of the ArrayList will be 16, once the capacity reaches its maximum capacity of 16, size of the ArrayList will be 25 and keep on increasing based on Data size.....
How? Here is the Answer and Formula
New capacity = (Current Capacity * 3/2) + 1
So, if the default capacity is 10, then
Current Capacity = 10
New capacity = (10 * 3/2) + 1
Output is 16
In Jdk 1.6: New capacity = (Current Capacity * 3/2) + 1;
In Jdk 1.7:
int j = i + (i >> 1); this is same as New capacity = (Current Capacity * 1/2) + Current Capacity;
ex:size will increase like :10-->15-->22-->33
(oldSize * 3)/2 + 1
If you are using default constructor then initial size of ArrayList will be 10 else you can pass the initial size of array while creating the object of ArrayList.
Example: In case default constructor
List<String> list = new ArrayList<>();
list.size()
Example: In case parameterized constructor
List<String> list = new ArrayList<>(5);
list.size()
Arraylist default capacity is 10.
[1,2,3,4,5.....10]
if you want to increase the size of Arraylist in java, you can apply this
formula-
int newcapacity, current capacity;
newcapacity =((current capacity*3/2)+1)
arralist will be [1,2,3,4,5.....10,11] and arraylist capacity is 16.
This is the lastest JDK version (2022 June), JDK 18, and you can download it on https://jdk.java.net/18/ or we can look the source on Github https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/ArrayList.java
When you add an item into your ArrayList, Java will ensure that it can hold at least the items was in it and the new item. Java prefer to increase the capacity to 1.5* current capacity according to this expression
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);.
oldCapacity >> 1 means 0.5 * oldCapacity
so newLength will be 1.5 * oldCapacity if it is positive and not overflow
Here are the code snippets:
src/java.base/share/classes/java/util/ArrayList.java
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
private Object[] grow() {
return grow(size + 1);
}
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
src/java.base/share/classes/jdk/internal/util/ArraysSupport.java
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
return prefLength;
} else {
return hugeLength(oldLength, minGrowth);
}
}
ArrayList is the class of Collection Interface. Java is open source language we can change its implementation. here java predefined implementation is: new capacity = (currentCapacity*3)/2 + 1; or in JAVASE8 newcapacity = oldCapacity+(oldcapacity>>1);
The default size of the arraylist is 10. When we add the 11th ....arraylist increases the size (n*2). The values stored in old arraylist are copied into the new arraylist whose size is 20.
加载中,请稍侯......
精彩评论