Thursday, February 09, 2012

Java Data Structure - Part1

My dig at Java data structures -

Part1 -


How do hashtables/HashMap work ?

At the heart of the hash table algorithm is a simple array of items; this is often simply called the hash table. Hash table algorithms calculate an index from the data item's key and use this index to place the data into the array. The implementation of this calculation is the hash function

What happens if two keys have the same hashCode ?

Often termed as hash collision , hashtable implementations have to deal with it. One of the ways and the most common way to deal with this situation is to maintain a list of values
for keys with the same hashCode. HashCode of the keys would result into the same value and hence point to the same index in the array, containing mulitple key-values.
Run a equals on the key and return the appropriate value back to the caller.

What happens if the two keys have the same equals value ?

Pretty obvious duplicate keys cannot be stored and hence the original key/value is retained and new one being added is rejected

When implementing a LRU cache which datastructure would one use ?

LinkedHashMap would be an obvious choise for a couple of reasons -

1. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).
2. The removeEldestEntry(Map.Entry) method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.
3. A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order)


How would one define a structural modification in a HashMap ?

A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with a key that an instance already contains is not a structural modification.

How would one define a structural modification in a LinkedHashMap ?

A structural modification is any operation that adds or deletes one or more mappings or, in the case of access-ordered linked hash maps, affects iteration order.
In insertion-ordered linked hash maps, merely changing the value associated with a key that is already contained in the map is not a structural modification.
In access-ordered linked hash maps, merely querying the map with get is a structural modification.

Its important to understand structural modifications , since maps are not synchronized unlike a hashtable if a thread structurally modifies a map while another thread is iterating over the same there could be serious concurrency issues. Potentially resulting in ConcurrentModificationException

Please comment below with any interesting questions/discussions you might have come across with hashtables/maps

MORE STUFF-

  • Memory footprint of java primitives

  • Gretty - example - web-service

  • Sample code - Kilim

  • An actor framework for Java concurrency

  • Querying the memory usage of a Java object
  • Saturday, December 10, 2011

    Memory footprint of java primitives

    Memory foot print of Java primitives

    Java Primitive Data Types

    Data Type Description Size Default Value
    boolean true or false 1-bit false
    char Unicode Character 16-bit \u0000
    byte Signed Integer 8-bit (byte) 0
    short Signed Integer 16-bit (short) 0
    int Signed Integer 32-bit 0
    long Signed Integer 64-bit 0L
    longfloat Real number 32-bit 0.0f
    double Real number 64-bit 0.0d

    Next -- Garbage Collection explained
    Prev -- Querying memory usage of a java object




    ALSO READ
    Java development 2.0: Ultra-lightweight Java web services with Gretty
    An actor framework for Java concurrency
    10 things you didn't know about java performance monitoring
    Java collection performance - Chart view
    The Clean Coder

    Gretty - example - web-service



    import org.mbte.gretty.httpserver.* 
    
    @GrabResolver(name='gretty', 
      root='http://groovypp.artifactoryonline.com/groovypp/libs-releases-local')
    @Grab('org.mbte.groovypp:gretty:0.4.279') 
    
    GrettyServer server = [] 
    server.groovy = [ 
        localAddress: new InetSocketAddress("localhost", 8080), 
        defaultHandler: { 
            response.redirect "/" 
        }, 
        "/:name": {
            get {
                response.text = "Hello ${request.parameters['name']}"
            } 
        } 
    ] 
    server.start()
    
    What this program does -

    I created a server listening on port 8080, then set up a simple root endpoint containing the parameter name. Any request to some other endpoint will be routed back to / via the defaultHandler. The handler basically sends the requesting client an HTTP 301 "moved permanently" code, with the location of /. All requests will receive a response (with the content-type set to text/plain) containing the string "Hello" along with the value of any parameter passed; for instance, /Andy would yield "Hello Andy."

    required librabies -

    Groovy 1.8
    gretty 0.4.279 and its dependent librabies downloaded by Grape


    Execute -

    groovy server.groovy

    Making content type text/html -


    "/:name": {
     get {
      response.html = "Hello ${request.parameters['name']}"
     } 
    } 
    
    Using a template -
    <html> <head>
      <title>Hello!</title>
     </head>
     <body>
      <p>${message}</p>
     </body>
    </html>
    
    Using the template in response -

    "/:name" {  get {
       response.html = template("index.gpptl", 
         [message: "Hello ${request.parameters['name']}"])
      }
    }
    
    Accessing Mongo DB- use Morphia



    @GrabResolver(name='morphia', root='http://morphia.googlecode.com/svn/mavenrepo/')
    @Grab(group='com.google.code.morphia', artifactId='morphia', module="morphia", 
      version='0.99')
    

    Anyone's guess that this is a pure restful service - So this brings us to the question on when to use a restful service vs a soap based service. A quick read REST vs SOAP service




    Also Read
    An actor framework for Java concurrency
    Instrumentation - Querying the memory usage of a Java object
    10 things you didn't know about java performance monitoring
    The Clean Coder

    Sample code - Kilim

    A simple Calculator example -pretty naive but then demonstrates using Actor based model in java

    In Kilim a thread must extend Task object and implement the execute method which should throw Pausable exception. Kilim weaver (read it as byte code enhancer) interprets classes containing operations throwing Pausable exception and weaves(enhances) it.

    import java.math.RoundingMode;
    
    import kilim.Mailbox;
    import kilim.Pausable;
    import kilim.Task;
    
    public class Calculator extends Task{
    
     private Mailbox mailbox;
    
     public Calculator(Mailbox mailbox) {
      super();
      this.mailbox = mailbox;
     }
    
     @Override
     public void execute() throws Pausable, Exception {
      while (true) {   
       Calculation calc = mailbox.get(); // blocks
       if (calc.getAnswer() == null) {
        calc.setAnswer(calc.getDividend().divide(calc.getDivisor(), 8, 
          RoundingMode.HALF_UP));    
        System.out.println("Calculator determined answer");
        mailbox.putnb(calc);
       }
       Task.sleep(1000);
      }
     }
    }
    


    Thread2 - demonstrates sharing of data between Thread1 using a Mailbox

    import java.math.BigDecimal;
    import java.math.MathContext;
    import java.util.Date;
    import java.util.Random;
    
    import kilim.Mailbox;
    import kilim.Pausable;
    import kilim.Task;
    
    public class DeferredDivision extends Task {
    
     private Mailbox mailbox;
    
     public DeferredDivision(Mailbox mailbox) {
      super();
      this.mailbox = mailbox;
     }
    
     @Override
     public void execute() throws Pausable, Exception {
      Random numberGenerator = new Random(new Date().getTime());
      MathContext context = new MathContext(8);
      while (true) {
       System.out.println("I need to know the answer of something");
       mailbox.putnb(new Calculation(
         new BigDecimal(numberGenerator.nextDouble(), context), 
         new BigDecimal(numberGenerator.nextDouble(), context)));
       Task.sleep(1000);
       Calculation answer = mailbox.getnb(); // no block
       if (answer != null && answer.getAnswer() != null) {
        System.out.println("Answer is: " + answer.printAnswer());
       }
      }
     }
    }
    



    Using Ant invoke Kilim's weaver(byte code enhancer)
    
     
      
      
      
      
     
    
    


    A simple test runner
    import kilim.Mailbox;
    import kilim.Task;
    
    public class CalculationCooperation {
     public static void main(String[] args) {
      Mailbox sharedMailbox = new Mailbox();
    
      Task deferred = new DeferredDivision(sharedMailbox);
      Task calculator = new Calculator(sharedMailbox);
    
      deffered.start();
      calculator.start();
    
     }
    }
    

    Notice how the same Mailbox is shared between threads without a lock or synchronization

    Your output will vary — actors are nondeterministic
    [java] I need to know the answer of something
    [java] Calculator determined answer
    [java] Answer is: The answer of 0.36477377 divided by 0.96829189 is 0.37671881
    [java] I need to know the answer of something
    [java] Calculator determined answer
    [java] Answer is: The answer of 0.40326269 divided by 0.38055487 is 1.05967029
    [java] I need to know the answer of something
    [java] Calculator determined answer
    [java] Answer is: The answer of 0.16258913 divided by 0.91854403 is 0.17700744
    [java] I need to know the answer of something
    [java] Calculator determined answer
    [java] Answer is: The answer of 0.77380722 divided by 0.49075363 is 1.57677330
    

    Sequence Diagram -


    Conclusion - As in Scala or Erlang , Actor model can be applied to java.



    Also Read
    Java development 2.0: Ultra-lightweight Java web services with Gretty
    Instrumentation - Querying the memory usage of a Java object
    10 things you didn't know about java performance monitoring
    5 things you didn't know about java.util.concurrent
    The Clean Coder

    Friday, December 09, 2011

    An actor framework for Java concurrency

    Recently my curiosity towards learning something new , bumped me into a framework called Kilim. Ya that's right , not sure how many of you have heard about it.

    Goal of this framework - to introduce Actor based concurrency to java ala. making the model similar to Erlang and Scala

    Why do we need this switch from thread based model to Actor based model when it comes to concurrency - thread based model depends on using shared memory when it comes to communicating between threads. Actor based model takes a slightly different approach of using Mailboxes to communicate.

    So whats the advantage ? - well when coded against Actor based model we don't need to worry about thread locks or use any kind of synchronization blocks. Actors are guaranteed to run on multi-core processors. Since there is no limitation or a dependency on shared memory actors can be scheduled on any core or a processor. Improves the overall performance and the scalability of system.

    How to use Kilim? sample code - here








    Also Read
    Java development 2.0: Ultra-lightweight Java web services with Gretty
    Instrumentation - Querying the memory usage of a Java object
    10 things you didn't know about java performance monitoring
    5 things you didn't know about java.util.concurrent
    The Clean Coder

    Thursday, December 08, 2011

    Querying the memory usage of a Java object

    Creating the instrumentation agent class - would work with Jdk 5 and above



    The JVM will pass to our method an implementation of the Instrumentation interface, defined in java.lang.instrument. In turn, this interface defines the method getObjectSize(). So for example, if we want to measure the memory usage of an instance of SomeClass, our agent code would look as follows:
    import java.lang.instrument.*;
    import com.somepackage.SomeClass;
    
    public class MyAgent {
      public static void premain(String args, Instrumentation inst) {
        SomeClass obj = new SomeClass();
        long size = inst.getObjectSize(obj);
        System.out.println("Bytes used by object: " + size);
      }
    }
    
    Package the agent into a jar -

    create manifest.txt with
    Premain-Class: mypackage.MyAgent

    execute this to create a jar -

    jar -cmf manifest.txt agent.jar mypackage/MyAgent.class

    Run the application with the agent -

    java -javaagent:agent.jar -cp . com.mypackage.Main

    Accessing the Instrumentation object from within our application -

    public class MyAgent {
      private static volatile Instrumentation globalInstr;
      public static void premain(String args, Instrumentation inst) {
        globalInstr = inst;
      }
      public static long getObjectSize(Object obj) {
        if (globalInstr == null)
          throw new IllegalStateException("Agent not initted");
        return globalInstr.getObjectSize(obj);
      }
    }
    

    Now, provided the agent is included in the JVM command line parameters as above, then from anywhere in our application we can call MyAgent.getObjectSize() to query the memory size of an object created by our Java application

    Note that the getObjectSize() method does not include the memory used by other objects referenced by the object passed in.


    Next -- Memory footprint of java datatypes




    Also Read
    Java development 2.0: Ultra-lightweight Java web services with Gretty
    An actor framework for Java concurrency
    Java Garbage Collection explained
    Java collection performance - Chart view
    The Clean Coder

    Hello world with gretty



    Gretty is a simple web framework for both building web servers and clients. Built on top of netty, it supports NIO style http server, asynchronous http client. It also supports both websocket server and client.

    It's designed to be light weight and run as a standalone embedded solution.

    It's written in Groovy++. But you can use it with pure Groovy, Scala or even Java.

    Do bear with me for not being a fancy writer -

    Sample code demonstrating a quick web-service implementation



    Also Read
    An actor framework for Java concurrency
    Instrumentation - Querying the memory usage of a Java object
    10 things you didn't know about java performance monitoring
    The Clean Coder

    Share it