Open Source For Geeks: January 2019

Sunday, 27 January 2019

Sorting Techniques

Background

This post summarises various sorting techniques.

Sorting Techniques

I have written posts over time to show the implementation of some of the sorting techniques. Following are links to the same -

What is transient keyword in Java?

Background

In one of my earlier post, I had covered what serialization in Java is and how transient keyword can be used in that context. You can take a look at that post -

Serialization in Java

We saw that in serialization context, instance variables marked as transient will not be serialized and on deserialization, they get the default values. In this post, we will see some more details about transient keyword with an example.

Transient use cases

The transient keyword should be used when you do not want to serialize your instance variables. Eg.

An instance of Logger class. There is no state associated with a logger instance, so we do not need to serialize it.
Similarly, any secure data like passwords, which you may not want to serialize.

You cannot use any classes in the JDK that does not implement Serializable as references in your class that is Serializable. It needs to be marked transient. Else it will throw “java.io.NotSerializableException” exception.

The transient and final keyword

Transient treats final keyword a bit differently. So let's take an example to understand this,

//final field 1
public final transient String myName = "Aniket";
//final field 2
public final transient Logger myLogger = LoggerFactory.getLogger(MyClass.class.getName());

If you consider above fields in a class, by our above logic they should not be serialized since they are marked as transient. However, if any final variable is evaluated as a "constant expression" like in case of myName above, it will be serialized. So in above case myName is serialized and myLogger is not.

On the side note, recall serialVersionUID which is static and final. It is the only static variable that gets serialized. static instances do not form the state of the object, so by very definition of serialization, it is not serialized.

Use of transient keyword in HashMap.

If you see HashMap implementation you can see the array that backs it is marked as transient.

      /**
      * The table, resized as necessary. Length MUST Always be a power of two.
  */
      transient Entry[] table;

If this array is not serialized, how does it get deserialized back to restore instance state? Class does implement serializable -

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
 
 
    private static final long serialVersionUID = 362498820763181265L;

Reason for this is that two instances of same class do not generate the same hashcode (unless of course, you override the hashcode method to do so). The native implementation uses the objects memory location which will be different for the object before serialization and after deserialization. So it is not guaranteed that the objects will be in the same bucket and in the same location as that of hashmap that was serialized. This is why the array itself is not serialized by marking it as transient. So how is the instance state restored?

For this in HashMap implementation, they override writeObject and readObject method. In the writeObject method, all entries from the entry array are read in a sequence and serialized. Similarly, in readObject for deserialization, it is read in the same order and then stored in its own internal entry table array. So the buckets and position are dynamically calculated during deserialization with the same data.

PS: This is a good interview question :)

Saturday, 19 January 2019

How to print odd and even numbers in order with two threads

Background

Let us say you have two threads - one thread prints even numbers and other one prints odd numbers. You need to design this in such a way that all the numbers are printed in the natural order i.e 1,2,3,4 etc.

This is more of a synchronization questions rather than a data structure question. You need to understand how threads, synchronization works in order to be able to solve this question.

How to print odd and even numbers in order with two threads

We can do this two ways -

Using Sempahores
Using wait and notify

Let us see how we can do this using semaphores -

public static void withSemaphores() throws InterruptedException, ExecutionException {
 
 Semaphore oddLock = new Semaphore(1);
 Semaphore evenLock = new Semaphore(0);
 
 Runnable printOdd = () -> {
  for (int i = 1; i < 10; i = i + 2) {
   try {
    oddLock.acquire();
   } catch (Exception e) {
    // TODO Auto-generated catch block
    e.printStackTrace();
   }
   ;
   System.out.println(i);
   evenLock.release();
  }
 };
 
 Runnable printEven = () -> {
  for (int i = 2; i < 10; i = i + 2) {
   try {
    evenLock.acquire();
   } catch (Exception e) {
    // TODO Auto-generated catch block
    e.printStackTrace();
   }
   System.out.println(i);
   oddLock.release();
 
  }
 };
 
 new Thread(printOdd).start();
 new Thread(printEven).start();
}

Before we see how this is actually working you need to understand how semaphores work. They essentially are like permits. You can initialize the semaphore with the initial permits. Let us say semaphore has 2 permits, to begin with. In this case, 2 threads can acquire these permits. The 3rd thread which comes has to wait till one of the 2 permits become available again. Threads that have acquired the permits can release them once they are done. Permits are acquired by acquire() method and released by release() method. To read more about Semaphores you can refer a post I had written earlier -

Counting Semaphore, CountDownLatch, CyclicBarrier - synchronization methods for concurrency

Also, note I have used Java 8 lambda syntax in the code above. You can read more about lambds -

Using Lambda Expressions from Java 8

Now with this understanding let's see how the above logic works.

printOdd runnable is responsible for printing odd numbers whereas printEven prints even number. For loop is designed in such a way and it increments by 2 to continue printing respective numbers. We need to start with 1 which is odd, so old thread starts first. Notice we have 2 semaphores - one for odd and one for even. Odd semaphore has 1 permit whereas even semaphore has 0, to begin with. The odd thread can get the permit from an odd semaphore and print the odd value which is 1. Meanwhile, the even thread will get blocked since no permits are available for even semaphore. Only when an odd thread releases even semaphore permit, even thread will go ahead and print 2. That's how each thread locks each other till numbers are printed in sequence.

You can do the same with the wait and notify. You can see both of the above methods on my GitHub repository on data structures - https://github.com/aniket91/DataStructures/blob/master/src/com/osfg/questions/PrintOddEven.java

Thursday, 17 January 2019

How to use Callable interface with Threads in Java?

Background

In one of the previous posts on Creating Threads with Executor service, we saw an interface called Callable. Executor has a method called submit that took Callable object and returned a future object which had the results. Unlike the Runnable interface, we can use Callable interface to return the result or throw checked Exceptions. In this post, we will see how to use Callable interface with plain Thread construct.

How to use Callable interface with Threads in Java?

We know that Thread takes Runnable interface only. No surprises there. So we cannot directly use objects implementing the Callable interface. Also to get the result we need Future object as we saw in Executors. Remember any design pattern that suits this use case? yes, it is Adapter Pattern. Java provides a class called FutureTask which implements Runnable and Future, combining both functionalities conveniently. Let's see an example of how we can do this -

package com.osfg;

import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.FutureTask;

public class Test {
 public static void main(String args[]) throws InterruptedException, ExecutionException {
 
  Callable<String> callable = () -> {
   Thread.sleep(5000);
   return "Hello!";
  };
 
  FutureTask<String> futureTask = new FutureTask<>(callable);
  Thread t = new Thread(futureTask);
  t.start();
 
  while (!futureTask.isDone()) {
   System.out.println("Task not done yet!");
   Thread.sleep(1000);
  }
 
  System.out.println(futureTask.get());
 }
 
}

You can see here that our Callable waits for 5 seconds and returns the results. And in the main thread, we do a check every 1 second to see if the result is available in the FutureTask. So if you run above code you will get -

Task not done yet!

Hello!

FutureTask has following methods -

public boolean cancel(boolean mayInterrupt): Used to stop the task. It stops the task if it has not started. If it has started, it interrupts the task only if mayInterrupt is true.
public Object get() throws InterruptedException, ExecutionException: Used to get the result of the task. If the task is complete, it returns the result immediately, otherwise, it waits until the task is complete and then returns the result.
public boolean isDone(): Returns true if the task is complete and false otherwise

Sunday, 27 January 2019

Sorting Techniques

Background

Sorting Techniques

Related Links

What is transient keyword in Java?

Background

Transient use cases

The transient and final keyword

Use of transient keyword in HashMap.

Related Links

Saturday, 19 January 2019

How to print odd and even numbers in order with two threads

Background

How to print odd and even numbers in order with two threads

Related Links

Thursday, 17 January 2019

How to use Callable interface with Threads in Java?

Background

How to use Callable interface with Threads in Java?

Related Links