java - Whats the purpose of Vector capacity

Question

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.

I really wonder if theres any real world example where these constrcutors are used?

And a smiliar question: whats exactly the difference between Vector.get(int position) and Vector.elementAt(int position)? I read that the method get was defined before Vector was added to the Collection class and so it was necessary to add the method elementAt(int position) later too. Is that true? Or are there any other differences?

Answer 1

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.

Here's an excerpt from Vector API:

Each vector tries to optimize storage management by maintaining a capacity and a capacityIncrement. 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.

Note that post-construction, you can also use ensureCapacity to achieve the same effect.

See also

• When you create a collection object (List, Set, etc), usually they take a parameter known as “initialCapacity”. What does this parameter mean and how is it used ?

---

Why does it matter?

Let's say for example you have 100 elements that you want to insert into a Vector. The nullary constructor sets a Vector to have an initial capacity of 10, and doubles in size when growing. This means that to accommodate 100 elements, it would double to 20, 40, 80, and then finally 160, before it can fit all 100 elements.

Note that 4 incremental reallocation steps were performed, and when it finally fits all 100 elements, only 60% of the actual capacity is used. On the other hand, an ensureCapacity(100) (or using the appropriate constructor overload to achieve the same effect) prior to insertion would make the process more efficient, since there's no excess unused capacity, and the array would only need to be reallocated once.

Do note that asymptotically, the two processes above are equally optimal (O(N) time and O(N) space), but of course the the latter is a constant-time improvement over the former both in space and time.

Of course, if you set ensureCapacity(10000000), and only insert 100 elements, you'd be using only .001% of the capacity -- what a waste! So if you know ahead of time how many elements you're about to insert, you can make the process more efficient (by a constant factor) by using ensureCapacity, but in any case Vector still does a fine job on its own even without your help.

See also

• Java Set Initial Capacity Best Practice

---

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 with capacityIncrement. 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

---

Miscellaneous

What about elementAt and get?

Straight from the documentation:

As of the Java 2 platform v1.2, this class was retrofitted to implement the List interface, making it a member of the Java Collections Framework. Unlike the new collection implementations, Vector is synchronized.

public E elementAt(int index) : Returns the component at the specified index. This method is identical in functionality to the get(int) method (which is part of the List interface).

So chronologically, Vector had elementAt, before it was retrofitted to implement List, and therefore must implement get.

Note the part about Vector being synchronized. If you don't need this feature, ArrayList would be a much better choice since you're not paying for the cost of thread-safety.

See also

• ArrayList vs. Vectors in Java if thread safety isn’t a concern