Whats the purpose of Vector capacity
The Vector API defines 4 different constructors:
Vector()
Vector(Collection<? extends E> c)
Vector(int ini开发者_JAVA百科tialCapacity)
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?
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 acapacityIncrement
. Thecapacity
is always at least as large as the vectorsize
; it is usually larger because as components are added to the vector, the vector's storage increases in chunks the size ofcapacityIncrement
. An application can increase thecapacity
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
andget
?
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
issynchronized
.
public E elementAt(int index)
: Returns the component at the specified index. This method is identical in functionality to theget(int)
method (which is part of theList
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
If you specify a zero or negative capacity increment, the capacity of the vector is doubled every time, as per the documentation for the capacityIncrement
field:
The amount by which the capacity of the vector is automatically incremented when its size becomes greater than its capacity. If the capacity increment is less than or equal to zero, the capacity of the vector is doubled each time it needs to grow.
If you only specify the capacity, the default capacityIncrement
is zero - hence the doubling behaviour.
You would specify a capacity if you already had a good idea of how large your collection would need to be - this avoids unnecessary copying.
As for get
and elementAt()
- yes, elementAt()
was added for the general collections API. Looking at the implementation, they're identical other than the precise details of the exception thrown in the error case.
精彩评论