什么是矢量容量的目的

Question

Vector API定义了4种不同的构造函数:

Vector()

Vector(Collection<? extends E> c)

Vector(int initialCapacity)

Vector(int initialCapacity, int capacityIncrement)

但它们如何运作以及它们用于什么？我为什么要为矢量定义固定容量？即使我将初始容量设置为100,我也可以向向量添加101.项:

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());

在上面的代码中,第二个sysout(test.capacity())写入200.为什么此向量中的容量为200？初始容量为100,我没有定义容量增量.

我真的想知道是否有使用这些建筑师的真实世界的例子？

还有一个熟悉的问题:究竟是Vector.get(int position)和Vector.elementAt(int position)之间的区别？我读到在将Vector添加到Collection类之前定义了get方法,因此有必要在以后添加方法elementAt(int position).真的吗？或者还有其他差异吗？

Answer 1

什么是"初始"容量？

在最初的容量仅仅是:的能力Vector,在施工时间.

A Vector是一个可动态增长的数据结构,它会根据需要重新分配其后备阵列.因此,没有最终容量,但您可以设置其初始值.

以下是VectorAPI的摘录:

每个向量都试图通过维护a capacity和a 来优化存储管理capacityIncrement.所述capacity总是至少为矢量一样大size; 它通常更大,因为随着组件被添加到向量中,向量的存储以块的大小增加capacityIncrement.应用程序可以capacity在插入大量组件之前增加向量; 这减少了增量重新分配的数量.

注意施工后,也可以ensureCapacity用来达到同样的效果.

也可以看看

• 创建集合对象(List,Set等)时,通常会使用称为"initialCapacity"的参数.这个参数意味着什么,它是如何使用的？

为什么这有关系？

比方说,你有100个要插入的元素Vector.的null构造设置一个Vector具有10的初始容量,并生长时的大小加倍.这意味着要容纳100个元素,它可以加倍到20,40,80,然后最后加160,然后才能适应所有100个元素.

请注意,执行了4个增量重新分配步骤,当它最终适合所有100个元素时,仅使用60%的实际容量.另一方面,ensureCapacity(100)在插入之前(或使用适当的构造函数重载来实现相同的效果)将使该过程更有效,因为没有多余的未使用容量,并且该阵列仅需要重新分配一次.

请注意,渐近地,上述两个过程同样是最佳的(O(N)时间和O(N)空间),但当然后者在空间和时间上都是对前者的恒定时间改进.

当然,如果你设置ensureCapacity(10000000),只插入100个元素,你只能使用.001%的容量 - 这是多么浪费!因此,如果您提前知道要插入多少元素,则可以通过使用来提高处理效率(通过常数因素)ensureCapacity,但无论如何,Vector即使没有您的帮助,它仍可以自行完成.

也可以看看

• Java Set初始容量最佳实践

为什么加倍？

没有详细说明,这种增长倍增是几何扩展的一种形式,这使得每次操作能够进行恒定时间的摊销分析Vector.值得注意的是ArrayList,由数组支持的类似可扩展数据结构甚至没有指定其增长策略的细节,但OpenJDK版本的增长因子为3/2.

请注意,Vector实际上允许您设置非几何增长因子capacityIncrement.重要的是要意识到,如果你设置 capacityIncrement 一个小的非零值,你实际上可以使 Vector 渐进的表现变得可怕.1例如,如果将其设置为,则添加N元素将是一个O(N^2)操作!

ArrayList 不会让你自定义它的增长政策,因为你甚至不应该知道(也不关心,真的!).

也可以看看

• 维基百科:动态数组
  • 请参阅:几何扩展和摊销成本

杂

怎么样elementAt和get？

直接来自文档:

从Java 2平台v1.2开始,这个类被改进以实现List接口,使其成为Java Collections Framework的成员.与新的集合实现不同,Vector是synchronized.

public E elementAt(int index):返回指定索引处的组件.该方法在功能上与get(int)方法(它是List接口的一部分)相同.

因此按时间顺序,Vector在elementAt改装之前已经实施List,因此必须实施get.

注意关于Vector存在的部分synchronized.如果您不需要此功能,那ArrayList将是一个更好的选择,因为您不需要支付线程安全的费用.

也可以看看

• 如果线程安全性不是问题,则使用Java中的ArrayList与Vectors