VectorのJavaコレクションを徹底解析

2022-02-21 01:12:43

I. ベクタープライマー

ベクタークラスと呼ばれ、要素数の異なるオブジェクトの配列のための動的配列を実装しています。ベクタークラスは配列と同様に0から始まる添え字で要素の位置を表しますが、配列と異なり、ベクターオブジェクトを作成すると、ベクターオブジェクトの要素数の増減に合わせて配列の要素数が自動的に変化します。

しかし、それはJavaで配列とベクターを比較することは合理的ではない、Javaのコレクションの配列の位置は、しばしば基本的なストレージとして使用されるため、つまり、配列の基本的な使用でJavaコレクションの多くは、方法メモリによると、連続メモリと不連続メモリに分割されているためです。この時間は、データ構造、配列と連鎖表の2種類に対応し、例えば、JavaのArrayListでは、HashMapと他のデータ構造は、配列の助けを借りて実装されて、もちろん、多くのデータ構造がHashMapの助けを借りて実装されて、それも実際には配列の助けを借りて実装されている。

VectorとArrayListの主な違いは、どちらも配列ベースのリストであること、そしてスレッドセーフであることです。 主な違いは、先ほどArrayListがスレッドセーフでないという話をしましたが、ArrayListのスレッドセーフです。 Collections.synchronizedList(new ArrayList<>()); それと同じように、もう一つの解決策はVectorを使うことです。

もうひとつは、VectorもArrayListもListの実装ですが、VectorはArrayListよりも早く登場し、JDK1.0には存在しましたが、ArrayListはJDK1.2から登場したので、現在の開発ではVectorがあまり使われないという点です。主な理由は、スレッドセーフを実現するための非効率な方法だからですが、もしJavaが同期ロックの効率を向上させることがあれば、Vectorはまだ良い選択となります

1. ベクターの取扱説明書

マニュアルを見る前に、クラスの継承関係の全体像を見てみましょう。

ここから、これはListファミリーに属することがわかります。

/**
 * The {@code Vector} class implements a growable array of objects. Like an array, it contains components that can be accessed using an integer index.
 * However, the size of a {@code Vector} can grow or shrink as needed to accommodate
 However, the size of a {@code Vector} can grow or shrink as needed to accommodate * adding and removing items after the {@code Vector} has been created.
 * Vector implements a dynamic array, just like an array, whose elements can be accessed using an integer subscript, but the size of a {@code Vector} can grow or shrink as needed to accommodate adding and removing items after the {@code Vector} has been created
 * 
Each vector tries to optimize storage management by maintaining a {@code capacity} and a {@code capacityIncrement}. The
 * {@code capacity} is always at least as large as the vector size; 
 The * vector consistently optimizes storage management by maintaining a capacity and a {@code capacityIncrement}.
 * it is usually larger because as components are added to the vector, the vector's storage increases in chunks the size of 
 * {@code capacityIncrement}. 
 * capacity is usually larger than size 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.
 * An application can increase the capacity of a vector before inserting a large number of data; this reduces the amount of incremental reallocation overhead
 * 
 The iterators returned by this class's {@link #iterator() iterator} and {@link #listIterator(int) listIterator} 
 * methods are 
fail-fast
: if the vector is structurally modified at any time after the iterator is created, in any way 
 * except through the iterator's own {@link ListIterator#remove() remove} or {@link ListIterator#add(Object) add} methods, the iterator 
 * will throw a {@link ConcurrentModificationException}.  Thus, in the face of
 * concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at 
 Thus, in the face of * concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at * an undetermined time in the future.  
 * The main real-quick failure in the paragraph above is that if you are in the middle of a traversal and the collection is modified, your traversal will fail, so you can use the iterator's modification method instead of the collection's modification method
 * The {@link Enumeration Enumerations} returned by the {@link #elements() elements} method are 
not
 fail-fast.
 * 
Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification.  
 * Fail-fast iterators throw {@code ConcurrentModificationException} on a best-effort basis. Therefore, it would be wrong to write a
 Therefore, it would be wrong to write a * program that depended on this
 Therefore, it would be wrong to write a * program that depended on this * exception for its correctness:  
The fail-fast behavior of iterators should be used only to detect bugs.

 * This paragraph has been translated several times before, because it's the same every time, so I won't translate it here
 * 
As of the Java 2 platform v1.2, this class was retrofitted to implement the {@link List} interface, making it a member of the
 * 
 Java Collections Framework
.  Unlike the new collection
 * If a thread-safe implementation is not needed, it is recommended to use {@link
 * ArrayList} in place of {@code Vector}.
 * In java 1.2, which is the java2 platform, the class was improved to implement the List interface, making it a member of java Collections, and unlike the new collection (ArrayList) implementation, the
 * Vector is synchronous, if a thread-safe implementation is not needed, it is recommended to use ArrayList instead of Vector
 * @author Lee Boynton
 * @author Jonathan Payne
 * @see Collection
 * @see LinkedList
 * @since JDK1.0
 */

public class Vector
 extends AbstractList
 implements List

, RandomAccess, Cloneable, java.io.
Serializable { ... ... }

2. ベクターの内部構成

要素データ

elementDataはVectorの要素を格納するもので、それ自体は配列です。


/**
 * The array buffer into which the components of the vector are stored. The capacity of the vector is the length of this array buffer,
 The capacity of the vector is the length of this array buffer, * and is at least large enough to contain all the vector's elements.
 * elementData is an array buffer into which the components of the vector are stored. The capacity of the vector is the length of this array buffer, * and is at least large enough to contain all the vector's elements.
 *The 
Any array elements following the last element in the Vector are null.
 * @serial
 */

  protected Object[] elementData;

要素数

Vectorに格納されている要素の数は、実際にはArrayListにおけるサイズですが、別の名前が付いています。


/* The number of valid components in this {@code Vector} object.
 * The number of valid components in this {@code Vector} object. components {@code elementData[0]} through
 * {@code elementData[elementCount-1]} are the actual items.
 * The number of valid elements in the Vector, the elements in the elementData array are from 0 i.e. elementData[0] to elementCount-1 i.e. elementData[elementCount-1].
 * @serial
 */
protected int elementCount;

キャパシティインクリメント

capacityIncrementは動的配列の成長率で、増分と解釈することもできます。Vectorの作成時にcapacityIncrementのサイズを指定すると、Vector内の動的配列の容量が増えるたびに、その増加分がcapacityIncrementになります。このクラスのアノテーションにあるように


/**
 * The amount by which the capacity of the vector is automatically incremented when its size becomes greater than its capacity.  
 * 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 the capacityIncrement is less than or equal to zero, the capacity * of the vector is doubled each time it needs to grow.
 * @serial
 */
protected int capacityIncrement;

// Default constructor
Vector()
// capacity is the default capacity size of the Vector. When the capacity is increased due to adding data, the capacity will be doubled each time.
Vector(int capacity)
// capacity is the default capacity size of Vector, capacityIncrement is the increment value each time the capacity of Vector is increased.
Vector(int capacity, int capacityIncrement)
// Create a Vector containing a collection
Vector(Collection<? extends E> collection)

3. ベクター用コンストラクタ


/**
 * Constructs an empty vector so that its internal data array has size {@code 10} and its standard capacity increment is zero.
 * Constructs an empty vector so that its internal data array has size {@code 10} and its standard capacity increment is zero.
 */
public Vector() {
    this(10);
}

/**
 * Constructs an empty vector with the specified initial capacity and
 * with its capacity increment equal to zero.
 * Constructs an empty vector with the specified initial capacity and * with its capacity increment equal to zero.
 * @param initialCapacity the initial capacity of the vector
 * @throws IllegalArgumentException if the specified initial capacity is negative Throws an exception when the argument is negative
 */
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

参照されない構造

このコンストラクタ・メソッドは、実際には、初期容量を指定するコンストラクタ・メソッドを呼び出します。


    /**
     * Constructs an empty vector with the specified initial capacity and
     * capacity increment.
     * Constructs an empty vector with the specified initial capacity and * capacity increment.
     * @param initialCapacity the initial capacity of the vector
     * @param capacityIncrement the amount by which the capacity is
     * increased when the vector overflows
     * @throws IllegalArgumentException if the specified initial capacity is negative
     * throws an exception if the initial capacity is negative
     */
    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

/**
 * Constructs a vector containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 * Constructs a vector containing the elements of the specified collection, in the order they are returned by the collection's * iterator.
 * @param c the collection whose elements are to be placed into this vector
 * @throws NullPointerException if the specified collection is null Throws an exception if the parameter collection is null
 * @since 1.2
 */
public Vector(Collection<? extends E> c) {
    // Because the toArray method of the collection is called here, an exception is thrown if the collection is empty
    Object[] a = c.toArray();
    elementCount = a.length;
    // The following completes the addition of the elements to the collection, if c is an ArrayList, then the assignment is done directly, otherwise the copy method of Arrays is used
    if (c.getClass() == ArrayList.class) {
        elementData = a;
    } else {
        elementData = Arrays.copyOf(a, elementCount, Object[].class);
    }
}


@Test
public void testAdd() {
    Vector
 vector = new Vector(10);
    vector.add("a");
}

初期容量の指定


/**
 * Appends the specified element to the end of this Vector.
 * Appends the specified element to the end of this Vector, note that this method is synchronized
 * @param e element to be appended to this Vector
 * @return {@code true} (as specified by {@link Collection#add})
 * @since 1.2
 */
public synchronized boolean add(E e) {
    // record modifications
    modCount++;
    // ensure capacity, this is to ensure that the internal array is large enough to hold the element before adding it, also in ArrayList, it is like this ensureCapacityInternal(size + 1), (elementCount + 1) can be considered as required
    ensureCapacityHelper(elementCount + 1);
    // Once the capacity is guaranteed, we add the element to the specified position in the array
    elementData[elementCount++] = e;
    return true;
}

初期容量と増分を指定する

実は、上記のコンストラクタのメソッドは、すべてこのコンストラクタで呼び出されます。


ensureCapacityHelper

他のコレクションを元に作成


/* This implements the unsynchronized semantics of ensureCapacity.
 * This implements the unsynchronized semantics of ensureCapacity.
 * Synchronized methods in this class can internally call this
 Synchronized methods in this class can internally call this * method for ensuring capacity without incurring the cost of an
 Synchronized methods in this class can internally call this * method for ensuring capacity without incurring the cost of an * extra synchronization.
 * See
 * @see #ensureCapacity(int)
 */
private void ensureCapacityHelper(int minCapacity) {
    // Determine if it needs to be expanded, if the minimum required capacity is greater than the actual storage capacity then it needs to be expanded
    if (minCapacity - elementData.length > 0)
        // method to expand the capacity
        grow(minCapacity);
}

II. ベクターの一般的な方法

1. メソッドを追加する


private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // if capacityIncrement>0 then the new capacity is oldCapacity + capacityIncrement; otherwise 2 times oldCapacity
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // Complete the expansion and data migration
    elementData = Arrays.copyOf(elementData, newCapacity);
}

ここでは、addメソッドのソースコードをトレースします。


/**
* Inserts the specified element at the specified position in this Vector.
* Shifts the element currently at that position (if any) and any
* Subsequent elements to the right (adds one to their indices).
* Inserts a specified element at the specified position in the Vector, and if there is an element at the current position, shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).
* to the right of the previous position
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws ArrayIndexOutOfBoundsException if the index is out of range
* ({@code index < 0 || index > size()})
* @since 1.2
*/   
public void add(int index, E element) {
   insertElementAt(element, index);
}

次に /** * Inserts the specified object as a component in this vector at the specified {@code index}. * Each component in this vector with an index greater or equal to the specified {@code index} is shifted upward to have an index one greater than the value it had previously. * The element is inserted at the specified position, and the current position and its subsequent positions are shifted upward to the next position from the current position *

The index must be a value greater than or equal to {@code 0} and less than or equal to the current size of the vector. (If the * index is equal to the current size of the vector, the new element is appended to the Vector.) * This position must be between 0 and size, if the index is equal to size, the element will be appended to the end of the Vector * @param obj the component to insert * @param index where to insert the new component * @throws ArrayIndexOutOfBoundsException if the index is out of range ({@code index < 0 || index > size()}) */

public synchronized void insertElementAt(E obj, int index) { modCount++; if (index > elementCount) { throw new ArrayIndexOutOfBoundsException(index + " > " + elementCount); } // The following methods are explained earlier, but they will ensure that there is enough space, then copy the index and the elements after it to index+1, and then place them in order ensureCapacityHelper(elementCount + 1); System.arraycopy(elementData, index, elementData, index + 1, elementCount - index); elementData[index] = obj; elementCount++; } /** * Returns the element at the specified position in this Vector. * Returns the element at the specified position in this Vector. * @param index index of the element to return * @return object at the specified index * @throws ArrayIndexOutOfBoundsException if the index is out of range ({@code index < 0 || index >= size()}) * @since 1.2 */ public synchronized E get(int index) { // if index >= elementCount then throw an exception because the last element is elementData[elementCount-1] if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); return elementData(index); } /** * Returns the specific data */ @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; }

Integer value = null; Iterator size = vec.iterator(); while(size.hasNext()){ value = size.next(); }

Integer value = null; int size = vec.size(); for (int i=0; i<size; i++) { value = (Integer)vec.get(i); }

Integer value = null; for (Integer integ:vec) { value = integ; }

Integer value = null; Enumeration enu = vec.elements(); while (enu.hasMoreElements()) { value = (Integer)enu.nextElement(); }

iteratorThroughRandomAccess: 313 ms iteratorThroughIterator: 279 ms iteratorThroughFor2: 287 ms iteratorThroughEnumeration: 289 ms @Test public void iterator() { Vector vec = new Vector(); for (int i = 0; i < 10000000; i++) { vec.add(i); } iteratorThroughRandomAccess(vec); iteratorThroughIterator(vec); iteratorThroughFor2(vec); iteratorThroughEnumeration(vec); } private static void isRandomAccessSupported(List list) { if (list instanceof RandomAccess) { System.out.println("RandomAccess implemented!"); } else { System.out.println("RandomAccess not implemented!"); } } public static void iteratorThroughRandomAccess(List list) { long startTime; long endTime; startTime = System.currentTimeMillis(); int size = list.size(); // Note here that you don't want to put i < list.size() directly in the for loop, because it will call the size method every time and there will be performance loss for (int i = 0; i < size; i++) { list.get(i); } endTime = System.currentTimeMillis(); long interval = endTime - startTime; System.out.println("iteratorThroughRandomAccess:" + interval + " ms"); } public static void iteratorThroughIterator(List list) { long startTime; long endTime; startTime = System.currentTimeMillis(); for (Iterator iter = list.iterator(); iter.hasNext(); ) { iter.next(); } endTime = System.currentTimeMillis(); long interval = endTime - startTime; System.out.println("iteratorThroughIterator:" + interval + " ms"); } public static void iteratorThroughFor2(List list) { long startTime; long endTime; startTime = System.currentTimeMillis(); for (Object obj : list) ; endTime = System.currentTimeMillis(); long interval = endTime - startTime; System.out.println("iteratorThroughFor2: " + interval + " ms"); } public static void iteratorThroughEnumeration(Vector vec) { long startTime; long endTime; startTime = System.currentTimeMillis(); for (Enumeration enu = vec.elements(); enu.hasMoreElements(); ) { enu.nextElement(); } endTime = System.currentTimeMillis(); long interval = endTime - startTime; System.out.println("iteratorThroughEnumeration:" + interval + " ms"); }

iteratorThroughIterator: 247 ms iteratorThroughIterator: 17 ms

@Test public void iterator2() { Vector vec = new Vector(); ArrayList arr = new ArrayList(); for (int i = 0; i < 10000000; i++) { vec.add(i); arr.add(i); } //iteratorThroughIterator still uses the above code iteratorThroughIterator(vec); iteratorThroughIterator(arr); }

iteratorThroughIterator: 221 ms iteratorThroughIterator: 12 ms

public ListIterator listIterator() { return list.listIterator(); // Must be manually synched by user }

@Test public void iterator3() { Vector vec = new Vector(); ArrayList arr = new ArrayList(); for (int i = 0; i < 10000000; i++) { vec.add(i); arr.add(i); } iteratorThroughIterator(vec); iteratorThroughIterator(Collections.synchronizedList(arr)); }

public ListIterator listIterator() { return list.listIterator(); // Must be manually synched by user }


public ListIterator
 listIterator() {
    return list.listIterator(); // Must be manually synched by user
}

容量を拡大するための具体的な方法は以下の通りです。


@Test
public void iterator3() {
    Vector vec = new Vector();
    ArrayList arr = new ArrayList();
    for (int i = 0; i < 10000000; i++) {
        vec.add(i);
        arr.add(i);
    }
    iteratorThroughIterator(vec);
    iteratorThroughIterator(Collections.synchronizedList(arr));
}

2. add(int index, E element)

このメソッドは主に要素 指定された位置に と add(E e) ベクトルの末尾に要素を追加します．


public ListIterator
 listIterator() {
    return list.listIterator(); // Must be manually synched by user
}

次に、insertElementAtの実装を見てみましょう。


@Test
public void iterator3() {
    Vector vec = new Vector();
    ArrayList arr = new ArrayList();
    for (int i = 0; i < 10000000; i++) {
        vec.add(i);
        arr.add(i);
    }
    iteratorThroughIterator(vec);
    iteratorThroughIterator(Collections.synchronizedList(arr));
}

3.取得方法


public ListIterator
 listIterator() {
    return list.listIterator(); // Must be manually synched by user
}

4. トラバーサル方式

4つのトラバーサルの方法

ベクター対応 4つのトラバーサルメソッド . 効率に若干の差があるかもしれませんが、大きな差ではありません

1つ目は、スルー イテレータ のトラバーサルです。つまり、イテレータを通過するのです。


@Test
public void iterator3() {
    Vector vec = new Vector();
    ArrayList arr = new ArrayList();
    for (int i = 0; i < 10000000; i++) {
        vec.add(i);
        arr.add(i);
    }
    iteratorThroughIterator(vec);
    iteratorThroughIterator(Collections.synchronizedList(arr));
}

2つ目は ランダムアクセス であり、インデックス値でトラバースする。VectorはRandomAccessインターフェイスを実装しているので、インデックス値による要素のランダムアクセスをサポートしています。


public ListIterator
 listIterator() {
    return list.listIterator(); // Must be manually synched by user
}

3つ目は 別の種類のforループ


@Test
public void iterator3() {
    Vector vec = new Vector();
    ArrayList arr = new ArrayList();
    for (int i = 0; i < 10000000; i++) {
        vec.add(i);
        arr.add(i);
    }
    iteratorThroughIterator(vec);
    iteratorThroughIterator(Collections.synchronizedList(arr));
}

4枚目 列挙型トラバーサル


public ListIterator
 listIterator() {
    return list.listIterator(); // Must be manually synched by user
}

トラバーサルの性能テスト

以下にあるテストコードは、まずこちらに掲載されていますが、全体的なパフォーマンスの差は大きくないことがわかると思います


@Test
public void iterator3() {
    Vector vec = new Vector();
    ArrayList arr = new ArrayList();
    for (int i = 0; i < 10000000; i++) {
        vec.add(i);
        arr.add(i);
    }
    iteratorThroughIterator(vec);
    iteratorThroughIterator(Collections.synchronizedList(arr));
}

ArrayListとの比較

比較した結果を貼っておきましょう。上はVectorの探索時間、下はArrayListの探索時間ですが、ここではArrayListの17msがVectorの247msよりはるかに優れていることが分かります。


iteratorThroughIterator: 247 ms
iteratorThroughIterator: 17 ms

ここでは、トラバーサルのコードを掲載します。


@Test
public void iterator2() {
    Vector vec = new Vector();
    ArrayList arr = new ArrayList();
    for (int i = 0; i < 10000000; i++) {
        vec.add(i);
        arr.add(i);
    }
    //iteratorThroughIterator still uses the above code
    iteratorThroughIterator(vec);
    iteratorThroughIterator(arr);
}

Collections.synchronizedList()と比較します。

比較というより、Collections.synchronizedXXX() の返されたコレクションを走査するとき、スレッドセーフに注意する必要があることをここに念のため書いておくと、ここで返されたオブジェクトはその走査メソッドによって同期されていないため


iteratorThroughIterator: 221 ms
iteratorThroughIterator: 12 ms

以下はそのソースコードです。


public ListIterator
 listIterator() {
    return list.listIterator(); // Must be manually synched by user
}

以下はテストコードです。


@Test
public void iterator3() {
    Vector vec = new Vector();
    ArrayList arr = new ArrayList();
    for (int i = 0; i < 10000000; i++) {
        vec.add(i);
        arr.add(i);
    }
    iteratorThroughIterator(vec);
    iteratorThroughIterator(Collections.synchronizedList(arr));
}

III 要約

実はVectorとArrayListはどちらもListの配列ベースの実装で、つまりList陣営に属し、主な違いはスレッドセーフである 主な違いは、基礎となる実装が配列に基づいていることです

Vectorがスレッドセーフを実装する方法は、メソッドに同期ロックをかけることです。 そのため、スレッドセーフな場合はArrayListを、マルチスレッドな場合はVectorを使用します。 Vectorは、主にスレッドセーフを実現するための非効率な方法であるため、今日の開発ではあまり使われていませんが、Javaが同期ロックの効率を改善することがあれば、Vectorはまだ良い選択です。

ArrayListとは異なり Vectorの拡張容量は、現在の容量にcapacityIncrementを加えたもの、または現在の容量の2倍となります。