5.25 Vector

1. What Is It?

A thread-safe List.

2. How to Use It

public class VectorTest
{
    public static void main(String[] args) throws InterruptedException
    {
        Vector<Integer> vector = new Vector<>();
        Thread thread1 = new Thread(() -> {
            for (int i = 0; i < 10000; i++)
            {
                vector.add(i);
            }
        });

        Thread thread2 = new Thread(() -> {
            for (int i = 10000; i < 20000; i++)
            {
                vector.add(i);
            }
        });

        thread1.start();
        thread2.start();

        thread1.join();
        thread2.join();

        assert vector.size() == 20000;

        for (int i = 0; i < 20000; i++)
        {
            assert vector.contains(i);
        }

        vector.remove(2);
        System.out.println(vector.contains(1));//true
        System.out.println(vector.contains(2));//false
    }
}

3. Source-Code Analysis

3.1. UML

It can be seen that Vector is a List, can be cloned, can be serialized, and supports indexed access.

3.2. Constructor

The default initial length is 10. If no explicit increment is specified, expansion doubles the capacity.

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    // Implemented underneath with an Object array.
    protected Object[] elementData;

    // Actual number of elements in the array.
    protected int elementCount;

    // Increment used when growing the array.
    // If 0, capacity doubles.
    protected int capacityIncrement;

    public Vector() {
        // Initial capacity is 10.
        this(10);
    }

    public Vector(int initialCapacity) {
        // 0 means capacity doubles during expansion.
        this(initialCapacity, 0);
    }

    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }
}

3.3. add Method

O(1) without expansion; O(N) when expansion is required.

// synchronized is added.
public synchronized boolean add(E e) {
    modCount++;
    // Ensure enough capacity for the new element.
    ensureCapacityHelper(elementCount + 1);
    // Assign directly.
    elementData[elementCount++] = e;
    return true;
}

3.3.1. synchronized Ensures Thread Safety

This method is declared with synchronized.

public synchronized boolean add(E e) {
    //...
}

3.3.2. Expand When Necessary and Migrate the Old Array

• ensureCapacityHelper

private void ensureCapacityHelper(int minCapacity) {
    // The array capacity is insufficient; expansion is required.
    if (minCapacity - elementData.length > 0)
        // Expand.
        grow(minCapacity);
}

• grow

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // If no increment is specified, double the capacity.
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    // Avoid a capacity that is too small and would require another expansion soon.
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // Avoid an excessively large array causing OOM.
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // Copy the old array's elements into the new array.
    elementData = Arrays.copyOf(elementData, newCapacity);
}

3.3.3. Insert at the End of the Array

// Assign directly.
elementData[elementCount++] = e;

3.4. remove Method [Delete by Index]

• O(N)

public synchronized E remove(int index) {
    modCount++;
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    // Obtain the element at index and return it after deletion.
    E oldValue = elementData(index);

    // Calculate the number of elements to move.
    int numMoved = elementCount - index - 1;
    // Copy all elements after index forward, which effectively deletes index.
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // Set to null so GC can reclaim it.
    elementData[--elementCount] = null; // Let gc do its work

    return oldValue;
}

3.4.1. synchronized Ensures Thread Safety

public synchronized E remove(int index) {
//...
}

3.4.2. Move Elements After the Deleted Element Forward

// Calculate the number of elements to move.
int numMoved = elementCount - index - 1;
// Copy all elements after index forward.
if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index,
                     numMoved);

3.5. contains Method

• O(N)

public boolean contains(Object o) {
    // indexOf is synchronized; if found it returns a non-negative index.
    return indexOf(o, 0) >= 0;
}

• indexOf

public synchronized int indexOf(Object o, int index) {
    // The target is null.
    if (o == null) {
        // Traverse the array.
        for (int i = index ; i < elementCount ; i++)
            if (elementData[i]==null)
                return i;
    // The target is not null.
    } else {
        // Traverse the array.
        for (int i = index ; i < elementCount ; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

3.5.1. synchronized Ensures Thread Safety

public synchronized int indexOf(Object o, int index) {
//...
}

3.5.2. Traverse the Array to Find an Equal Element

for (int i = index ; i < elementCount ; i++)
{
    //...
}

4. Thread-Safety Issue

Individual method calls can be thread-safe, but compound operations cannot necessarily be guaranteed to be thread-safe. For example:

public Object deleteLast(Vector v){
    int lastIndex  = v.size()-1;
    v.remove(lastIndex);
}

This custom deleteLast method is a compound operation composed of size and remove, and it may throw ArrayIndexOutOfBoundsException.

5. References

• Synchronized Containers Such as Vector Are Not Thread-Safe for All Operations - HollisChuang’s Blog