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)

How to avoid thread collision using Locks in java?

Each of the method discussed here  has some advantages and disadvantages.  Here we will see the java.util.concurrent.locks  package.

java.util.concurrent.locks package:

The java API says this packages as, 'Interfaces and classes providing a framework for locking and waiting for conditions that is distinct from built-in synchronization and monitors.'

This package has the following main classes.

• AbstractOwnableSynchronizer
  
• AbstractQueuedLongSynchronizer
  
• AbstractQueuedSynchronizer
  
• LockSupport
  
• ReentrantLock
  
• ReentrantReadWriteLock
  
• ReentrantReadWriteLock.ReadLock
  
• ReentrantReadWriteLock.WriteLock

Example

Remember the race condition example, which we discussed earlier. The same program with ReentrantLock, will solves the race condition. Please see the below code.

package thread;

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * @author Sivaranjani D
 * 
 */
public class AccountOverDraw{

 public static void main(String[] args) {
  Runnable atm = new ATM();
  Thread withdrwer1 = new Thread(atm);
  withdrwer1.setName("withdrawer1");
  withdrwer1.start();

  Thread withdrwer2 = new Thread(atm);
  withdrwer2.setName("withdrawer2");
  withdrwer2.start();
 }

}

class Account {
 int balance = 500;

 public void debit(int amount) {
  balance = balance - amount;
 }

 public void credit(int amount) {
  balance = balance + amount;
 }

 public int getBalance() {
  return balance;
 }
}

class ATM implements Runnable {
 Account account = new Account();
 Lock lock = new ReentrantLock();
 public void run() {
   for (int i = 0; i <10; i++) {
    lock.lock();
   if (account.getBalance() > 0) {
    makeWithdrawal(100);
   } else {
    System.out.println("Not enough in amount for "
      + Thread.currentThread().getName() + " to withdraw ");
   }
   lock.unlock();
  } 
 }

 private  void makeWithdrawal(int amt) {
  if (account.getBalance() >= amt) {
   System.out.println(Thread.currentThread().getName()
     + " cheked balance and the balance is :"
     + account.getBalance());

   account.debit(amt);
   System.out.println(Thread.currentThread().getName()
     + " completes the withdrawal and the balance: "
     + account.getBalance());
  }
 }

}

Explanation:

1. The only difference which avoids race condition is, here the atomic statements are wrapped inside the lock and unlock.
   
2. This step ensures that both the statements can be accessed by only one thread at a time. Also if one thread does balance check it does the debit as well before the other thread reads the balance.

Example of race condition in java multithreading

Race Condition:

Race condition occurs, when 2 or more threads try to access the shared data of same program and try to change it.  In java, the shared data may be the instance variables because for method variables, each thread has it's own copy.

Example:

package thread;

/**
 * @author Sivaranjani D
 * 
 */
public class MultiThreadsDanger {

	public static void main(String[] args) {
		Runnable atm = new ATM();
		Thread withdrwer1 = new Thread(atm);
		withdrwer1.setName("withdrawer1");
		withdrwer1.start();

		Thread withdrwer2 = new Thread(atm);
		withdrwer2.setName("withdrawer2");
		withdrwer2.start();
	}

}

class Account {
	int balance = 500;

	public void debit(int amount) {
		balance = balance - amount;
	}

	public void credit(int amount) {
		balance = balance + amount;
	}

	public int getBalance() {
		return balance;
	}
}

class ATM implements Runnable {
	Account account = new Account();

	public void run() {
		for (int i = 0; i < 5; i++) { 			if (account.getBalance() > 0) {
				makeWithdrawal(100);
			} else {
				System.out.println("Not enough in amount for "
						+ Thread.currentThread().getName() + " to withdraw ");
			}

		}
	}

	private void makeWithdrawal(int amt) {
		if (account.getBalance() >= amt) {
			System.out.println(Thread.currentThread().getName()
					+ " cheked balance and the balance is :"
					+ account.getBalance());

			account.debit(amt);
			System.out.println(Thread.currentThread().getName()
					+ " completes the withdrawal and the balance: "
					+ account.getBalance());
		}
	}

}

Output
withdrawer1 cheked balance and the balance is :500
withdrawer1 completes the withdrawal and the balance: 400
withdrawer2 cheked balance and the balance is :400
withdrawer2 completes the withdrawal and the balance: 300
withdrawer2 cheked balance and the balance is :300
withdrawer2 completes the withdrawal and the balance: 200
withdrawer2 cheked balance and the balance is :200
withdrawer2 completes the withdrawal and the balance: 100
withdrawer2 cheked balance and the balance is :100
withdrawer2 completes the withdrawal and the balance: 0
Not enough in amount for withdrawer2 to withdraw
Not enough in amount for withdrawer2 to withdraw
Not enough in amount for withdrawer2 to withdraw
Not enough in amount for withdrawer2 to withdraw
Not enough in amount for withdrawer2 to withdraw
Not enough in amount for withdrawer2 to withdraw
withdrawer1 cheked balance and the balance is :400
withdrawer1 completes the withdrawal and the balance: -100
Not enough in amount for withdrawer1 to withdraw
Not enough in amount for withdrawer1 to withdraw
Not enough in amount for withdrawer1 to withdraw
Not enough in amount for withdrawer1 to withdraw
Not enough in amount for withdrawer1 to withdraw
Not enough in amount for withdrawer1 to withdraw
Not enough in amount for withdrawer1 to withdraw
Not enough in amount for withdrawer1 to withdraw

Explanation:

1. The file has an account class, which has some methods to credit, debit and get balance


2. There is a ATM class which implements runnable. This ATM has the account and it's run method has the provision to call withdrawal method


3. In the main class, we have created 2 threads by passing the same ATM object. So both the threads are considered as a 2 with-drawers . Both the threads now calls the run method of same ATM object and both the threads runs in the same run block.


4. Even though we are doing the balance check in the above program, the output shows -100. How this is happening??


5. The reason is, the atomic operations are not accessed by a single thread. In the above program atomic operation is, checking the balance and debit (inside withdrawal method). For example, consider the account has a balance of 100. And think now the first thread is doing the balance check. That means it executes the line if (account.getBalance() >= amt) . Now it succeeds in this line because we have 100 as balance and the amt to be debited is also 100. So next it will call the account.debit(amt); But as we know thread scheduler may stop this thread before executing the debit step and save it's state. Now, the second thread comes and it does the same first step. This also succeeds,  because still the first thread has not debited. so the second thread also calls the second statement. It debits the amount and balance will becomes zero. Since the second thread finished its job it will die. Now the thread scheduler may again resumes the first thread, which was stopped after balance check. So now the first thread starts from where it paused. That means it start with the debit. So now we will get the -100 as output.

This situation is called as race condition.

How to avoid thread collision using AtomicInteger java?

Each of the method discussed here  has some advantages and disadvantages.  Here we will see the java.util.concurrent.atomic package.

java.util.concurrent.atomic package:

This package has the following classes. The API says this package as, "A small toolkit of classes that support lock-free thread-safe programming on single variables."

• AtomicBoolean


• AtomicInteger


• AtomicIntegerArray


• AtomicIntegerFieldUpdater<T>


• AtomicLong


• AtomicLongArray


• AtomicLongFieldUpdater<T>


• AtomicMarkableReference<V>


• AtomicReference<V>


• AtomicReferenceArray<E>


• AtomicReferenceFieldUpdater<T,V>


• AtomicStampedReference<V>

Advantages:

Using these classes thread does not require lock on the object. This avoids the waiting time to get the lock. (Locks will be explained further)

Disadvantages:

These classes can be used with only variables, but not with the classes or methods.

I will discuss about the AtomicInteger class here.

AtomicInteger:

AtomicInteger class has some thread safe methods by which it ensures that atomic operations will be executed by a single thread only.
Please see the below program for better understanding.

package thread;

import java.util.concurrent.atomic.AtomicInteger;

/**
 * @author Sivaranjani D
 * 
 */
public class AtomicIntegerExample {
	public static void main(String args[]) {

		Incrementer job = new Incrementer();
		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.getIncerementedNumber());
		System.out.println("Atomic " + job.getIncerementedAtomicNumber());
	}
}

class Incrementer implements Runnable {
	AtomicInteger atomicnumber = new AtomicInteger();
	int normalnumber = 0;

	public void run() {
		for (int i = 0; i < 50; i++) {
			increment();
			incrementAtomicNumber();
		}
	}

	public int getIncerementedNumber() {
		return normalnumber;
	}

	public void increment() {
		try {
			Thread.sleep(100);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
		normalnumber++;
	}

	public AtomicInteger getIncerementedAtomicNumber() {
		return atomicnumber;
	}

	public void incrementAtomicNumber() {
		try {
			Thread.sleep(50);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
		atomicnumber.addAndGet(1);

	}
}

Explanation:

1. Incrementer class implements Runnable and it has 2 fields namely normalnumber  of type int and a atomicnumber of type AtomicInteger .
   


2. There are 2 methods namely increment which increments the normalnumber  and incrementAtomicNumber which increments the atomicnumber 


3. And we are calling the above 2 methods in the run method of Incrementer for 50 times .


4. We are creating 2 threads in the AtomicIntegerExample  class by passing the above Incrementer c lass Object.


5. Now both the threads should execute the run method of Incrementer class and loops it for 50 times.


6. Since we made t1.join() and t2.join(), main Thread will waits on the both the thread


7. After both the threads complets, main thread will print the value.


8. The output will be always 50 for the atomicnumber , but when you take the normalnumber it is not. That is because, AtomicInteger does the following 3 tasks (atomic) in a single block but normalnumber does not.

• Read the old value of normalnumber


• Increment the normalnumber


• Reassign the incremented value to normalnumber

What is Thread collision and how to avoid it in java?

What is Thread Collision?

In a multi-threaded environment, multiple threads will be running in the same method/block of the program. This is called thread collision and it can cause significant effect in the program.  Thread collision leads to race condition.

For example, considered the below program.
The program has a class named ThreadIncrementer ,which implements the Runnable interface. It's run method increments numbers from 1 to 50; And we have created 3 Threads by passing the  runnable object. So each threads will be running the same run method of the ThreadIncrementer class.

Code:

package thread.assignment;

/**
 * @author Sivaranjani D
 * 
 */
public class ThreadIntor {
	public static void main(String[] args) throws InterruptedException {
		ThreadIncrementer threadIncrementer = new ThreadIncrementer();
		Thread t1 = new Thread(threadIncrementer);
		Thread t2 = new Thread(threadIncrementer);
		Thread t3 = new Thread(threadIncrementer);
		t1.start();
		t2.start();
		t3.start();

		t1.join();
		t2.join();
		t3.join();
		System.out.println(threadIncrementer.normalnumber);
	}

}

class ThreadIncrementer implements Runnable {
	int normalnumber = 0;

	public void run() {
		for (int i = 0; i < 50; i++) {
			try {
				Thread.sleep(10);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
			normalnumber++;
		}
	}
}

Output:
142

The expected output for the above program should be 150. Because the loop will increment normalnumber for 50 and there are 3 threads running. So 3*50 = 150.
But, you don't get the same 150 all the time. That is because of multiple threads collision in the same block.

How Thread collision creates the above problem?

In the above example, take a look at the code normalnumber++. This might look like a single line of code. But it is not.
Generally there are 3 tasks happens inside.

1. Read the old value of normalnumber


2. Increment the normalnumber


3. Reassign the incremented value to normalnumber

Consider now, there 2 threads coming into the block to increment normalnumber. And consider the old value of normalnumber is 5

• The first thread performs the step 1, and reads the value of normalnumber as 5 and goes to the step 2.


• Before the first thread increments the value, the second thread also reads the old value of normalnumber as 5.


• Now, consider the first thread incremented normalnumber to 6 and reassigned the value


• But since Second Thread also has read the same old value as 5, it will also does the same job what First Thread does.


• Now we are missing one increment. After 2 increment the value of normalnumber should be 7. Instead we are getting only 6.

In the above program, it may not look serious. But think about the account overdraw by 2 threads, which is a serious issues.

So please make design consideration and follow the below ways to avoid collision in the multi-threaded environment.

Different ways to avoid thread collision:

• Using Atomic Wrapper classes from java.util.concurrent.atomic package


• 
  
  Using locks from java.util.concurrent.locks package.


• 
  
  Using thread safe classes provided by java API


• 
  
  Using Volatile keyword


• 
  
  Using Synchronization keyword