Reasons Why Certain Sets Are Unsafe

In the context of the Java Collections Framework, when a collection is described as "unsafe," it specifically refers to

In the context of the Java Collections Framework, when a collection is described as "unsafe," it specifically refers to thread-unsafety. This means that if multiple threads access a single collection instance concurrently—and at least one of those threads modifies the collection—the internal state of the object can become corrupted. Such corruption manifests as data loss, inconsistent results, unexpected exceptions, or in extreme cases, infinite loops that freeze the CPU.

To achieve true thread safety, a data structure must generally guarantee three properties:

  • Atomicity: A set of operations must be executed as a single, indivisible unit. Either the entire sequence completes, or none of it does, ensuring that no other thread sees a partial or intermediate state.
  • Visibility: Changes made to a shared variable by one thread must be immediately and reliably visible to other threads.
  • Ordering: The execution order of instructions must remain predictable, preventing the compiler or CPU from reordering operations in a way that leads to unexpected behavior.

Most standard collections—such as ArrayList, LinkedList, HashMap, HashSet, and TreeMap—are designed without internal synchronization mechanisms. Consequently, they cannot guarantee these three properties under concurrent access.
It is important to understand that the lack of thread safety in standard collections is not a "bug" or an oversight. Rather, it is a deliberate design choice. By omitting synchronization, these collections offer significantly better performance and lower overhead for the vast majority of use cases, which are single-threaded.

The technical reasons for their unsafety can be categorized as follows:

1. Absence of Synchronization Controls

Standard collections do not employ concurrency primitives like synchronized blocks, Lock objects, or CAS (Compare-And-Swap) operations. Without these guards, multiple threads can enter the same method simultaneously and modify internal fields—such as the size counter, array references, or linked-list pointers—at the same time.

2. Non-Atomic Internal Operations

Many methods that appear to be a single action are actually composed of several discrete steps. For example, adding an element to an ArrayList typically involves:

  1. Checking if the current capacity is sufficient.
  2. Expanding the internal array if necessary.
  3. Writing the element into the array.
  4. Incrementing the size variable.

If a thread switch occurs between these steps, two threads might read the same size value and attempt to write their respective elements into the same array index. This results in one element being overwritten and the final size of the collection being lower than expected.

3. The "Check-Then-Act" Race Condition

Even if individual methods were synchronized, "composite operations" remain dangerous. A common pattern is the "check-then-act" sequence:

if (!map.containsKey(key)) {
    map.put(key, value);
}

In a concurrent environment, two threads could both check containsKey(key) and find it returns false before either has called put(). Both threads would then proceed to insert the value, leading to redundant writes or the accidental overwriting of data.

4. Iterator Conflicts and Fail-Fast Mechanisms

Standard collection iterators use a fail-fast mechanism. They track a modification count (modCount); if the collection is structurally modified (elements added or removed) while a thread is iterating through it, the iterator throws a ConcurrentModificationException.

It is crucial to note that fail-fast is a detection mechanism, not a safety guarantee. It does not prevent data corruption; it simply attempts to alert the developer that the collection was modified illegally during iteration.

5. Memory Visibility Issues

Standard collections do not establish a "happens-before" relationship between threads. Because they lack volatile fields or synchronized blocks for their internal storage, a value written by Thread A may remain in a CPU cache and not be flushed to main memory. Thread B might then read a stale or null value, even if Thread A has technically already completed the write operation.

6. Structural Hazards during Resizing

The most severe issues often occur during capacity expansion (resizing) or rehashing. These processes involve creating a new internal array and migrating all existing elements. If multiple threads trigger a resize simultaneously, the internal pointers can become corrupted. In older versions of HashMap, this could lead to the creation of a circular linked list, causing any subsequent get() call to enter an infinite loop and spike CPU usage to 100%.

A Practical Example: Concurrent ArrayList Writes

The following example demonstrates how concurrent modifications can lead to unpredictable results in an ArrayList.

import java.util.ArrayList;
import java.util.List;

public class UnsafeDemo {
    public static void main(String[] args) throws InterruptedException {
        List<Integer> list = new ArrayList<>();

        Runnable task = () -> {
            for (int i = 0; i < 1000; i++) {
                list.add(i);
            }
        };

        Thread t1 = new Thread(task);
        Thread t2 = new Thread(task);

        t1.start();
        t2.start();
        t1.join();
        t2.join();

        System.out.println("Final size: " + list.size());
    }
}

In a thread-safe environment, the final size should be exactly 2,000. However, in practice, this code often prints a number less than 2,000 or throws an ArrayIndexOutOfBoundsException. This happens because the internal size update and the array boundary check are not atomic.

Strategies for Achieving Thread Safety

Depending on the performance requirements and access patterns, Java provides several alternatives to standard collections:

  • Synchronized Wrappers: Methods like Collections.synchronizedList wrap a standard collection and synchronize every individual method. While safe for single calls, composite operations still require manual synchronization on the collection object.
  • Concurrent Collections: Classes in the java.util.concurrent package, such as ConcurrentHashMap and CopyOnWriteArrayList, use sophisticated techniques like lock striping, CAS, and copy-on-write to provide high concurrency with minimal contention.
  • Blocking Queues: ArrayBlockingQueue and LinkedBlockingQueue are designed for producer-consumer patterns, providing built-in mechanisms to block threads when the queue is full or empty.
  • Immutable Collections: Using List.of() or Map.of() creates collections that cannot be modified after creation. Since their state never changes, they are inherently thread-safe.

Decision Framework for Collection Selection

When choosing a collection for a multi-threaded application, consider the following logic:

  1. Single-threaded or Thread-confined? $\rightarrow$ Use standard collections (ArrayList, HashMap) for maximum performance.
  2. Read-heavy with rare writes? $\rightarrow$ Use CopyOnWriteArrayList or Immutable collections.
  3. High-concurrency read/write of key-value pairs? $\rightarrow$ Use ConcurrentHashMap.
  4. Passing data between threads (Producer/Consumer)? $\rightarrow$ Use BlockingQueue.
  5. Need atomic composite operations? $\rightarrow$ Use the atomic methods provided by concurrent collections (e.g., putIfAbsent) or implement explicit locking.

Summary

The "unsafety" of certain collections stems from a design philosophy that prioritizes efficiency over synchronization. By omitting the guarantees of atomicity, visibility, and ordering, standard collections avoid the performance penalties of locking. However, this places the responsibility on the developer to ensure that shared mutable state is managed correctly, either by choosing a concurrent implementation or by implementing external synchronization.