Set, Map in collection allows duplicates ?

Collections in java

If you already knows about collection framework, this blog's title will be a real surprise for you. Because in Collection framework Set does not accept any duplicate value and Map does not take any duplicate key.
But See the below program.

Example:

import java.util.HashSet;
import java.util.Set;

/**
 * @author Sivaranjani D
 * 
 */

public class ThreadSafeCheck {
	public static void main(String[] args) {
		SyncList job = new SyncList();
		Thread t1 = new Thread(job);
		Thread t2 = new Thread(job);
		t1.start();
		t2.start();
		try {
			t1.join();
			t2.join();
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
		System.out.println("Normal :" + job.set.size());
	}
}
class SyncList implements Runnable {
	Set set = new HashSet();
	public void run() {
		addNormalMap();
	}
	private void addNormalMap() {
		for (int i = 0; i < 50; i++) {
			set.add(i);
		}
	}
}

Output:

Normal :63

Explanation:

The above program shows that, Set allows duplicates. Because in the above program we are adding same numbers from 1to 50 inside the set. And 2 threads are running the same loop. So it tries to add each values 2 times. But since Set does not allow duplicates, the size should be always 50 even though there are 100 values inserted into the set. But we are not getting the size as 50 always. What is the reason?

This is same as what we discussed already in our previous posts. The atomic operations are not executed by a single thread at a time.

The internal implementation of set, always check for the value's existence before inserting. If it already exists it does not add the same value again. But when we are running the same code in multi-threaded environment, the atomic operations may not be executed in a proper way.

For example,

1. Consider that the first thread is trying to add value 40 into the set


2. So the first thread check for the value's existence in the set. But initially It will not be there so it can add the value. But think at this situation, thread scheduler  preempted the first thread before it insert the value and resumes the second thread.


3. Now consider that the Second thread also trying to add the same number 40. So here also the value is checked for it's existence. And the check will succeed because, the previous thread is paused before it inserts 40. So second thread will insert the value (40) into set.


4. Now assume that the second thread is preempted and thread scheduler, selects the first thread. So First thread resumes from where it left. So it adds the same number again which created the duplicate in the set. (The thread does not check for the values presence at this time, because already it did once)