Sunday, June 30, 2013

Callable and Future in Java

Runnable is default abstraction for creating a task in Java. It has a single method run() that accepts no arguments and returns no value, nor it can throw any checked exception. To overcome these limitations, Java 5 introduced a new task abstraction through Callable [javadoc ] interface.
public interface Callable<V>{
     V call() throws Exception;
}
Evident from the Callable interface shown above, call() method can return an Object, or more specifically any generic type. Like Runnable, Callable is also designed to be executed by threads. But you can't directly pass a Callable into Thread for execution. Check below snippet :

         Callable task = new Callable(){
  public Integer call(){
System.out.println("inside call method");
   return 1;
}
        };
Thread t = new Thread(task);    //doesn't compile

The last line in above code will not compile. It gives below compilation error message:  
"The constructor Thread(Callable) is undefined".
It tells Thread can't take a Callable argument.

Recall that Thread class implements Runnable interface, and it has been with Java since version 1.0, whereas Callable got added to the language in version 5.0 (or 1.5) only.

Running a Callable Task

Passing Callable into Thread for execution is out of question. Java SE 5 provides ExecutorService to execute the Callable object. The service accepts a Callable object.

        <T> Future<T> submit(Callable<T> task);

As above definition shows, submitting a Callable object to ExecutorService returns Future object. Future represents the life cycle of a task and is discussed below:

        Callable<List<T>> task = new Callable<List<T>>(){
               public List<T> call(){
                    List<T> results = new ArrayList<T>();
                   
                    //computation
                   
                    return results;
               }
        };

       ExecutorService es = Executors.newSingleThreadExecutor();

       Future<List<T>> future = es.submit(task);
       List<T> data = future.get();
       System.out.println("List Data :"+ data); 

The get() method of Future blocks, until the task is completed. This is equivalent to join() (i.e. t.join()) in normal thread case.

A closer look at Future

Future represents the life cycle of a task and provides methods to test whether the task has completed or been canceled, retrieve the result, and cancel the task. The behavior of get method depends on the state of the task (yet to start, completed, running). Get method returns immediately or throws Exception if the task has already completed. If the task is not completed then it blocks until the task completes. 
Future class methods
Straight from Java Doc :
Future represents the result of an asynchronous computation. Methods are provided to check if the computation is complete, to wait for its completion, and to retrieve the results of the computation.  The results can only be retrieved using method get when the computation has completed, blocking if necessary until it is ready. Cancellation is performed by the cancel method. Additional methods are provided to determine if the task completed normally or was canceled. Once a computation has completed, the computation cannot be canceled. If you would use a Future for the sake of cancellability but not provide a usable result, you can declare the type of the form Future<?> and return null as a result of the underlying task.

----

post your comments/questions below !!!

Saturday, June 15, 2013

LinkedHashMap Implementation in Java

LinkedHashMap is one of the commonly used Map implementations in Java. LinkedHashMap inherits from HashMap and implements Map interface. The basic building block is same as that of HashMap. It will be appropriate to cover HashMap internals before delving into details of LinkedHashMap. I have already discussed HashMap internals here.  This post talks about the delta or extras which LinkedHashMap adds on top of HashMap.

Building Blocks

LinkedHashMap uses the same array structure as used byHashMap. This means that it stores data in the array of Entry objects. Let's cover major aspects of LinkedHashMap.

Entry: HashMap stores objects in random order. Even in LinkedHashMap objects are put in the same way; but with some extra overheads, all these objects are interconnected to maintain a particular order. Let's see how Entry object differs here with respect to HashMap Entry.

   static class Entry<K,V> extends HashMap.Entry<K,V>{
         Entry<K,V> before, after;  
         Entry(int hash, K key, V value, HashMap.Entry<K,V) next){
             super(hash,key,value,next);
         }
   } 

LinkedHashMap's Entry class adds two extra pointers before and after to form a doubly linked list. HashMap.Entry is defined in HashMap internals post.

Header: Stores the head of the doubly linked list. Notice the way it is getting initialized/constructed at below snippet. This means that header is both start as well as end of the doubly linked list. 

       Entry<K,V> header;
       //construction or initialization
       header = new Entry<>(-1, null, null, null);
       header.before = header.after = header;

AccessOrder: This defines the order in which you can iterate a LinkedHashMap. It supports access-order as well as insertion-order. Default constructor supports insertion order (as shown below).

         
        boolean accessOrder;

        public LinkedHashMap(){

             super();
             accessOrder = false;
        } 

Other aspects like size, load factor, capacity, threshold etc remain unchanged.

Introspection

Let's do similar exercise as done in HashMap post, to store fruits inside LinkedHashMap and introspect internal details.  

 import java.lang.reflect.Field;  
 import java.lang.reflect.InvocationTargetException;  
 import java.lang.reflect.Method;  
 import java.util.LinkedHashMap;  
 import java.util.Map;  
   
 public class LinkedHashMapSimul {  
      static Map<String, Integer> map;  
   
      // Actual Method from HashMap library  
      static int indexFor(int h, int length) {  
           return h & (length - 1);  
      }  
   
      // Actual Method from HashMap library  
      static int hash(int h) {  
           h ^= (h >>> 20) ^ (h >>> 12);  
           return h ^ (h >>> 7) ^ (h >>> 4);  
      }  
   
      public static void interrospect() {  
           try {  
                Class<?> c = map.getClass();  
                c = c.getSuperclass();  
                Field f = c.getDeclaredField("size");  
                f.setAccessible(true);  
                int size = f.getInt(map);  
   
                f = c.getDeclaredField("loadFactor");  
                f.setAccessible(true);  
                float loadFactor = f.getFloat(map);  
   
                f = c.getDeclaredField("threshold");  
                f.setAccessible(true);  
                int threshold = f.getInt(map);  
   
                f = c.getDeclaredField("modCount");  
                f.setAccessible(true);  
                int modCount = f.getInt(map);  
   
                Method m = c.getDeclaredMethod("capacity", null);  
                m.setAccessible(true);  
                int capacity = (Integer) m.invoke(map, null);  
   
                System.out.println("Size: " + size + "; LoadFactor: " + loadFactor  
                      + "; Threashold: " + threshold + "; ModCount: " + modCount  
                      + " ; capacity :" + capacity);  
           } catch (SecurityException e) {  
                e.printStackTrace();  
           } catch (NoSuchFieldException e) {  
                e.printStackTrace();  
           } catch (IllegalArgumentException e) {  
                e.printStackTrace();  
           } catch (IllegalAccessException e) {  
                e.printStackTrace();  
           } catch (NoSuchMethodException e) {  
                e.printStackTrace();  
           } catch (InvocationTargetException e) {  
                e.printStackTrace();  
           }  
      }  
   
      public static void main(String[] args) {  
           map = new LinkedHashMap<String, Integer>();  
   
           map.put("guava", indexFor(hash("guava".hashCode()), 16));  
           map.put("mango", indexFor(hash("mango".hashCode()), 16));  
           map.put("pear", indexFor(hash("pear".hashCode()), 16));  
           map.put("banana", indexFor(hash("banana".hashCode()), 16));  
   
           System.out.println(" Map :" + map);  
           interrospect();  
      }  
 } 

Output
 Map :{guava=5, mango=9, pear=15, banana=1}
Size: 4; LoadFactor: 0.75; Threashold: 12; ModCount: 4 ; capacity :16

So the output confirms that the iteration order is the same as insertion. Above class creates default LinkedHashMap; which means initial capacity is 16, the load factor is 0.75 and accessOrder is false. Below diagram shows the mapping of the above items in the Entry array. Note that linked list begins from the header and ends at the header. Also due to this, iteration is more efficient in LinkedHashMap (compared to HashMap). Iteration in LinkedHashMap requires time proportional to the size of the map regardless of its capacity.



Related Post : HashMap Implementation in Java
 TreeMap implementation in Java 

Tuesday, June 11, 2013

Brief overview of JDBC

JDBC(Java DataBase Connectivity) is a Java API for connecting a wide range of Databases through Java program. Using JDBC API you can also access data from sources like spreadsheets and flat files. These apis are part of standard Java platform (JAVA SE). The actual driver to communicate with data sources is not part of the platform though (link).

JDBC API has two packages java.sql and javax.sql.
Below are the steps for successful communication with the data sources:

Step 1: Register Driver

Before starting the real communication with the data source, you need to load data source drivers in the memory. Recall that Java's class Class provides a static method (forName()) to load a class. It can be used to load and return a Class reference, but here, we just need to load appropriate driver class. 

    String driverName = "com.mysql.jdbc.Driver";
    Class.forName(driverName);

 

Step 2: Establish a Connection

If step 1 executes successfully without any error/exception then we are ready to move to the next step and create a Connection object. DriverManager provides a factory method to create the Connection object. 

    static final String USER = "user.id";
    static final String PASSWORD = "user.password";
    static final String URL = "jdbc.url";
    Connection con = DriverManager.getConnection(URL, USER, PASSWORD);

 

Step 3: Create Statement/s

SQL Statement is created using Connection object. This object is used for executing static SQL statement and returning the result.

    Statement stmt = con.createStatement();

Supported Statements are:
  1. Statement: Used for implementing SQL statements without any parameter.
  2. PreparedStatement: Used for precompiling SQL statements that might contain parameter as well.
  3. CallableStatement: Used for executing stored procedures (may contain input as well as output parameter).

 

Step 4 : Execute Query 

Finally, execute the query by calling the appropriate method on Statement object.
  1. execute: Used if query could return one or more ResultSet objects.
  2. executeQuery: Returns one ResultSet object.
  3. executeUpdate: Returns an integer representing the number of rows affected by the query. Use this method during INSERT, UPDATE and DELETE. 
     String sqlQuery = "Select name from EMPLOYEE";
     ResultSet rs = stmt.executeQuery(sqlQuery);

 

Step 5: Extract data from ResultSet

ResultSet object has response/result data which can be extracted using cursor/iterator. This is done by calling the appropriate get method (getXXX()).

    while(rs.next()){
         String name = rs.getString("name");
         //retrieve other attributes
    }

 

Step 6: Close Connection

Finally close connection and release resources held.

     }finally{
        if(stmt != null) {
           stmt.close();  //ResultSet also gets closed implicitly. 
       }
    }

      Wednesday, June 5, 2013

      HashMap implementation in Java

      Map is an associative array data structure used for mapping or associating value(s) with a key. We can insert key-value pairs in the map with the expectation that later on value can be looked up (or searched) given the key as the input. Insert(put) and search(get) are two most important operations on the map. In a normal array, keys are indices of the array and value is the object stored at the given index; whereas, in an associative array, keys could be of any type but still, we can quickly locate the value.

      One of the primary and most important map implementations in Java is HashMap. This post focuses on its internals instead of focusing on API details (Java doc).

      Building Blocks

      Let's cover some of the important aspects of HashMap:

      Array: HashMap internally stores all key-value pairs in an array. This array can be re-sized if required but its length should always be a power of two. The resizing happens when array is filled up to threshold level. 

          Entry[] table;  //Array in which key/value pair gets stored
          table = new Entry[capacity];  // Array creation based on the default/user supplied capacity

      Entry: As shown above, HashMap stores key,value pair in an array of Entry. Entry stores key as well as value. Apart from this, it also stores hash value of key so that it doesn't need to calculate on every invocation. If multiple keys have same hashcode; it results in collisions.  To handle this scenario next pointer is used to chain them and form a linked list. 

         static class Entry<K,V>{
              final K key;
              V value;
              Entry<K,V> next;
              final int hash;
         }

      Capacity: Capacity denotes the length of the array or number of buckets in the hash map. Initial capacity is specified at time of creation (default value is 16). You can specify any capacity initially but it should be power of 2.


          Map<String,String> map = new HashMap<String,String>(capacity);

      Load Factor: Load factor is a measure of, how full the hash map is allowed to get before its capacity is automatically increased. Default load factor is 0.75. If you create a default hashMap (capacity is 16 and load factor is 0.75) then re-sizing will happen if the 12 items have been added to the map. So REHASHING happens when number of entries in the map exceeds the product of load factor and the current capacity.

      Threashold: The next value at which resize will happen.  ( (int)capacity*loadFactor )

      Size : The number of key-value mappings contained in this map. The resize of the array depends on this number. It gets checked after every add method call.

        if( size >= threashold){  //if size after last add call >= threashold then resize table
               resize(2*table.length);
          }

      Introspection

      Above attributes of HashMap are not exposed for public use through API. This means you can't check how does HashMap evolves as you keep on adding key/value pairs.

      But does it mean that:
      You can't check these attributes at all?
      You can't check which index in the array a new item gets added?
      Certainly NOT.

      Reflection comes to rescue here (Reflection in Java). I have written a utility class through which you can monitor the evolution of HashMap through Reflection. 

          Map<String,Integer> map = new HashMap<String,Integer>();

      HashMapSimul.java uses default hashMap; which means, capacity will be 16 and loadFactor will be 0.75. Below example maps fruit names to the position on which it will get added in Map. Value is index on which item will get added in Map. I have used actual methods from the API to get the index.

       import java.lang.reflect.Field;  
       import java.lang.reflect.InvocationTargetException;  
       import java.lang.reflect.Method;  
       import java.util.HashMap;  
       import java.util.Map; 
      
       public class HashMapSimul {  
            static Map<String, Integer> map;  
            // Actual Method from HashMap library  
            static int indexFor(int h, int length) {  
                 return h & (length - 1);  
            }  
            // Actual Method from HashMap library  
            static int hash(int h) {  
                 h ^= (h >>> 20) ^ (h >>> 12);  
                 return h ^ (h >>> 7) ^ (h >>> 4);  
            }  
            public static void interrospect() {  
                 try {  
                      Class<?> c = Class.forName("java.util.HashMap");  
                      Field f = c.getDeclaredField("size");  
                      f.setAccessible(true);  
                      int size = f.getInt(map);  
                      f = c.getDeclaredField("loadFactor");  
                      f.setAccessible(true);  
                      float loadFactor = f.getFloat(map);  
                      f = c.getDeclaredField("threshold");  
                      f.setAccessible(true);  
                      int threshold = f.getInt(map);  
                      f = c.getDeclaredField("modCount");  
                      f.setAccessible(true);  
                      int modCount = f.getInt(map);  
                      Method m = c.getDeclaredMethod("capacity", null);  
                      m.setAccessible(true);  
                      int capacity = (Integer) m.invoke(map, null);  
                      System.out.println("Size: " + size + "; LoadFactor: " +loadFactor  
                            + "; Threashold: " + threshold + "; ModCount: " + modCount  
                            + " ; capacity :" + capacity);  
                 } catch (ClassNotFoundException e) {  
                      e.printStackTrace();  
                 } catch (SecurityException e) {  
                      e.printStackTrace();  
                 } catch (NoSuchFieldException e) {  
                      e.printStackTrace();  
                 } catch (IllegalArgumentException e) {  
                      e.printStackTrace();  
                 } catch (IllegalAccessException e) {  
                      e.printStackTrace();  
                 } catch (NoSuchMethodException e) {  
                      e.printStackTrace();  
                 } catch (InvocationTargetException e) {  
                      e.printStackTrace();  
                 }  
            }  
            public static void main(String[] args) {  
                 map = new HashMap<String, Integer>();  
                 map.put("guava", indexFor(hash("guava".hashCode()), 16));  
                 map.put("mango", indexFor(hash("mango".hashCode()), 16));  
                 map.put("pear", indexFor(hash("pear".hashCode()), 16));  
                 map.put("orange", indexFor(hash("orange".hashCode()), 16));  
                 System.out.println(" Map :" + map);  
                 interrospect();  
                 System.out.println("-------------------------------");  
                 map.put("banana", indexFor(hash("banana".hashCode()), 16));  
                 System.out.println(" Map :" + map);  
                 interrospect();  
            }  
       }
      

      Output
       Map :{orange=1, guava=5, mango=9, pear=15}
      Size: 4; LoadFactor: 0.75; Threashold: 12; ModCount: 4 ; capacity :16
      -------------------------------------
       Map :{banana=1, orange=1, guava=5, mango=9, pear=15}
      Size: 5; LoadFactor: 0.75; Threashold: 12; ModCount: 5 ; capacity :16

      Mapping above item to Array of Entry