Thread: Which is better Vector<type> or ArrayList ?

As sci4me, Vector is internally "thread-safe" while ArrayList isn't. Personally I wouldn't ever use Vector because there is both too much and too little thread safety with Vector. You'll end up with code which runs slowly, and might not be correct.

It has to deal with how modern computer architectures work, and what optimizations a compiler is allowed to make.

Thread safety only matters if a certain resource can be concurrently accessed from multiple threads. These are shared resources, and a thread-safe program must make sure that the resource is always valid regardless of if it is accessed from one thread or multiple threads. How it does this is beyond the scope here.

For example, consider a simple bank account resource.

A thread could request funds to be transferred from one account to another if and only if the account has enough funds to transfer.

For example, say account 1 has $150.

What would happen if two threads request $100 dollars to be transferred at the same time?

One possible execution path is:

Thread A reads the current value ($150), and decide it is safe to transfer.
Thread B reads the current value ($150), and decides it is safe to transfer.
Thread A subtracts $100 from account 1. account 1 now has $50.
Thread B subtracts $100 from account 1. account 1 now has -$50.

This is just one possible problem which can happen when shared resources aren't properly synchronized. However, synchronizing isn't free. It can be very expensive to force synchronization on every operation (which is basically what Vector does), and doesn't guarantee that a program is synchronized correctly at all.

For example, how would you safely remove every other element in a thread-safe manner? Synchronizing on each individual remove operation doesn't guarantee another thread won't muck with the Vector, changing what elements are removed. On the other-hand, it is also too much synchronization. This operation requires a thread to acquire exclusive access to the vector. At this point the thread can use the much cheaper non-thread-safe remove element because it is guaranteed that no other thread can touch the vector until your thread is done modifying it and releases the lock.

Hence why I don't recommend using Vector ever.

@datathinker read my reply on why not use Vector. It covers why internal synchronization in Vector is a very bad thing. Just because you're using a Vector doesn't mean your program is "thread safe".

An implementation also isn't required to expand an ArrayList by 50% when needed, it is only required to be amortized O(1). I believe there are similar specifications for Vector, but I couldn't find any supporting documentation.

Regardless of whether expanding the capacity by 50% or 100% they are both amortized O(1) and will perform roughly the same. If you know before-hand you will be inserting a large number of elements, pre-allocate a large enough capacity. This will beat all auto-expand strategy in both memory and time complexity.

@Alaa That doesn't affect Vector's thread safety. Vector is internally synchronized, so single operations are Thread-safe. However, the issue is there are no transactional operations like I described above with removing every other element.

// in Thread A
my_vec.add(new Object());
 
// in Thread B
my_vec.add(new Object());

This is perfectly thread safe, even if there is no wrapping synchronized block or any other synchronization methods.

// in Thread A
// remove last element
my_vec.remove(my_vec.size() - 1);
 
// in Thread B
my_vec.remove(0);

This is not synchronized correctly! The problem is there are a total of 2 operations required by Thread A to be done as a single transaction.

Suppose my_vec.size() initially is 5.

Thread A calls my_vec.size(), retrieves 5.
Thread B decides it wants to remove the first element. This is done synchronously as a single step, so the actual size of my_vec is now 4.
Thread A calls my_vec.remove(4). Kaboom! You get an out of range exception because there is no 4th element. The last element is actually at index 3 now.

Fixing this code:

// in Thread A
synchronized(my_vec)
{
    my_vec.remove(my_vec.size() - 1);
}
 
// in Thread B
synchronized(my_vec)
{
    my_vec.remove(0);
}

This is perfectly fine, until you realize that Thread A had to acquire 3 locks just to remove the last element. Additionally, every other Thread must now at a minimum acquire 2 locks to do any operation. Technically if Vector internally uses synchronized(this) you could get away without the synchronized block in thread B, but as far as I can tell there's no guarantees on what type of locking Vector provides so this is a very bad thing to rely on. This is an example of too much synchronization.

@AndrewR

Luckily for you, there's not much learning involved. The two classes implement the same interfaces so you can call the same methods and expect basically the same results. Simply declare your variables as ArrayList and you're good