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

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
long	float	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

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

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