HastSet thread safe

Question

===update====

from comment

so I clearly read the doc and know it's not thread safe and I wanted to run a small experiment to see how it will break. So the doc says the result is non deterministic. Does anyone know what could happen? If I want to prove it's not thread safe how can I write a sample code so that I can actually see that it's no thread safe? Have you guys actually tried and seen not working example? Do you have sample code?

If I have three threads accessing the hashset of string.

• One adding a new string
• Second removing the string
• Third removing all

Is the HashSet thread safe?

public void test()
{
    Set<String> test = new HashSet<>();
    Thread t0= new Thread(new Runnable() {
        @Override
        public void run() {
            while (true) {
                boolean c = test.contains("test");
                System.out.println("checking " + c);
                try {
                    Thread.sleep(50);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    });
    Thread t1 = new Thread(new Runnable() {
        @Override
        public void run() {
            while (true) {
                test.add("test");
                System.out.println("adding");
                try {
                    Thread.sleep(50);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    });
    Thread t2 = new Thread(new Runnable() {
        @Override
        public void run() {
            while (true) {
                if (!test.isEmpty())
                {
                    test.removeAll(test);
                }
                System.out.println("removing");
                try {
                    Thread.sleep(500);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }

        }
    });
    t0.start();
    t1.start();
    t2.start();

    while(true) {

    }
}

I have this test code and ran it and it seems working. No exceptions were thrown. I was little confused because HashSet is not thread-safe. Whay am I missing?

Answer 1

From comment:

so I clearly read the doc and know it's not thread safe and I wanted to run a small experiment to see how it will break. So the doc says the result is non deterministic. does anyone know what could happen? If I want to prove it's not thread how cam I write a sample code so that I can actually see that it's no thread safe? Have you guys actually tried and seen that not working example? do you have sample code?

The problem is that updating the Set may not be an atomic operation, especially not when the internal hash table needs to be re-sized.

If two threads are updating at the same time, you may get the simple result that one thread overrides the change by the other thread, so you lose a change. More seriously, the conflict may corrupt the internal structure of the Set.

To show this, here is a small program that causes high conflict during add of values. All values added are distinct, so they should all be added, but you will see that size of the Set is incorrect when program is done, proving that some added values got lost.

final int THREAD_COUNT = 10;
final int NUMS_TO_ADD = 100000;
Set<Integer> set = new HashSet<>();
Thread[] threads = new Thread[THREAD_COUNT];
for (int i = 0; i < THREAD_COUNT; i++) {
    final int threadNo = i;
    threads[i] = new Thread() {
        @Override public void run() {
            for (int j = 0; j < NUMS_TO_ADD; j++)
                set.add(j * THREAD_COUNT + threadNo); // all distinct values
        }
    };
    threads[i].start();
}
for (int i = 0; i < threads.length; i++)
    threads[i].join();
System.out.println("Found " + set.size() + " values, expected " + THREAD_COUNT * NUMS_TO_ADD);

Each time you run it, you will get a different result, e.g.

Found 898070 values, expected 1000000

Found 825773 values, expected 1000000

Found 731886 values, expected 1000000

Exception in thread "Thread-7" java.lang.ClassCastException: java.base/java.util.HashMap$Node cannot be cast to java.base/java.util.HashMap$TreeNode
    at java.base/java.util.HashMap$TreeNode.moveRootToFront(HashMap.java:1883)
    at java.base/java.util.HashMap$TreeNode.putTreeVal(HashMap.java:2063)
    at java.base/java.util.HashMap.putVal(HashMap.java:638)
    at java.base/java.util.HashMap.put(HashMap.java:612)
    at java.base/java.util.HashSet.add(HashSet.java:220)
    at Test$1.run(Test.java:16)

Or the program simply hangs!

Answer 2

Thread Safe

Thread unsafe does not mean you can not use it in multi-treads or the program will throw exceptions. It means you can not always get what you want when program is executed in multi threads. See this for more.

In computer programming, thread-safe describes a program portion or routine that can be called from multiple programming threads without unwanted interaction between the threads.

And, you can not say an object is thread safe even if you get the expected experiment results. Because the results may vary in different environments. You should use synchronization mechanism provided by JDK.

HashSet

HashSet is not thread safe, this means:

• If you write an object into it, this object may not be visible to other threads.
• If you read the set from different threads at same time, they may get different results.
• If you call add first, then call removeAll, the objects in this set may not be removed.
• ......

User Andreas's example is pretty clear. Since HashSet is based on HashMap's key set, you can refer this How to prove that HashMap in java is not thread-safe.

Solution

JDK provided a thread safe version set, all operations on the set need aquire a inner monitor lock first.

Set s = Collections.synchronizedSet(new HashSet(...));

---