Sunday 22 February 2015

Java Class Design using Builder

Background

Two important principle of Object Oriented programming are - 
  1. For each class design aim for low coupling and high cohesion.
  2. Classes should be open for extension but closed for modification.

We will see how we can use these to design any classes.



Class Design


Lets design a simple Employee class which has it's name.

public class Employee {
    
    private String name;
    
    public Employee(String name)
    {
        this.name = name;
    }
    
}


Looks good. Every time anyone has to create an instance of Employee he has to supply name in the constructor. So you see any flaw in this?

Well there is. Lets say new requirement comes up and you now have to add employee age. What would you do?

One way would be change the constructor to include age now.

public class Employee {
    
    private String name;
    private int age;
    
    public Employee(String name, int age)
    {
        this.name = name;
        this.age = age;
    }  
}


Though it solves our new requirement it will break all our existing code. All Users using our existing code will  have to make changes now. So we definitely cannot remove the constructor with name in it. So what do we do next ?

Lets create an overridden constructor.

public class Employee {
    
    private String name;
    private int age;
    
    public Employee(String name)
    {
        this.name = name;
    }
    
    public Employee(String name, int age)
    {
        this(name);
        this.age = age;
    }
    
}


Ok this looks good. This will not break existing code and will meet our existing requirement. Now take a minute to this what about future requirements. Lets say you may have to add employees sex, salary etc in the Employee mode. What will you do then? Keep adding overloaded constructors?

Sure you can. But that is a very poor design choice. Simplest thing to do is following -

public class Employee {
    
    private String name;
    private int age;
    
    public Employee(){}

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }
    
}


That's right. A simple no argument default constructor and getter, setter methods corresponding to instance variables. This is flexible design implementation. Going forward we can add as many instance variables with corresponding get and set methods.

Though this is good and simple class design. I would not say it is optimal. What if you want to ensure that user should not create a Employee instance without providing name.

Sure different developers will have different methods to ensure that and have good design. I like to use builder for that. See following -


import static org.apache.commons.lang3.Validate.*;
public class Employee
{
    private String name;
    private int age;
    
    private Employee() {}

    public String getName()
    {
        return name;
    }
    
    public int getAge()
    {
        return age;
    }

    public static class EmployeeBuilder
    {
        private final Employee employee;

        public EmployeeBuilder()
        {
            employee = new Employee();
        }

        public EmployeeBuilder setName(String name)
        {
            employee.name = name;
            return this;
        }
        
        public EmployeeBuilder setAge(int age)
        {
            employee.age = age;
            return this;
        }

        public Employee build()
        {
            validateFields();
            return employee;
        }

        private void validateFields()
        {
            notNull(employee.name, "Employee Name cannot be Empty");
            isTrue(employee.age >= 21, "Employee age cannot be less than 21");
        }
    }
}



Notice following points -
  1. We made constructor of Employee class private. So no one can directly instantiate Employee class. He or she has to use our Builder class.
  2. There is not setter methods in Employee class. Again builder should be used.
  3. Builder's build() methods validates our requirements like name cannot be null or age has to be more than 21.
  4. You can easily create Employee objects using - 
Employee employee = new EmployeeBuilder().setName("Aniket").setAge(23).build();

Friday 20 February 2015

Using Android Emulator to test your Android Application

Background

I have written a couple of posts before on Android Application development, debugging and other general concepts. As you know Android is just an operating system running on Linux kernel customized for resource constrained environment like that of handheld systems. Before you roll out your application to other users you need to test it on various models (with different configurations). This is where you Emulator comes into picture. You can create a emulator that suits your testing requirement. In this post we will cover some of the events that we can simulate with emulators like setting batter to low etc. So basically we will use a telnet to connect to Android virtual device and issue commands to simulate various events.

Creating an Android virtual Device

Lets start by creating an Android virtual device. Open your Eclipse which come as a pert of ADT bundle.

Go to 

Windows -> Android Virtual Device Manager

I currently don't have any emulators. So the manager shows no emulators.



Go ahead and create one. Click on create button on the right. Fill in the configuration details as per your requirements.


After successful creation of AVD start it. Wait for it to initialize (It may take couple of minutes). My Emulator looks like the following at startup -



Now lets connect to it via telnet. See the number at the top of the Emulator ? (5554:athakur_Nexus) This number (5554) is the port number emulator is running on. You can do various action by connecting to it via telnet. Connecting is very simple. Simply type following in command prompt -

  • telnet localhost 5554
and you  get a 'OK' response. Notices the 3G network symbol at the top right corner. Lets change it to 2G or edge. Command for that is -
  • network speed edge


To change it back to 3G you can use command -
  • network speed full
 You can also change the battery status of your emulated device.  Notice the battery icon. It about little more than 50% charged and battery is still charging (power is connected).

Lets first reduce the battery level. To do so you can use following command -
  • power capacity 4
and notice how battery level drops.



Battery is still charging. Notice the lightning symbol inside battery icon. Lets stop the charging. To do so use the following command -
  • battery status not-charging (Usage: "status unknown|charging|discharging|not-charging|full")
You can also simulate sms.  I am going to send a dummy message from telnet and you should see it as a proper message received in the emulator. Command for the same is -
  • sms send 9999999999 "Hi! - From Open Source For Geeks" (Syntax : sms send <phonenumber> <text message>)




You can even change your  coordinates on the map with following command -

  • geo fix 2.00 39.12
It is also possible to make a call from one emulator to  another. Simple go to dialer and dial port number of the other emulator. Emulator number running with that port will receive the call.






These are only some command. To get a full list of command you can type help after connecting to telnet -


Note :

  • You can reorient your device in the emulator by pressing Ctrl+F12 (Command+F12 on Mac). When this happens and your current Activity is killed and restarted.

Related Links

Monday 16 February 2015

Proxy Design Pattern in Java

Background

We know proxy design pattern involves a representative object that controls access to it's subject that may be - 
  1. Remote
  2. Expensive to create (Virtual Proxy) or
  3. Need secure access (Protection Proxy)
In last post on

Understanding Java Remote Method Invocation (RMI)

We say example of Remote proxy. Stub is essentially the proxy that controls access of actual remote object.

Here is the summary of what happens in Proxy design pattern -

Proxy class implements the same interface as that of the Subject. Client crates a instance of proxy class (Typically using Factory pattern.) rather than the actual subject and calls methods on proxy (this is possible since both proxy and subject implement same interface). Now proxy internally instantiates Subject and calls methods on it depending on the purpose of the proxy.




We will see example of both Virtual as well as Protection proxy in this example. Later we will also see how proxies are dynamically created (Java has in built support for it).

 Virtual Proxy

Lets say we are creating a news website. Lets design Interface for it - 

public interface NewsSiteInterface {
    void showNews();
}

Now lets write the actual implementation - 
public class NewsSiteImpl implements NewsSiteInterface {
    
    String news;
    
    public NewsSiteImpl() {
        //simulate blocking data transfer
        try {
            Thread.sleep(5000);
            System.out.println("Data Received");
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        news = "Hello World";
    }
    
    public void showNews() {
        System.out.println(news);
    }

  
}


Notice the constructor simulates fetching data which is a block call. If you directly make instance of NewsSiteImpl and call showNews() on it site may possible hang as instance creation will take time. Lets now create a proxy that would avoid this blocking call.


public class NewsSiteProxy implements NewsSiteInterface {
    
    NewsSiteInterface newsSite;
    
    public NewsSiteProxy() {
        new Thread(new Runnable() {
            @Override
            public void run() {
                newsSite = new NewsSiteImpl();
                showNews();
            }
        }).start();
    }

    @Override
    public void showNews() {
        if(newsSite == null) {
            System.out.println("Loading....");]
        }
        else {
            newsSite.showNews();
        }
        
    }

}

So now we create instance of  NewsSiteInterface in another thread asynchronously. So user can go ahead and call showNews(). Obviously data may not be loaded by then, So we just show Loading...
Important point out program will not get hanged. Lets test out setup.

public class NewsDemo {
    public static void main(String args[])
    {
        NewsSiteInterface newSite  = new NewsSiteProxy();
        newSite.showNews();
        newSite.showNews();
    }
    
}

and the output is -

Loading....
Loading....
Data Received
Hello World

So that was our virtual proxy that helped us tackle creating on expensive time consuming instance.

Now lets see our protection proxy. Well the concept remains the same. Instead of doing task asynchronously we do some validation.

 In our next protection proxy demo we will use Java Dynamic proxies.

Protection Proxy and Java Dynamic proxy

Lets say we are designing a programming QnA site like Stack Overflow.  When user create a account on Stack Overflow he essentially created a profile. Lets write a class for that -


public interface StackOverflowProfile {
    String askQuestion(String question);
    String writeAnswer(String answer);
    void upVote();
    void downVote();
}


Now lets create a concrete implementation of this profile interface.

public class StackOverflowProfileImpl implements StackOverflowProfile {

    @Override
    public void askQuestion(String question) {
        //Ask Question
    }

    @Override
    public void writeAnswer(String answer) {
        //Provide Answer to a question
    }

    @Override
    public void upVote() {
        //Up vote an Answer or Question
        
    }

    @Override
    public void downVote() {
        //Down vote an Answer or Question
    }

}


So far so good. Program would work but we did a major mistake here. We do not have verification check in the code which means a user can keep asking questions, answer them and keep upvoting the same thereby increasing his or her reputation.  Only if we knew proxy pattern before :)

Lets divide out auth checks / Proxy into two parts -
  1. Owner of a Question
  2. Non Owner
Our use case is -
  • Owner can ask question, answer question but cannot do upvote or downvote.
  • Non owner cannot ask question but he can answer, upvote or downvote.
Note : Each profile can use either of the proxy depending on if he or she is the owner of the Question. If owner then Owner Proxy will be used and upvote or downvote operations will not be allowed. If non owner proxy is used then question cannot be asked (as someone else is the owner) but answer, upvote, dowvote operations are allowed.

We are now going to use Dynamic proxies to implement above checks -

import java.lang.reflect.InvocationHandler;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;

public class OwnerSOProfile implements InvocationHandler {
    
    StackOverflowProfile soProfile;
    
    public OwnerSOProfile(StackOverflowProfile soProfile)
    {
        this.soProfile = soProfile;
    }

    @Override
    public Object invoke(Object proxy, Method method, Object[] args)
            throws Throwable {
        try
        {
            if(method.getName().equalsIgnoreCase("askQuestion"))
            {
                method.invoke(proxy, args);
            }
            else if(method.getName().equalsIgnoreCase("writeAnswer"))
            {
                method.invoke(proxy, args);
            }
            else if(method.getName().equalsIgnoreCase("upVote"))
            {
                throw new IllegalAccessException("Cannot Up vote own question or answer");
            }
            else if(method.getName().equalsIgnoreCase("downVote"))
            {
                throw new IllegalAccessException("Cannot down vote own question or answer");
            }
        }
        catch(InvocationTargetException ex) {
            ex.printStackTrace();
        }
        return null;
    }
}




and

import java.lang.reflect.InvocationHandler;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;

public class NonOwnerSoProfile implements InvocationHandler {
    
    StackOverflowProfile soProfile;
    
    public NonOwnerSoProfile(StackOverflowProfile soProfile)
    {
        this.soProfile = soProfile;
    }

    @Override
    public Object invoke(Object proxy, Method method, Object[] args)
            throws Throwable {
        
        try
        {
            if(method.getName().equalsIgnoreCase("askQuestion"))
            {
                throw new IllegalAccessException("Cannot edit question as you are not the owner");
            }
            else if(method.getName().equalsIgnoreCase("writeAnswer"))
            {
                method.invoke(proxy, args);
            }
            else if(method.getName().equalsIgnoreCase("upVote"))
            {
                method.invoke(proxy, args);
            }
            else if(method.getName().equalsIgnoreCase("downVote"))
            {
                method.invoke(proxy, args);
            }
        }
        catch(InvocationTargetException ex) {
            ex.printStackTrace();
        }
        return null;
    }
}



and finally lets do a demo -

import java.lang.reflect.Proxy;

public class SODemo {
    
    public static void main(String args[])
    {
        //general profile
        StackOverflowProfile profile = new StackOverflowProfileImpl();
        //allowed
        (profile).askQuestion("What is proxy pattern?");
        //not allowed
        getOwnerSoProxy(profile).upVote();
        //not allowed
        getNonOwnerSoProxy(profile).askQuestion("Java anti patterns?");
        //alowed
        getNonOwnerSoProxy(profile).upVote();
    }
    
    public static StackOverflowProfile getOwnerSoProxy(StackOverflowProfile profile)
    {
        return (StackOverflowProfile) Proxy.newProxyInstance(profile.getClass().getClassLoader(), profile.getClass().getInterfaces(), new OwnerSOProfile(profile));
    }
    
    public static StackOverflowProfile getNonOwnerSoProxy(StackOverflowProfile profile)
    {
        return (StackOverflowProfile) Proxy.newProxyInstance(profile.getClass().getClassLoader(), profile.getClass().getInterfaces(), new NonOwnerSoProfile(profile));
    }

}

Note : For above demo code. Try one call at a time because we have not added any Exception handling so whenever IllegalAccess Exception is thrown JVM will terminate.

Related Links

Saturday 14 February 2015

Understanding Java Remote Method Invocation (RMI)

Background

Everyone with Java background would know we can easily call methods on an instantiated object as long as everything is limited to same JVM (Java virtual machine). Even imagined if we can invoke methods on a remote object as if they were local. Well the answer is yes and that is exactly what we are going to see in this post. Infact RMI uses one of the famous design patters - The Proxy Pattern . We will cover that in detail under design patterns. For now keep following in mind -

Proxy Design Pattern involves a representative Object (A proxy) that controls access to another object which may be - 
  • Remote
  • Expensive to Create (Virtual Proxy)
  • Needs secure access (Protection Proxy)

This post aims to help you understand how RMI works, how objects interact with a simple demo.

Getting Started

Java RMI APIs essentially help you to invoke methods on remote object.  There are four essential entities that take part in RMI - 
  1. Client
  2. Stub / Client Helper (Proxy)
  3. Server
  4. Skeleton / Server Helper

Server is where you have your actual implementation of service. Client want to call it.  Client code cannot directly call methods on remote server object as they are on different JVMs .So client creates a representation of actual service called stub or proxy and invokes methods on it. Stub takes this call, serializes method name, parameters etc and send its over network to the skeleton on the server. skeleton then deserializes the information and invokes the method on actual object. It takes the result serializes it and sends in back to stub. Stub deserializes the result and returns it back to the client code.


That's for the overview of how RMI works. Now lets see an actual demo in Java.


To The Code....

Lets start by writing an interface for the remote service - 

import java.rmi.Remote;
import java.rmi.RemoteException;


public interface GreeterService extends Remote {
    public String displayWelcomeMessage(String name) throws RemoteException;
}

Notice how our interface extends java.rmi.Remote interface? It is a marker interface(No methods in it) just like - 
  • java.lang.Cloneable
  • java.io.Serializable

It is used to mark that methods of instances of class that implement this interface can be called from non local (remote) virtual machines.

Also notices how our method declaration throws RemoteException ? Well it's not mandatory but a good practice so that the implementation handles it and is aware that thing may go wrong as calls are made to another virtual machine (which may be remote).

Lets write implementation for this -

import java.rmi.Naming;
import java.rmi.RemoteException;
import java.rmi.server.UnicastRemoteObject;


public class GreeterServiceImpl extends UnicastRemoteObject implements GreeterService {

    protected GreeterServiceImpl() throws RemoteException { }

    @Override
    public String displayWelcomeMessage(String name) throws RemoteException {
        return "Hi " + name + " welcome to Open Source For Geeks!";
    }
    
    public static void main(String args[])
    {
        try {
            GreeterService greeterService = new GreeterServiceImpl();
            Naming.rebind("greeterServiceObj", greeterService);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}


So we wrote a class that implements the GreeterService and it's methods.

Notice how we have extended UnicastRemoteObject? That is because that super class takes care of actual communication part with remote VM.

Also notice we have declared a no-args constructor that throws RemoteException. That's because super class UnicastRemoteObject has constructor that throws that Exception.
  • UnicastRemoteObject is used for exporting a remote object with JRMP and obtaining a stub that communicates to the remote object (Socket level logic). 
  • We will use this GreeterServiceImpl class to generate skeleton and stub and the communication logic is handled by UnicastRemoteObject that GreeterServiceImpl extends.
  • JRMP is Java Remote Method Protocol.  It is a Java-specific, stream-based protocol for Java-to-Java remote calls, requiring both clients and server to use Java objects. RMI-IIOP is an alternative protocol which exposes Java objects to CORBA ORBs.
We are done with our server level logic. Now lets
  1. Create skeleton and stub, 
  2. start rmi registry
  3. Start Remote Service
First Compile classes -
  • javac *.java

You should have two class files - GreeterService.class and GreeterServiceImpl.class. Now you can go ahead and create stub skeleton . Run

  • rmic GreeterServiceImpl 
 You should get GreeterServiceImpl_Stub.class file.


Note : From rmic 1.2 onwards, Java don't generate skeletion class any more. New JRMP protocol supported for RMI has got rid of the use of skeleton files.  




Now start rmiregistry. Just type rmiregistry in command line.


Note 1 : Start rmiregistry from location that has access to the stub class file.
Note 2 : If you want to start your rmi registry on different port (defult is 1099) you can use command - rmiregistry [port]

 Now start your remote Service -

  • java GreeterServiceImpl
Your remote service and rmiregistry are all set. Now lets write client and test our setup -

import java.net.MalformedURLException;
import java.rmi.Naming;
import java.rmi.NotBoundException;
import java.rmi.RemoteException;


public class GreeterClient {

    public static void main(String args[])
    {
        try {
            GreeterService greeterService = (GreeterService) Naming.lookup("rmi://127.0.0.1/greeterServiceObj");
            System.out.println(greeterService.displayWelcomeMessage("Aniket"));
        } catch (MalformedURLException | RemoteException | NotBoundException e) {
            e.printStackTrace();
        }
    }
    
}


Make sure your client Java process has access to following Java class files -
  1. GreeterClient.class
  2. GreeterService.class
  3. GreeterServiceImpl_Stub.class
 Yes! That's all client needs. Lets run client.


  • javac *.java
  • java GreeterClient

 Related Links



Friday 13 February 2015

Understanding how hashing (HashMap and HashSet) work in Java

Background

Hashing is a very important concept in computer programming and a very popular concept for interview questions. Two important data structures related to hashing are HashMap and HashSet which is exactly what we are going to look at in this post.

Overview

If you are from a computer science background you would know HashMap is a data structure which stores key value pairs where as a HashSet stores unique data. In HashMap we have kind of buckets and each data added to a HashMap falls into one of the buckets depending on the hash value of it. Also you must have heard that adding and retrieving objects in HashMap happen in time complexity O(1).

But still there are open end question like -
  • What happens when two objects added to HashMap have same hash (code) value ? - a situation typically known as collision.
  • If above is handled how get and put work in hashmap?.... and so on.
We will address them now.

Understanding how HashMap works

 You can visualize HashMap as follows-




So you have an Array and each array position is essentially a Linked List. As you know you don't have to specify size of the HashMap. It increases dynamically like ArrayList.  The main data structure is essentially an array.

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


When you create a HashMap you either choose to provide initial capacity or when you don't a default value is used.

    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 16;


 When table is created it is created with either this initial default capacity or the capacity you provide in the constructor.

Next important thing is when should out table we resized to meet the dynamically changing data size of HashMap. Answer depends on a threshold that is determined by load factor.

    /**

     * The load factor used when none specified in constructor.

     */

    static final float DEFAULT_LOAD_FACTOR = 0.75f;


HashMap provides a constructor to initialize load factor as well. So when your data size equals

  • threshold = table capacity * load factor

then the HashMap table is resized. Constructors are as follows -

    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
        table = new Entry[capacity];
        init();
    }

    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param  initialCapacity the initial capacity.
     * @throws IllegalArgumentException if the initial capacity is negative.
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
        init();
    }


How is data with keys generating same hash code stored in HashMap?

As mentioned earlier each index has reference to object of type Entry which is a Linked List. It has a next pointer. So if an entry is added to hash map it's hash code is computed which determines the index at which it should be put. If that index has an entry then new entry is added to the start of the linked list and existing linked list is appended to next of it.

    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

    void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }


Also note how null is handled. Yes null is an acceptable key in HashMap.

So how is data retrieved if two keys generate same hash code?

Same hash code will make searched for both keys data land on same index in the table. From there the each Entry object is iterated over and it's key compared with the search key. Yes both key and value are stored in the Node/Entry object! On successful match corresponding value is returned.

    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

How data is stored in HashMap

 First of all the Node array size is always 2^N. Following method guarantees it -

static final int tableSizeFor(int cap) {

    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

So lets say you provide initial capacity as 5
cap = 5

n = cap - 1 =  4 = 0 1 0 0
n |= n >>> 1;    0 1 0 0 | 0 0 1 0 = 0 1 1 0 = 6
n |= n >>> 2;    0 0 1 1 | 0 1 1 0 = 0 1 1 1 = 7
n |= n >>> 4;    0 0 0 0 | 0 1 1 1 = 0 1 1 1 = 7
n |= n >>> 8;    0 0 0 0 | 0 1 1 1 = 0 1 1 1 = 7
n |= n >>> 16;   0 0 0 0 | 0 1 1 1 = 0 1 1 1 = 7
return n + 1     7 + 1 = 8 


So table size is 8 = 2^3

Now possible index values you can put your element in map are 0-7 since table size is 8. Now lets look at put method. It looks for bucket index as follows -

Node<K,V> p =  tab[i = (n - 1) & hash];

where n is the array size. So n = 8. It is same as saying

Node p = tab[i = hash % n];

So all we need to see now is how

hash % n == (n - 1) & hash

Lets again take an example. Lets say hash of a value is 10.

hash = 10
hash % n = 10 % 8 = 2
(n - 1) & hash = 7 & 10 = 0 1 1 1 & 1 0 1 0 = 0 0 1 0 = 2

So it's a optimized modulo operation with bitwise & operator.

A good hash function

A hash function is a method that computes hash of a key where data is stored. It should obviously return value between 0 - (n-1) for an array of length n used to store the data.

A good has function will have take minimum computation time will evenly distribute keys in the array. 
For array of size n and m elements inserted it's load factory would ideally be 

α = m/n

A hash function can be thought of two parts - 
  1. Hash code Map (Key -> Integer)
  2. Compression Map (Integer -> [0,N-1])
Simple hash function (Compression Map) for an array of size N would be

  • h(k) = k mod n where k is the key and n is the size of the array.

NOTE : In above function h(k) you need to take care that m is not  a power of 2. If you do you are only using last m bits of the number to compute hash in that case which is not a good method.

So choose m close to n and m should be prime.


Another compression map can be -

  • h(k) =lowerbound ( k A mod 1) where k is the key, m is the size of the array and A is a constant between 0 and 1 i.e 1<A<0
NOTE : For String avoid adding ascii values of characters as it is not a good function. Multiple words may result in same hash and map to same bucket resulting in higher collision. Use polynomial function instead. So if your integers of ascii chars are c0, c1, c2 use polynomial like -

C0 + C1(X) + C2(X^2)

String class in Java uses following has method -

    /**
     * Returns a hash code for this string. The hash code for a
     * <code>String</code> object is computed as
     * <blockquote><pre>
     * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
     * </pre></blockquote>
     * using <code>int</code> arithmetic, where <code>s[i]</code> is the
     * <i>i</i>th character of the string, <code>n</code> is the length of
     * the string, and <code>^</code> indicates exponentiation.
     * (The hash value of the empty string is zero.)
     *
     * @return  a hash code value for this object.
     */
    public int hashCode() {
    int h = hash;
        int len = count;
    if (h == 0 && len > 0) {
        int off = offset;
        char val[] = value;

            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
        return h;
    } 



Other hashing techniques are
  1. Linear probing :

    if (table is full error)
    probe = h(k)
    while(table(probe) is not empty)
              probe = (probe + 1) mod m
    table[prob] = k
  2. double hashing :

    if (table is full error)
    probe = h1(k)
    offset = h2(k)
    while(table(probe) is not empty)
              probe = (probe + offset) mod m
    table[prob] = k

NOTE : In java if hashing is involved (lets say you are using HashMap or a HashSet) make sure you override equals() and hascode() method to suit your requirements.  As much as is reasonably practical, the hashCode() method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer)

HashMap changes in Java8

The performance has been improved by using balanced trees instead of linked lists under specific circumstances. It has only been implemented in the classes 
  1. java.util.HashMap, 
  2. java.util.LinkedHashMap and 
  3. java.util.concurrent.ConcurrentHashMap.
This will improve the worst case performance from O(n) to O(log n).

Lastly lets see HashSet.

Understanding HashSet

Well if you are still guessing the data structure of HashSet then following would be a surprise -

    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();



Yup HashSet stores data as keys of HashMap with dummy value. Constructor is equivalent to that of HashMap -

    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
    map = new HashMap<E,Object>();
    } 



    public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<E,Object>(initialCapacity, loadFactor);
    }



    public HashSet(int initialCapacity) {
    map = new HashMap<E,Object>(initialCapacity);
    }


Add and Remove methods are as follows -

    public boolean add(E e) {
    return map.put(e, PRESENT)==null;
    }



    public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
    }

Understanding LinkedHashMap

LinkedHashMap as we know stores the insertion order. However it also extends HashMap so it respects O(1) time complexity as well for insertion. So how does it really work.

LinkedHashMap maintains another type on Entry which holds pointer to previous as well as next Entry Node.

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

LinkedHashMap also stores head and tail of this double linked list and thats how it maintains the insertion order. So even though put follows hashing storage and retrieval order is maintained using doubly linked list.

    /**
     * The head (eldest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> head;
    /**
     * The tail (youngest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> tail;

So whenever you add a new key, value pair following happens -

    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }
    // link at the end of list
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    } 

When iterating it iterates from head to tail thereby providing same order as insertion.

NOTE : before and after pointers are in addition to the next pointer which is inherited from HashMap.Node class. So next points to next node having same hash (collision scenario) thereby preserving O(1) lookups. Before and After pointers guarantee insertion lookup order.

Understanding TreeMap

TreeMap as you already know stores the data in sorted order. If the data it stores implements Comparable interface then it stores data in that natural order or you can pass a custom comparator to the TreeMap and it will use that to sort and store the data.

TreeMap maintains a binary search tree structure. It has a root, value less than root go to left where as value greater than root go to right and it's balanced too (RBT - A red–black tree is a kind of self-balancing binary search tree).

    /**
     * The comparator used to maintain order in this tree map, or
     * null if it uses the natural ordering of its keys.
     *
     * @serial
     */
    private final Comparator<? super K> comparator;
    private transient Entry<K,V> root;

Simple code snippet would be -

        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;

where cmp is the comparison value got either from comparators compare() method or Comparables compareTo() method.

Related Links

Monday 9 February 2015

Adapter and Facade Design Patterns in Java

Background

Some time back we saw Decorator design pattern which was the 1st Structural design pattern that we tried to understand. Adapter and Facade are two more design pattern that come under same category - Structural Design pattern.

Adapter Design Pattern

Adapter pattern converts one interface to another interface that is expected by the target or client system. It simply make interfaces compatible so that integration is possible. To visualize see following diagram


Target or client expects an interface where as interface that is going to use it provides different interface and none of them can be modified. In such cases Adapter proves to be beneficial.

Lets take an example -

Lets say you have designed a program that computes cost of a list of items supplied to it. In your computeCost() method you expect that customer would provide Iterator instance. You write code something like below -

import java.util.Iterator;


public class CostComputer {
    
    public static int computeCost(Iterator<Product> iterator)
    {
        int cost = 0;
        while(iterator.hasNext())
        {
            cost = cost + iterator.next().getCost();
        }
        return cost;
    }
    
}


Also you have exposed a Product interface. Those who want to compute cost should have models extending this Product interface implement it's getCost() method and then can pass the iterator of it to above utility method.

public interface Product {
    int getCost();
}



Now here's something you did not expect.  You get a Toy manufacturing company as your client and their code is something like -

public class Toy implements Product {

    int cost;
    
    public Toy(int cost)
    {
        this.cost = cost;
    }
    
    @Override
    public int getCost() {
        return cost;
    }

}


and

import java.util.Enumeration;
import java.util.Random;
import java.util.Vector;


public class ToysCreator {
    
    int count;
    
    public ToysCreator(int count)
    {
        this.count = count;
    }
    
    public Enumeration createToys()
    {
        Vector toys = new Vector<>();
        for(int i=0; i<count ;i++)
        {
            toys.add(new Toy(new Random().nextInt(10)));
        }
        return toys.elements();
    }

}


and then they tried to use your code as follows -

public class ToysCostComputer {
    
    public static void main(String args[])
    {
        System.out.println(CostComputer.computeCost(new ToysCreator(6).createToys())); // this will fail
    }

}


and viola -

Exception in thread "main" java.lang.Error: Unresolved compilation problem:
    The method computeCost(Iterator<Product>) in the type CostComputer is not applicable for the arguments (Enumeration)

    at ToysCostComputer.main(ToysCostComputer.java:6)

Program crashed. Your code expected a Iterator but customer code returns Enumeration. Now you or your customer have to build Adapter to support Enumeration.

It goes as follows -

import java.util.Enumeration;
import java.util.Iterator;


public class EnumToIteratorAdapter implements Iterator<Product> {

    Enumeration<Product> enumeration;
    
    public EnumToIteratorAdapter(Enumeration<Product> enumeration)
    {
        this.enumeration = enumeration;
    }
    
    @Override
    public boolean hasNext() {
        return enumeration.hasMoreElements();
    }

    @Override
    public Product next() {
        return enumeration.nextElement();
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
        
    }

}


and now client can use our code with the help of Adapter

import java.util.Iterator;


public class ToysCostComputer {
    
    public static void main(String args[])
    {
        Iterator toysIterator = new EnumToIteratorAdapter(new ToysCreator(6).createToys());
        System.out.println(CostComputer.computeCost(toysIterator));
    }

}


and the output is - 27. Some random number but you get the point.

Class Diagram for our above demo is as follows -



Generic Class diagram for Adapter Pattern is as follows -



That was Adapter Pattern. Now lets come to facade pattern.

so in facade pattern Adapter implements target and has an instance of Adaptee. So whenever methods of target are called we call suitable methods of adaptee.

Facade Pattern.

Facade Pattern is kind of an overlay. It provides a unified interface to set of interfaces in the sub system. Note that we cannot say it encapsulates methods of sub system classes as methods of sub system classes are still available for direct use. Facade pattern just simplifies it by abstraction.

There is no fixed generic class diagram as such but it will look like -


Lets say you have multiple modules for handling program bugs. May be
  1. class BugCreator that creates various types of bugs - UI, functional, localization etc. 
    • Methods : createBug(String bugType) etc
  2. class BugsReplicator that tries replicates the bug as per the description of filed bug.
    • Methods :  replicateBug(Bug newBug) etc
  3. class BugsSolver that finds the fix and checks in the code.
    • Methods : fixBug(Bug newBug) etc
  4. class BugsDeployer that deploys the fix to dev or qa environments.
    • Methods : deployFix(CodeFix fix) etc
  5. class BugsTester that tests out the fix
    • Methods : testFix(Bug bug) etc
Now lets say your customer uses these classes or subsystems to handle their code bugs. They will have to call each method and do handling on their own. Instead you can provide them with a simplified facade.

public boolean resolveBug(String desc, String bugType)
{
      Bug newBug =  new BugCreator().createBug(bugType);
      boolean replicated = new BugsReplicator .replicateBug(newBug);
      if(replicated)
      {
          CodeFix fix = new BugsSolver().fixBug(newBug);
          new BugsDeployer().deployFix(fix);
          if(new BugsTester.testFix(Bug bug))
          {
              return true;
          }
          else
          {
              return false;
          }
      }
      else
      {
          return false;
      }
}


Now this is just an example that I am giving to help you understand how Facade pattern simplifies subsystem complexity. 


Notes

  • Facade does not encapsulate subsystem classes. It simply provides simplified interface to complex subsystem classes. Subsystem classes are still accessible for direct use.

Summary

  • Decorator pattern does not alter any interface. It simply adds responsibility.
  • Adapter pattern Converts one interface (Adaptee) to another (Target) for compatibility.
  • Facade pattern simplifies interface for complex subsystem subclasses.

Related Links

Saturday 7 February 2015

String processing using Matcher, Pattern and Regex in Java

Background

Using regex or simply regular expressions have been very important part of String processing. We will explore it is this post.


Before you get to Java code lets take a looks at Regex symbols - 

Regex Symbols

Common Regex Symbols : 

Common Regex Meta Symbols : 


Common Regex Quantifier Symbols : 

Now lets head on to Java Code....

Using java.util.regex.Pattern and java.util.regex.Matcher classes

Lets use these classes to demonstrate regex.

    public static void main(String args[])
    {
        String str = "Hi there! My name is John. How can I help you?";
        Pattern p = Pattern.compile("[.!?]");
        Matcher matcher = p.matcher(str);
        int count = 0;
        while(matcher.find()) {
            count++;
        }
        System.out.println("Count : " + count);

    }

and the output is - 3. Lets see what we did here. We have a String - "Hi there! My name is John. How can I help you?"  and we are interested in finding number of times symbol '.', '!' or '?' appears in the String. So we provided the regex "[.!?]". 

Did not quite get the regex part? Go back to previous section - Regex symbols. Notice in Common Regex symbols image [xyz] represent x or y or z. We are simply incrementing the counter if we find such a regex meaning '.', '!' or '?' '.

Lets head on to something more interesting. How many time have you used String classes split() method? Did you realize that it is infact a regex that split method takes. We split words from line as follows -

    public static void main(String args[])
    {
        String str = "Hello all. Welcome to Open Source For Geeks!";
        String[] tokens = str.split(" ");
        for(String token : tokens)
        {
            System.out.println(token);
        }

    }


and you get output as -

Hello
all.
Welcome
to
Open
Source
For
Geeks!


as expected.  If you see the split method code it internally used java.util.regex.Pattern to compile you regex and use it to split the String -

    public String[] split(String regex, int limit) {
    return Pattern.compile(regex).split(this, limit);
    }


Now lets do the same thing as split using Patter and Matcher.

    public static void main(String args[])
    {
        String str = "Hello all. Welcome to Open Source For Geeks!";
        Pattern pattern= Pattern.compile("\\w+");
        Matcher matcher = pattern.matcher(str);
        while(matcher.find()) {
            System.out.println(matcher.group());
        }

    }


and the output is -

Hello
all
Welcome
to
Open
Source
For
Geeks


Noticed any difference? '.'(dot) and '!'(exclamation) are not present. Well that is expected. See Regex symbols again. We used "\\w+"  which means match one or more word character and dot and exclamation aren't one of them.

Note : Space is also not a word character. Else we would have got whole String as matched pattern (leaving dot and exclamation mark aside). Digits are also part of word characters i.e \\w+ .

 So lets slightly modify our code to get the same output.

    public static void main(String args[])
    {
        String str = "Hello all. Welcome to Open Source For Geeks!";
        Pattern pattern= Pattern.compile("\\w+\\.*!*");
        Matcher matcher = pattern.matcher(str);
        while(matcher.find()) {
            System.out.println(matcher.group());
        }

    }


and the output is -

Hello
all.
Welcome
to
Open
Source
For
Geeks!


Ok that's the same. What did we do here? Notice the regex again. This time it is - "\\w+\\.*!*". We are saying get me sequence that matches [(one or more word characters) then (zero or more dot symbols) then (zero or more exclamation symbols)].

Note :  Dot is a regex symbol and hence you need to escape (like we did \\. ) it if you want to use it for searching dot pattern. Exclamation on the other hand was not so we could directly use it.


Another Example


Lets  do something practical now. Lets say you have following data (maybe in a file or just an array) -

data1=${key1}
data2=${key2}
data3=${key3}

and you have to replace the placeholder with the actual value whose mapping you have (again maybe in a different file).

key1 -> ActualKey1
key2 -> ActualKey2
key3 -> ActualKey3

and finally you want output like -

data1=ActualKey1
data2=ActualKey2
data3=ActualKey3

Lets write code to achieve this using regex.

    public static void main(String args[])

    {

        String[] replacableData = new String[]{"data1=${key1}","data2=${key2}","data3=${key3}"};

        Map<String, String> keyMappings = new HashMap<String, String>();

        keyMappings.put("key1", "ActualKey1");

        keyMappings.put("key2", "ActualKey2");

        keyMappings.put("key3", "ActualKey3");

        Pattern pattern= Pattern.compile("(\\w+=)(\\$\\{)(\\w+)(\\})");

        for(String str : replacableData) {

            Matcher matcher = pattern.matcher(str);

            String key = matcher.replaceAll("$3");

            System.out.println("Key : " + key);

            String newStr = matcher.replaceAll("$1"+ keyMappings.get(key));

            System.out.println("After Replacement : " + newStr);

        }

    }


and the output is -

Key : key1
After Replacement : data1=ActualKey1
Key : key2
After Replacement : data2=ActualKey2
Key : key3
After Replacement : data3=ActualKey3


Another important concept to note here is the groups in the rgex that you can refer later with $groupIndex.

In our regex - "(\\w+=)(\\$\\{)(\\w+)(\\})"

group1 -> (\\w+=)
group2 -> (\\$\\{)
group3 -> (\\w+)
group4 -> (\\})
  Also replaceAll() replaces the entire original String with whatever group combinations you provide. For example matcher.replaceAll("$1$2$3$4") will give you back the same String.

Note : replaceAll() method return a new String. original String is not changed.

Note :  Even used replace() and replaceAll() method of String class?  Both of them replace all occurences with the String you desire. Only difference is replaceAll() uses a regex where as replace() uses simple CharSequence.
t> UA-39527780-1 back to top