Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Thread-Safe Concatenation

Problem Statement

Write a Java program that implements a multi-threaded application using StringBuffer to append strings concurrently from multiple threads, ensuring thread safety. The program should allow multiple threads to append strings to a shared StringBuffer and verify that the resulting string is correct, demonstrating thread safety. Test the implementation with various scenarios, including different numbers of threads, varying string lengths, and edge cases like empty strings. You can visualize this as a team of workers adding their notes to a shared, synchronized logbook, ensuring that no notes are lost or jumbled even when everyone writes at the same time.

Input: A set of strings to be appended by multiple threads (e.g., ["thread1", "thread2", "thread3"]). Output: A single string containing all appended strings in the order of thread execution (e.g., "thread1thread2thread3") and verification of correctness. Constraints:

  • Number of threads is between 1 and 100.
  • Each string contains printable ASCII characters and may be empty.
  • The input strings may be null (handled by skipping or appending a default value). Example:
  • Input: 3 threads appending "thread1", "thread2", "thread3".
  • Output: "thread1thread2thread3" (order may vary due to thread scheduling).
  • Explanation: Each thread appends its string to a shared StringBuffer, and the result is consistent due to StringBuffer’s thread-safe methods.
  • Input: 2 threads appending "", "".
  • Output: ""
  • Explanation: Empty strings result in an empty final string.

Pseudocode

FUNCTION appendString(buffer, str)
    IF str is not null THEN
        CALL buffer.append(str)
    ENDIF
ENDFUNCTION

FUNCTION threadSafeConcatenation(strings, numThreads)
    IF strings is null OR numThreads <= 0 THEN
        RETURN null
    ENDIF
    CREATE sharedBuffer as new StringBuffer
    CREATE threadList as empty list
    FOR i from 0 to numThreads - 1
        CREATE thread that calls appendString(sharedBuffer, strings[i])
        ADD thread to threadList
    ENDFOR
    FOR each thread in threadList
        START thread
    ENDFOR
    FOR each thread in threadList
        JOIN thread
    ENDFOR
    RETURN sharedBuffer as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of (strings, numThreads) pairs
    FOR each (strings, numThreads) in testCases
        PRINT test case details
        CALL threadSafeConcatenation(strings, numThreads)
        PRINT resulting string
        VERIFY result correctness
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define a method appendString that safely appends a string to a shared StringBuffer.
  2. Define a method threadSafeConcatenation: a. Check for null input or invalid thread count; return null if invalid. b. Create a shared StringBuffer. c. Create and start threads, each calling appendString with a string. d. Wait for all threads to complete using join. e. Return the final concatenated string.
  3. Verify thread safety by checking if the result contains all input strings in any order (since thread scheduling is non-deterministic).
  4. In the main method, test with different numbers of threads, string lengths, and edge cases (e.g., empty strings, single thread), printing the input, output, and verification results.

Java Implementation

import java.util.ArrayList;

public class ThreadSafeConcatenation {
    // Appends a string to the shared StringBuffer
    private void appendString(StringBuffer buffer, String str) {
        if (str != null) {
            buffer.append(str);
        }
    }

    // Performs thread-safe concatenation using multiple threads
    public String threadSafeConcatenation(String[] strings, int numThreads) {
        if (strings == null || numThreads <= 0 || numThreads > strings.length) {
            return null;
        }
        StringBuffer sharedBuffer = new StringBuffer();
        ArrayList<Thread> threadList = new ArrayList<>();
        
        // Create threads
        for (int i = 0; i < numThreads; i++) {
            final String str = strings[i];
            Thread thread = new Thread(() -> appendString(sharedBuffer, str));
            threadList.add(thread);
        }
        
        // Start all threads
        for (Thread thread : threadList) {
            thread.start();
        }
        
        // Wait for all threads to complete
        for (Thread thread : threadList) {
            try {
                thread.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        
        return sharedBuffer.toString();
    }

    // Main method to test thread-safe concatenation
    public static void main(String[] args) {
        ThreadSafeConcatenation concatenator = new ThreadSafeConcatenation();

        // Test cases
        Object[][] testCases = {
            {new String[]{"thread1", "thread2", "thread3"}, 3}, // Multiple threads
            {new String[]{"", ""}, 2},                         // Empty strings
            {new String[]{"solo"}, 1},                        // Single thread
            {generateLargeStrings(10), 10},                   // Large input
            {new String[]{null, "test", null}, 3},            // Null elements
            {null, 1}                                         // Null input
        };

        for (int i = 0; i < testCases.length; i++) {
            String[] strings = (String[]) testCases[i][0];
            int numThreads = (int) testCases[i][1];
            System.out.println("Test case " + (i + 1) + ":");
            System.out.print("Input strings: [");
            if (strings != null) {
                for (int j = 0; j < numThreads && j < strings.length; j++) {
                    System.out.print(strings[j] != null ? "\"" + strings[j] + "\"" : "null");
                    if (j < numThreads - 1 && j < strings.length - 1) {
                        System.out.print(", ");
                    }
                }
            } else {
                System.out.print("null");
            }
            System.out.println("]");
            System.out.println("Number of threads: " + numThreads);
            String result = concatenator.threadSafeConcatenation(strings, numThreads);
            System.out.println("Concatenated result: \"" + (result != null && result.length() > 50 ? result.substring(0, 50) + "..." : result) + "\"");
            // Verify correctness
            if (strings != null && result != null) {
                StringBuilder expected = new StringBuilder();
                for (int j = 0; j < numThreads && j < strings.length; j++) {
                    if (strings[j] != null) {
                        expected.append(strings[j]);
                    }
                }
                System.out.println("Verification: " + (result.length() == expected.length() ? "Correct (length matches expected)" : "Incorrect"));
            } else {
                System.out.println("Verification: " + (result == null ? "Correct (null expected)" : "Incorrect"));
            }
            System.out.println();
        }
    }

    // Helper method to generate large strings for testing
    private static String[] generateLargeStrings(int size) {
        String[] largeStrings = new String[size];
        for (int i = 0; i < size; i++) {
            largeStrings[i] = "str" + i;
        }
        return largeStrings;
    }
}

Output

Running the main method produces (note: order of strings in the result may vary due to thread scheduling):

Test case 1:
Input strings: ["thread1", "thread2", "thread3"]
Number of threads: 3
Concatenated result: "thread1thread2thread3"
Verification: Correct (length matches expected)

Test case 2:
Input strings: ["", ""]
Number of threads: 2
Concatenated result: ""
Verification: Correct (length matches expected)

Test case 3:
Input strings: ["solo"]
Number of threads: 1
Concatenated result: "solo"
Verification: Correct (length matches expected)

Test case 4:
Input strings: ["str0", "str1", "str2", ..., "str9"]
Number of threads: 10
Concatenated result: "str0str1str2str3str4str5str6str7str8str9"
Verification: Correct (length matches expected)

Test case 5:
Input strings: [null, "test", null]
Number of threads: 3
Concatenated result: "test"
Verification: Correct (length matches expected)

Test case 6:
Input strings: [null]
Number of threads: 1
Concatenated result: "null"
Verification: Correct (null expected)

Explanation:

  • Test case 1: Three threads append "thread1", "thread2", "thread3"; result is correct (order may vary).
  • Test case 2: Two threads append empty strings; result is empty.
  • Test case 3: One thread appends "solo"; result is "solo".
  • Test case 4: Ten threads append "str0" to "str9"; result contains all strings.
  • Test case 5: Three threads, with nulls skipped, append "test"; result is "test".
  • Test case 6: Null input returns null.

How It Works

  • StringBuffer: Thread-safe due to synchronized methods, ensuring safe concurrent appends.
  • appendString: Appends a non-null string to the shared StringBuffer.
  • threadSafeConcatenation:
    • Creates a shared StringBuffer.
    • Spawns threads, each appending a string.
    • Waits for all threads to finish using join.
    • Returns the concatenated string.
  • Verification: Checks if the result’s length matches the sum of non-null input string lengths.
  • Example Trace (Test case 1):
    • Initialize: sharedBuffer = "".
    • Thread 1 appends "thread1" → sharedBuffer = "thread1".
    • Thread 2 appends "thread2" → sharedBuffer = "thread1thread2".
    • Thread 3 appends "thread3" → sharedBuffer = "thread1thread2thread3".
  • Main Method: Tests with multiple threads, empty strings, single thread, large inputs, and null cases, verifying thread safety.
  • Thread Safety: StringBuffer’s synchronized append method ensures no data corruption.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
Append (per thread)O(m)O(m)
Full AlgorithmO(n * m)O(n * m)

Note:

  • n is the number of threads, m is the average length of each string.
  • Time complexity: O(m) per append operation; O(n * m) for all threads (though concurrent execution may reduce wall-clock time).
  • Space complexity: O(n * m) for the StringBuffer storing all concatenated strings.
  • Worst case: O(n * m) time and space when all strings are long and non-null.

✅ Tip: Use StringBuffer for thread-safe string concatenation in multi-threaded environments. Test with multiple threads and varying string lengths to confirm thread safety.

⚠ Warning: Ensure proper thread synchronization using join to avoid accessing the StringBuffer before all appends complete. Check for null inputs to prevent unexpected behavior.