Vector Capacity

The Vector API defines 4 different constructors:

Vector()

Vector(Collection<? extends E> c)

Vector(int initialCapacity)

Vector(int initialCapacity, int capacityIncrement)

but how do they work and what are they used for? Why should i want to define a fixed capacity for a vector? Even if i set the initial capacity to 100, I can add a 101. item to the vector:

Vector<Object> test = new Vector<Object>(100);
for (int i = 0; i < 100; i++) {
    test.add(new Object());
}

test.add(new Object());
System.out.println(test.size());
System.out.println(test.capacity());

In the above code, the second sysout (test.capacity()) writes 200. Why is the capacity in this vector 200? The initial capacity is 100 and i didn't defined a capacity increment.

What's an "initial" capacity?

The initial capacity is simply that: the capacity of the Vector at construction time.

A Vector is a dynamically growable data structure, and it would reallocate its backing array as necessary. Thus, there is no final capacity, but you can set what its initial value is.

Answer:

Each vector tries to optimize storage management by maintaining a capacity and acapacityIncrement. The capacity is always at least as large as the vector size; it is usually larger because as components are added to the vector, the vector's storage increases in chunks the size of capacityIncrement. An application can increase the capacity of a vector before inserting a large number of components; this reduces the amount of incremental reallocation.

Why doubling?

Without going into details, this doubling in growth is a form of geometric expansion, which is what enabled constant-time amortized analysis per operation for Vector. It's worth noting that ArrayList, a similar growable data structure backed by an array, doesn't even specify the details of its growth policy, but the OpenJDK version has a growth factor of 3/2.

Do note that Vector actually allows you to set a non-geometric growth factor withcapacityIncrement. It's important to realize that if you set capacityIncrement to a small non-zero value, you can in fact make Vector perform horrible asymptotically. If you set it to 1, for example, then adding N elements would be an O(N^2) operation!

ArrayList doesn't let you customize its growth policy, since you're not even supposed to know (nor care, really!).

See also

• Wikipedia: Dynamic array
  • See: Geometric expansion and amortized cost