Tuesday, May 31, 2011

Thread Local in java

Thread Local can be considered as a scope of access, like a request scope or session scope. It’s a thread scope. It has following:

  • Values stored in Thread Local are global to the thread, meaning that they can be accessed from anywhere inside that thread. If a thread calls methods from several classes, then all the methods can see the Thread Local variable set by other methods (because they are executing in same thread). The value need not be passed explicitly. It’s like how you use global variables.
  • Values stored in Thread Local are local to the thread, meaning that each thread will have it’s own Thread Local variable. One thread can not access/modify other thread’s Thread Local variables.

Comparing Thread locals in other languages and Java

A thread-local variable effectively provides a separate copy of its value for each thread that uses it. Each thread can see only the value associated with that thread, and is unaware that other threads may be using or modifying their own copies. Some compilers (such as the Microsoft Visual C++ compiler or the IBM XL FORTRAN compiler) have incorporated support for thread-local variables into the language using a storage-class modifier (like static or volatile). Java compilers offer no special language support for thread-local variables; instead, they are implemented with the ThreadLocal class, which has special support in the core Thread class.

Because thread-local variables are implemented through a class, rather than as part of the Java language itself, the syntax for using thread-local variables is a bit more clumsy than for language dialects where thread-local variables are built in. To create a thread-local variable, you instantiate an object of class ThreadLocal. The ThreadLocal class behaves much like the various Reference classes in java.lang.ref; it acts as an indirect handle for storing or retrieving a value.

When to use ThreadLocal?

Consider a case when some application is connecting to database. Now you may provide some DAO with connection object as field:

class MyDao{
Connection con;
public void doSomeBusinessLogic()
{
con = datasource.getConnection();
con.doUpdate();
}
}

Now in multi-threaded environment, there is possible that when 1 connection is active, one may be updating and other may be updating simultaneously. So it may be possible that threads may update database but incompletely. So what is the solution for this?

Solution 1 : Make a Connection object locally in a synchronized method.

public synchronized void doBusinessLogic()
{
Connection con = datasource.getConnection();
//some logic
//do update
con.close();
}

This approach solves above problem, but brings in 1 more problem:


  1. We have to create connection object each time method is called, which is very expensive.
  2. Also as threads increase, high processor usage will result. So this may result in problem.

Solution 2 : Make a connection pool and get connections from there.


public synchronized void doBusinessLogic(){
Connection con = pool.getConnection();
//some logic
//do update
}


This approach is fine. But still there is problem of contention. If you are using multi-threaded environment, with multicores, it will be waste of resources to use Connection pooling approach.


Solution 3 : Use thread local


Now we can use ThreadLocal to avoid contention.
Suppose we have thread T1 and T2. ThreadLocal for T1 has a map in which it will have T1 and corresponding connection object. Similarilty ThreadLocal for T2 has T2 and corresponding connection object. Now when doing the same business logic, we can say:


public void doBusinessLogic(){
Connection con = myThreadLocal.connection;
con.doUpdate();
}


So we don't have to create the connection object again and again. Also if hardware is good there is no contention on the database. Suppose later we need some other local variable say transaction, even that will be saved in the map like this.
Some people say that we can pass connection as parameter in the business method, but that will make code look horrible and cumbersome. But that is a solution.


Advantage of ThreadLocal:



  1. No contention. If memory is not an issue, thread local is the best approach.
  2. It avoids using local objects like connection to be used as parameter, making code look simpler but still efficient.

Example code


Consider you have a Servlet which calls some business methods. You have a requirement to generate a unique transaction id for each and every request this servlet process and you need to pass this transaction id to the business methods, for logging purpose. One solution would be passing this transaction id as a parameter to all the business methods as discussed above. But this is not a good solution as the code is redundant and unnecessary.

To solve that, you can use Thread Local. You can generate a transaction id (either in servlet or better in a filter) and set it in the Thread Local. After this, what ever the business method, that this servlet calls, can access the transaction id from the thread local.

This servlet might be servicing more that one request at a time. Since each request is processed in separate thread, the transaction id will be unique to each thread (local) and will be accessible from all over the thread’s execution (global).

Java provides an ThreadLocal object using which you can set/get thread scoped variables. Below is a code example demonstrating what I’d explained above.

First make the DAO or transaction dealing class:

package com.vaani.dao;

public class SomeDAO {
private String transactionId = null;
//some methods to deal with transaction
public void setTransactionId(String transId)
{
transactionId = transId;
}
public String getTransactionId() {
return transactionId;
}

}

Now create Thread Local class to hold this Dao above.

package com.vaani.threadlocal;

import com.vaani.dao.SomeDAO;

public class MyThreadLocal {

public static final ThreadLocal userThreadLocal
                              = new ThreadLocal();

public static void set(SomeDAO dao) {
userThreadLocal.set(dao);
}

public static void unset() {
userThreadLocal.remove();
}

public static SomeDAO get() {
return (SomeDAO)userThreadLocal.get();
}
}
In the above code, you are creating a ThreadLocal object as a static field which can be used by rest of the code to set/get thread local variables.

Let’s create our main class file which will generate and set the transaction ID in thread local and then call the business method.

package com.vaani.demo;

import com.vaani.businesscode.BusinessService;
import com.vaani.dao.SomeDAO;
import com.vaani.threadlocal.MyThreadLocal;

public class ThreadLocalDemo extends Thread {

public static void main(String args[]) {

Thread threadOne = new ThreadLocalDemo();
threadOne.start();

Thread threadTwo = new ThreadLocalDemo();
threadTwo.start();
}

@Override
public void run() {
// sample code to simulate transaction id
SomeDAO dao = new SomeDAO();
dao.setTransactionId(getName());

// set the context object in thread local
// to access it somewhere else

MyThreadLocal.set(dao);

/* note that we are not explicitly
passing the transaction id */

new BusinessService().businessMethod();
MyThreadLocal.unset();

}
}


Finally, here’s the code for the BusinessService.java which will read from thread local and use the value.

package com.vaani.businesscode;

import com.vaani.dao.SomeDAO;
import com.vaani.threadlocal.MyThreadLocal;

public class BusinessService {

public void businessMethod() {
// get the context from thread local
SomeDAO dao = MyThreadLocal.get();
System.out.println(dao.getTransactionId());
}
}

Output

When you run the ThreadLocalDemo file, you’ll get the below output:

Thread-1
Thread-0

As you might see, even though we are not explicitly passing the transaction id, the value can be accessed from the business method and printed on the console. Adding to it, the transaction ID differs for each thread (0 and 1).

Source Code


You can download Source code from here.

Atomic operations

An atomic operation is an operation which is performed as a single unit of work without the possibility of interference from other operations.
In Java the language specification guarantees that that reading or writing a variable is atomic (unless the variable is of type long or double). Long and double are only atomic if they declared as volatile.
The operation i++ it not atomic in Java for the standard variables (int, long, etc).
Here i++ is not a single instructions its basically 3 instructions :
i.) Read i
ii.) Increment i
iii.) Set i
These 3 instructions may not happen atomically.

It first reads the value which is currently stored in i (atomic operations) and then it adds one to it (atomic operation). But between the read and the write the value of i might have changed. Java

Since Java 1.5 the java language provides atomic variables, e.g. AtomicInteger or AtomicLong which provide methods like getAndDecrement(), getAndIncrement() and getAndSet() which are atomic.

Difference between synchronized and volatile



The main differences between synchronized and volatile are:
  • a primitive variable may be declared volatile whereas synchronized cannot be applied on the primitive types, but on some object or method or class.
  • Lock - Volatile deals with visibility, so if one thread modifies some variable, it will be known to other thread, so unlike a synchronized block we will never hold on to any lock; This is the big difference as synchronized offers mutual exclusion while volatile don't.
  • Attempting to synchronize on a null object will throw a NullPointerException, while  this is fine with volatile.
  • As synchronized offers mutual exclusion, it offers atomicity as well. But volatile doesn't mean atomic. (click on the link to see why)
Thanks

Monday, May 30, 2011

How to synchronize a static variable of a class ?

There are some ways(3 to my knowledge, but may be more), by which a static variable can be synchronized in java.

1) Use a synchronized static method. This synchronizes on the class object.

public class Counter {
private static int count = 0;

public static synchronized void incrementCount() {
count++;
}
}


2) Explicitly synchronize on the class object, using synchronize on ClassName.class

public class Counter {
private static int count = 0;

public void incrementCount() {
synchronize (Test.class) {
count++;
}
}
}


3) Synchronize on some other static object.

public class Counter {
private static int count = 0;
private static final Object countLockHelper = new Object();

public void incrementCount() {
synchronize (countLockHelper) {
count++;
}
}
}


Method 3 is best in many cases because the lock object is not exposed outside of your class. So if you create instance of these class, they will be synchronized on the same static object.

But if you just using some basic type like integer here in case of counter, consider using an AtomicInteger or another suitable class from the java.util.concurrent.atomic package:

public class Counter {

private final static AtomicInteger count = new AtomicInteger(0);

public void incrementCount() {
count.incrementAndGet();
}
}

Sunday, May 29, 2011

Difference between Factory Pattern or Abstract Factory Pattern and Builder Pattern

Abstract factory may also be used to construct a complex object, then what is the difference with builder pattern? In builder pattern emphasis is on ‘step by step’. Builder pattern will have many number of small steps. Those every steps will have small units of logic enclosed in it. There will also be a sequence involved. It will start from step 1 and will go on upto step n and the final step is returning the object. In these steps, every step will add some value in construction of the object. That is you can imagine that the object grows stage by stage. Builder will return the object in last step. But in abstract factory how complex the built object might be, it will not have step by step object construction.

Both are creational pattern but differ:
Factory Pattern Builder Pattern
The factor pattern defers the choice of what concrete type of object to
make until run time.
E.g. going to a restaurant to order the special of  the day.  The waiter is the interface to the factory that takes the
abstractor generic message "Get me the special of the day!" and returns
the concrete product (i.e "Chilli Paneer" or some other dish.)
The builder pattern encapsulates the logic of how to put together a
complex object so that the client just requests a configuration and the
builder directs the logic of building it.   E.g The main contractor
(builder) in building a house knows, given a floor plan, knows how to
execute the sequence of operations (i,e. by delegating to subcontractors)
needed to build the complex object.  If that logic was not encapsulated in
a builder, then the buyers would have to organize the subcontracting
themselves 
The factory is concerned with what is made. The builder with how it is
made. So it focuses on the steps of constructing the complex object.
In case of Factory or Abstract Factory, the product gets returned immediately Builder returns the product as
the final step.

Restrictions on clone method

There are couple of restrictions on clone methods:
  • It is a protected method and can only be called from within the same class or the module that contains the class.
  • We can only clone objects which are declared to implement the Cloneable interface.
  • Objects that cannot be cloned throw the CloneNotSupportedException.

Environment variables in java

Unlike C or C++, there is no getEnv() method in Java.

Part of the reason is that Java could conceivably be run on a platform that does not support the concept of environment variables. The expected way to pass environment-variable-like values to a Java application is with the -Dname=value syntax seen a few times in earlier chapters. Using the -D syntax on the java command line effectively adds the specified name and value to the list of system properties. Therefore, if you need to send a system environment variable named SomeEnvVar to your Java code, you can include it on the command line like this:

java -Dsome.env.variable=$SomeEnvVar YourClass (Unix/Linux)

or

java -Dsome.env.variable=%SomeEnvVar% YourClass (Windows) 


Then you access the new system property as follows:

String some_value = System.getProperty ("some.env.variable"); 

Obviously, you can name the system property anything you want.



Range-view Operation on list

The range-view operation, subList(int fromIndex, int toIndex), returns a List view of the portion of this list whose indices range from fromIndex, inclusive, to toIndex, exclusive. This half-open range mirrors the typical for-loop:

for (int i=fromIndex; i<toIndex; i++) {
...
}


As the term view implies, the returned List is backed by the List on which subList was called, so changes in the former List are reflected in the latter.


This method eliminates the need for explicit range operations (of the sort that commonly exist for arrays). Any operation that expects a List can be used as a range operation by passing a subList view instead of a whole List. For example, the following idiom removes a range of elements from a list:

list.subList(fromIndex, toIndex).clear();



Similar idioms may be constructed to search for an element in a range:


int i = list.subList(fromIndex, toIndex).indexOf(o);
int j = list.subList(fromIndex, toIndex).lastIndexOf(o);


Note that the above idioms return the index of the found element in the subList, not the index in the backing List.

Any polymorphic algorithm that operates on a List (like the replace and shuffle examples, above) works with the List returned by subList.

Here's a polymorphic algorithm whose implementation uses subList to deal a hand from a deck. That is to say, it returns a new List (the "hand") containing the specified number of elements taken from the end of the specified List (the "deck"). The elements returned in the hand are removed from the deck.

public static List dealHand(List deck, int n) {
int deckSize = deck.size();
List handView = deck.subList(deckSize-n, deckSize);
List hand = new ArrayList(handView);
handView.clear();
return hand;
}

 

The literal-minded might say that this program deals from the bottom of the deck, but I prefer to think that the computer is holding the deck upside down. At any rate, for many common List implementations, like ArrayList, the performance of removing elements from the end of the list is substantially better than that of removing elements from the beginning.

Here's a program using the dealHand method in combination with Collections.shuffle to generate hands from a normal 52-card deck. The program takes two command line arguments: the number of hands to deal and the number of cards in each hand.

 

import java.util.*;

class Deal {
public static void main(String args[]) {
int numHands = Integer.parseInt(args[0]);
int cardsPerHand = Integer.parseInt(args[1]);

// Make a normal 52-card deck
String[] suit = new String[] {"spades", "hearts", "diamonds", "clubs"};
String[] rank = new String[]
{"ace","2","3","4","5","6","7","8","9","10","jack","queen","king"};
List deck = new ArrayList();
for (int i=0; i<suit.length; i++)
for (int j=0; j<rank.length; j++)
deck.add(rank[j] + " of " + suit[i]);

Collections.shuffle(deck);

for (int i=0; i<numHands; i++)
System.out.println(dealHand(deck, cardsPerHand));
}
}


Let's run the program:


% java Deal 4 5

[8 of hearts, jack of spades, 3 of spades, 4 of spades, king of diamonds]
[4 of diamonds, ace of clubs, 6 of clubs, jack of hearts, queen of hearts]
[7 of spades, 5 of spades, 2 of diamonds, queen of diamonds, 9 of clubs]
[8 of spades, 6 of diamonds, ace of spades, 3 of hearts, ace of hearts]

While the subList operation is extremely powerful, some care must be exercised when using it. The semantics of the List returned by subList become undefined if elements are added to or removed from the backing List in any way other than via the returned List. Thus, it's highly recommended that you use the List returned by subList only as a transient object, to perform one or a sequence of range operations on the backing List. The longer you use the subList object, the greater the probability that you'll compromise it by modifying the backing List directly (or through another subList object).


 

Positional Access and Search Operations on Lists

The basic positional access operations (get, set, add and remove) behave just like their longer-named counterparts in Vector (elementAt, setElementAt, insertElementAt and removeElementAt) with one noteworthy exception. The set and remove operations return the old value that is being overwritten or removed; the Vector counterparts (setElementAt and removeElementAt) return nothing (void). The search operations indexOf and lastIndexOf behave exactly like the identically named operations in Vector.

The addAll operation inserts all of the elements of the specified Collection starting at the specified position. The elements are inserted in the order they are returned by the specified Collection's iterator. This call is the positional access analogue of Collection's addAll operation.

Here's a little function to swap two indexed values in a List.

private static void swap(List a, int i, int j) {
Object tmp = a.get(i);
a.set(i, a.get(j));
a.set(j, tmp);
}


Of course there's one big difference. This is a polymorphic algorithm: it swaps two elements in any List, regardless of its implementation type. "Big deal," you say, "What's it good for?" Funny you should ask. Take a look at this:


public static void shuffle(List list, Random rnd) {
for (int i=list.size(); i>1; i--)
swap(list, i-1, rnd.nextInt(i));
}


This algorithm (which is included in the JDK's Collections(in the API reference documentation)class) randomly permutes the specified List using the specified source of randomness. It's a bit subtle: It runs up the list from the bottom, repeatedly swapping a randomly selected element into the current position. Unlike most naive attempts at shuffling, it's fair (all permutations occur with equal likelihood, assuming an unbiased source of randomness) and fast (requiring exactly list.size()-1 iterations). The following short program uses this algorithm to print the words in its argument list in random order:


import java.util.*;

public class Shuffle {
public static void main(String args[]) {
List l = new ArrayList();
for (int i=0; i<args.length; i++)
l.add(args[i]);
Collections.shuffle(l, new Random());
System.out.println(l);
}
}


In fact, we can make this program even shorter and faster. The Arrays(in the API reference documentation)class has a static factory method called asList that allows an array to be viewed as a List. This method does not copy the array; changes in the List write through to the array, and vice-versa. The resulting List is not a general-purpose List implementation, in that it doesn't implement the (optional) add and remove operations: arrays are not resizable. Taking advantage of Arrays.asList and calling an alternate form of shuffle that uses a default source of randomness, you get the following tiny program, whose behavior is identical to the previous program:


import java.util.*;

public class Shuffle {
public static void main(String args[]) {
List l = Arrays.asList(args);
Collections.shuffle(l);
System.out.println(l);
}
}

Collection Operations on Lists–Simple and Bulk

Create the lists
List list1 = new ArrayList(); 
List list2 = new ArrayList();


Add the elements


// Add elements to the lists ...
list1.add("Hanuman");

Bulk Add
Copy all the elements from list2 to list1 (list1 += list2). list1 becomes the union of list1 and list2

list1.addAll(list2); 

Bulk Remove
Remove all the elements in list1 from list2 (list1 -= list2). list1 becomes the asymmetric difference of list1 and list2

list1.removeAll(list2); 

Intersection of Lists
Get the intersection of list1 and list2. list1 becomes the intersection of list1 and list2

list1.retainAll(list2); 

Remove all elements from a list

list1.clear(); 


Truncate the list


int newSize = 2;
list1.subList(newSize, list1.size()).clear();

Lists In Java

A List(in the API reference documentation)is an ordered Collection(in the API reference documentation)(sometimes called a sequence). Lists may contain duplicate elements. In addition to the operations inherited from Collection, the List interface includes operations for:

  • Positional Access: manipulate elements based on their numerical position in the list.
  • Search: search for a specified object in the list and return its numerical position.
  • List Iteration: extend Iterator semantics to take advantage of the list's sequential nature.
  • Range-view: perform arbitrary range operations on the list.

List Interface

List Implementations

 

Comparing List to Vector

ListIterator Interface

Operations on Lists

There are various type of operations that can be performed on lists:


Generic Lists in Java
Performance of List implementations in java

Introduction to Sets in java

A Set(in the API reference documentation) is a Collection(in the API reference documentation) that cannot contain duplicate elements. Set models the mathematical set abstraction. The Set interface contains no methods other than those inherited from Collection. It adds the restriction that duplicate elements are prohibited. Set also adds a stronger contract on the behavior of the equals and hashCode operations, allowing Set objects with different implementation types to be compared meaningfully. Two Set objects are equal if they contain the same elements.

The Properties class in java

The Properties class inherits from Hashtable and is part of JDK 1.0. Instances of Properties typically represent persistent values describing something such as system settings. For example, the System.getProperties() method returns a system properties table with various key/value pairs that describe the platform the program is running on.

The Properties class adds additional functionality that can be extremely useful. The Properties class represents a persistent list of properties. What exactly does this mean? The Properties class is designed to provide methods to store and load files containing key-value pairs as Strings. Properties files are simply key-value pairs where the key and value are separated by an "=" (name=Tom) and eack key-value pair is on a separate line. A Windows ini file is an example of a properties file. In many cases, XML files are replacing properties files but the simplicity of a properties file combined with its ease of use makes the Properties class still a very useful class.

Although the Properties file inherits the methods of the Hashtable, it is recommended that the Hashtable put method not be used as this may allow the insertion of non-String objects. Only Strings should be used as either a key or a value in a Properties object. A Properties object with a non-String in it will throw an exception if you attempt to store it to a file. A Properties object can contain another Properties object (specified in the constructor) which is used as the default keys if no matching key is found in the Properties object.

Methods in Property class

The Properties class provides several new methods:

  • Object setProperty(String key, String value) - Invokes the Hashtable put method. Although it returns an Object, the return should always be a String.
  • String getProperty(String key) - Returns the value found for the matching key. Null if no match is found.
  • String getProperty(String key, String defaultValue) - Returns the value found for the matching key.The defaultValue is returned if no match is found.
  • void list(PrintStream output) - Writes the Properties object out to the specified PrintStream.
  • void list(PrintWriter output) - Writes the Properties object out to the specified PrintWriter.
  • void load(InputStream input) - Loads data into the Properties object using the specified InputStream.Key-value pairs are assumed to be on separate lines and each kei is separated from its value by an equals sign ("="). In addition to the equals sign, a colon (":") or the first white space will be used as a separator when reading in a properties file.
  • void store(OutputStream output, String header) - Writes the Properties object out to the specified OutputStream. The header is written as a comment line at the beginning of the file. After the header line, another comment line is written containing the current date and time. A "#" is placed at the beginning of these lines to identify them as comments. The OutputStream will be flushed but will remain open. Any properties in the default Properties object are not written to the output.

Example of Properties class in java

Property class example in java

Here is an example of reading in a properties file, removing the password and printing out the reminder.
import java.util.*;
import java.io.*;

public class PropertyDemo {

public static void main(String[] args) 
                         throws Exception {

BufferedInputStream bStream = new BufferedInputStream
              (new FileInputStream("prefs.ini"));
Properties props = new Properties();
props.load(bStream);
props.remove("password");
props.list(System.out);
bStream.close();
}
} 

LinkedHashMap in java

New to J2SE 1.4, the LinkedHashMap class is used in exactly the same way as the HashMap class. It has no additional methods but it does have one additional constructor that we will discuss in a moment. The basic difference between HashMap and LinkedHashMap is that the LinkedHashMap maintains the order of the items added to the Map. It does this by maintaining a doubly linked list containing the hash and the original order of the items. According to Sun, the LinkedHashMap should run nearly as fast as the HashMap.

The LinkedHashMap has one additional constructor that takes an additional boolean parameter. This allows you to construct a LinkedHashMap that maintains items, not in the order that they are added to the Map but rather in the order in which they are accessed.

Example of LinkedHashMap

LinkedHashMap example in java

This example shows LinkedHashMap in java:

public class JavaLinkedHashMapExample {
public static void main(String[] args) {
//create object of LinkedHashMap
LinkedHashMap lHashMap = new LinkedHashMap();
//put the values
lHashMap.put("One", new Integer(1));
lHashMap.put("Two", new Integer(2));
//get the value
Object obj = lHashMap.get("One");
System.out.println(obj);
//iterate over linked hash map values
Collection c = lHashMap.values();

//obtain an Iterator for Collection
Iterator itr = c.iterator();



//iterate through LinkedHashMap values iterator
while(itr.hasNext())
System.out.println(itr.next());
}
}

Saturday, May 28, 2011

The IdenitityHashMap Class in java

The IdentityHashMap is also like the HashMap with the exception that a key is considered equal to another key only if they are pointing to the exact same object. Other implementations of Map use the equals( ) method to determine if two keys are equal. The IdentityHashMap uses the == comparator. Two keys (a and b) are considered equal if a == b. The IdentityhashMap should only be used in the cases where this functionality is required. It should not be used otherwise.

HashTable in java

Hashtable was part of the original java.util and is a concrete implementation of a Dictionary. However, Java 2 reengineered Hashtable so that it also implements the Map interface. Thus, Hashtable is now integrated into the collections framework. It is similar to HashMap, but is synchronized.

Like HashMap, Hashtable stores key/value pairs in a hash table. When using a Hashtable, you specify an object that is used as a key, and the value that you want linked to that key. The key is then hashed, and the resulting hash code is used as the index at which the value is stored within the table.

A hash table can only store objects that override the hashCode() and equals() methods that are defined by Object. The hashCode() method must compute and return the hash code for the object. Of course, equals() compares two objects. Fortunately, many of Java's built-in classes already implement the hashCode() method. For example, the most common type of Hashtable uses a String object as the key. String implements both hashCode() and equals().

Constructors of HashTable class

Hashtable( )
Hashtable(int size)
Hashtable(int size, float fillRatio)
Hashtable(Map m)

 

The first version is the default constructor. The second version creates a hash table that has an initial size specified by size. The third version creates a hash table that has an initial size specified by size and a fill ratio specified by fillRatio. This ratio must be between 0.0 and 1.0, and it determines how full the hash table can be before it is resized upward. Specifically, when the number of elements is greater than the capacity of the hash table multiplied by its fill ratio, the hash table is expanded. If you do not specify a fill ratio, then 0.75 is used. Finally, the fourth version creates a hash table that is initialized with the elements in m. The capacity of the hash table is set to twice the number of elements in m. The default load factor of 0.75 is used. The fourth constructor was added by Java 2.

 

Examples on HashTable


TreeMap in Java Collections

The TreeMap class guarantees that the keys in the Map will be sorted in ascending order by either the keys natural order or by a Comparator provided to the constructor of the TreeMap. TreeMap implements Map and SortedSet interfaces and extends AbstractMap. TreeMap keeps the balanced binary tree in sorted order by key.

Searching for an item in a TreeMap will be slower than in a HashMap because the hashing algorithm gives better performance than the compareTo() method which is used to locate items in a TreeMap.

 

Creating a TreeMap – Constructors for TreeMap

It has the following constructors. Here comp stands for Comparator, mp stands for Map, smp stands for SortedMap.

Result Constructor Description
tmap = new TreeMap() Creates new TreeMap. Keys sorted by natural order.
tmap = new TreeMap(comp) Creates new TreeMap using Comparator comp to sort keys.
tmap = new TreeMap(mp) Creates new TreeMap from Map mp using natural ordering.
tmap = new TreeMap(smp) Creates new TreeMap from SortedMap smp using key ordering from smp.


 

Methods in TreeMap

TreeMap adds the methods from Map and SortedMap. See the methods of these interfaces – Methods in Map interface, Methods in SortedMap interface.

So other than Map interface methods it has SortedMap interface Methods:

  • Object firstKey() - Gets the first key from the sorted Map.
  • Object lastKey() - Gets the last key from the sorted map.
  • SortedMap headMap(Object toKey) - Returns a view of the portion of this Map whose keys are less than toKey.
  • SortedMap tailMap(Object fromKey) - Returns a view of the portion of this Map whose keys are greater than or equal to fromKey.
  • SortedMap subMap(Object fromKey, Object toKey) - Returns a view of the portion of this Map whose starting key is greater than or equal to fromKey and whose ending key is less than toKey.

 

Example

TreeMap Example in java

TreeMap Example in java

This example covers tree-map example in java:

TreeMap tm = new TreeMap();
// Put elements to the map
tm.put("Kinshuk Chandra", new Double(3434.34));
tm.put("Himanshu Singh", new Double(123.22));
tm.put("Gaurav Mishra", new Double(1378.00));
tm.put("Mohit Mittal", new Double(99.22));
tm.put("Chitranshu Mishra", new Double(-19.08));
// Get a set of the entries
Set set = tm.entrySet();
// Get an iterator
Iterator i = set.iterator();
// Display elements
while(i.hasNext()) {
Map.Entry me = (Map.Entry)i.next();
System.out.print(me.getKey() + ": ");
System.out.println(me.getValue());
}
System.out.println();
// Deposit 1000 into My (Kinshuk Chandra's) account
double balance = ((Double)tm.get("Kinshuk Chandra")).doubleValue();
tm.put("Kinshuk Chandra", new Double(balance + 1000));
System.out.println("Kinshuk Chandra's new balance: " +
tm.get("Kinshuk Chandra"));

 

Output:

Chitranshu Mishra: -19.08
Gaurav Mishra: 1378.0
Himanshu Singh: 123.22
Kinshuk Chandra: 3434.34
Mohit Mittal: 99.22

Kinshuk Chandra's current balance: 4434.34


 

Notice that TreeMap sorts the keys. However, in this case, they are sorted by first name instead of last name. You can alter this behavior by specifying a comparator when the map is created.

The HashMap class in java

The HashMap class is the simplest implementation of the Map interface. The HashMap does not add any additional methods (other than clone) beyond those found in the Map interface.

Creating the HashMap in java

In addition to implemented the Map interface methods, HashMap has the following constructors.
Result Constructor Description
hmap = new HashMap() Creates a new HashMap with default initial capacity 16 and load factor 0.75.
hmap = new HashMap(initialCapacity) Creates a new HashMap with the specified initial int capacity.
hmap = new HashMap(initialCapacity, loadFactor) Creates a new HashMap with the specified capacity which will not exceed a specified (float) load factor.
hmap = new HashMap(mp) Creates a new HashMap with elements from the Map mp

 

Performance of the HashMap

The HashMap achieves good performance by using a hash to store the key in the Map. The hash allows fast lookup which means that the containKey( ) method will perform much better than the containsValue( ) method.

HashMaps will automatically grow when you add too many elements. However, growing requires copying, rehashing and rechaining, which affects its overall performance.
Performance of HashMap depends on two important factors that are

  • Initial Capacity and
  • Load Factor

Initial Capacity is the capacity at the time the HashMap is created. Load factor determines when to increase the capacity of the HashMap. The default load factor is 0.75.
Important Note: The initial capacity is not the actual number of elements you plan to store in HashMap. Say for example, if you set initial capacity of 100 and the load factor is 0.75, then the capacity of HashMap will be automatically increased when it reaches to 75 not 100.

Any Object used as a key in a HashMap must implement the hashCode( ) and equals( ) methods. See Part 2 of this series for a discussion of this issue.
The HashMap does not guarantee the order of the items in the Map and allows one null key. Duplicates are not permitted. The HashSet offers "constant time" performance for lookups involving the key and linear time for lookups based on value. This means that adding items to the Map will not cause significant performance degradation as long as lookups are done by the key. The performance of basic functions such as put, remove, get, etc is based on two factors which can be specified in the constructor of the HashMap, initial capacity and load factor.

Methods in HashMap

As discussed earlier, HashMap doesn't add any new methods to Map interface other than clone() method. So see – Map interface methods.

Example

Creating a HashMap in Java

Introduction to maps in java

A Map(in the API reference documentation)is an object that maps keys to values. A map cannot contain duplicate keys: Each key can map to at most one value.

These are the interfaces available for maps in java:

  • Map implemented by HashMap and TreeMap
  • SortedMap implemented by TreeMap.
  • Map.Entry which describes access methods to the key-value pairs.

Collection views for Maps for iteration

The Collection-view methods allow a Map to be viewed as a Collection in three ways:
  • keySet: the Set of keys contained in the Map.
  • values: The Collection of values contained in the Map. This Collection is not a Set, as multiple keys can map to the same value.
  • entrySet: The Set of key-value pairs contained in the Map. The Map interface provides a small nested interface called Map.Entry that is the type of the elements in this Set.

The Collection-views provide the only means to iterate over a Map.

Iterating over the keys in a Map

Here's an example illustrating the standard idiom for iterating over the keys in a Map:

for (Iterator i=m.keySet().iterator(); i.hasNext(); )
System.out.println(i.next());


Iterating over the values in Map

The idiom for iterating over values is analogous.

for (Iterator i=m.values().iterator(); i.hasNext(); )
System.out.println(i.next());


Iterating over the key value pairs

 

Here's the idiom for iterating over key-value pairs:

for (Iterator i=m.entrySet().iterator(); i.hasNext(); ) {
Map.Entry e = (Map.Entry) i.next();
System.out.println(e.getKey() +
": " + e.getValue());
}

When first presented with these idioms, many people worry that they may be slow because the Map has to create a new Collection object each time a Collection-view operation is called. Rest easy: This is not the case. There's no reason that a Map can't always return the same object each time it is asked for a given Collection-view. This is precisely what all of the JDK's Map implementations do.
With all three Collection-views, calling an Iterator's remove operation removes the associated entry from the backing Map (assuming the Map supports element removal to begin with). With the entrySet view, it is also possible to change the value associated with a key, by calling a Map.Entry's setValue method during iteration (again, assuming the Map supports value modification to begin with). Note that these are the only safe ways to modify a Map during iteration; the behavior is unspecified if the underlying Map is modified in any other way while the iteration is in progress.
The Collection-views support element removal in all its many forms: the remove, removeAll, retainAll, and clear operations, as well as the Iterator.remove operation. (Yet again, this assumes that the backing Map supports element removal.)
The Collection-views do not support element addition under any circumstances. It would make no sense for the keySet and values views, and it's unnecessary for the entrySet view, as the backing Map's put and putAll provide the same functionality.


Friday, May 27, 2011

SortedMap interface methods (java)

The SortedMap interface is used by TreeMap and adds additional methods to reflect that a TreeMap is sorted.
ResultMethodDescription
comp = comparator() Returns Comparator used to compare keys. null if natural ordering used (eg, String).
obj = firstKey() Key of first (in sorted order) element.
obj = lastKey() Key of last (in sorted order) element.
smp = headMap(obj) Returns SortedMap of all elements less than obj.
smp = tailMap(obj) Returns SortedMap of all elements greater than or equal to obj.
smp = subMap(fromKey, toKey) Returns SortedMap of all elements greater than or equal to fromKey and less than toKey.

Map.Entry interface methods (java)

Each element is a map has a key and value. Each key-value pair is saved in a java.util.Map.Entry object. A set of these map entries can be obtained by calling a map's entrySet() method. Iterating over a map is done by iterating over this set.
Assume in the following table that me is a Map.Entry object.
ResultMethod Description
obj = me.getKey() Returns the key from the pair.
objme.getValue(key) Returns the value from the Map pair.
objme.setValue(val) This is an optional operation and may not be supported by all Map.Entry objects. Sets the value of the pair, which modifies the Map which it belongs to. Returns the orginal value.

Map interface methods (java)


Here are some of the most useful Map methods. m is a Map, b is a boolean, i is an int, set is a Set, col is a Collection, key is an Object used as the key used to store a value, val is an Object stored as the value associated with the key.
ResultMethod Description
Adding key-value pairs to a map
obj = m.put(key, val) Creates mapping from key to val. It returns the previous value (or null) associated with the key.

m.putAll(map2) Adds all key-value entries from another map, map2.
Removing key-value pairs from a map

m.clear() Removes all elements from a Map
objm.remove(key) Deletes mapping from key to anything. Returns previous value (or null) associated with the key.
Retrieving information from the map
bm.containsKey(key) Returns true if m contains a key key
bm.containsValue(val) Returns true if m contains val as one of the values
objm.get(key) Returns value corresponding to key, or null if there is no mapping. If null has been stored as a value, use containsKey to see if there is a mapping.
bm.isEmpty() Returns true if m contains no mappings.
im.size() Returns number of mappings in m.
Retrieving all keys, values, or key-value pairs (necessary for iteration)
setm.entrySet() Returns set of Map.Entry values for all mappings.
setm.keySet() Returns Set of keys.
colm.values() Returns a Collection view of the values in m.

Map implementations in java

A number of classes implement the Map interface, including HashMap, TreeMap, LinkedHashMap, WeakHashMap, ConcurrentHashMap, and Properties. The most generally useful class is HashMap.
  • java.util.HashMap is implemented with a hash table. Access time is O(1). Entries are unsorted.
    – similar to HashTable but allows null keys and values
    – not thread safe
  • java.util.LinkedHashMap is implemented with a hash table. Access time is O(1). Entries are sorted in either entry order or order of last access, which is useful for implementing a LRU (least recently used) caching policy.
  • java.util.TreeMap is implemented as a balanced binary tree. Access time is O(log N). Entries are sorted. 
  • java.util.HashTable(old classes)
    – updated class from earlier Java versions
    – does not allow null keys or values
    – thread safe
  • java.util.WeakHashMap -
    – like HashMap
    – entry is automatically removed from HashMap if no more "ordinary" references to key
  • java.util.IdentityHashMap
  • java.util.EnumMap
  • java.util.Properties

Thursday, May 26, 2011

The ThreadGroup class in java

The ThreadGroup class manages groups of threads for Java applications. A ThreadGroup can contain any number of threads. The threads in a group are generally related in some way, such as who created them, what function they perform, or when they should be started and stopped.

ThreadGroups can contain not only threads but also other ThreadGroups. The top-most thread group in a Java application is the thread group named main. You can create threads and thread groups in the main group. You can also create threads and thread groups in subgroups of main. The result is a root-like hierarchy of threads and thread groups:

The ThreadGroup class has methods that can be categorized as follows:

Volatile keyword in java

Understanding volatile in java
To understand volatile, first you have to understand a little something about the Java memory model.
  • Each thread in Java takes place in a separate memory space, I mean its personal stack, but various threads share memory among them.
  • You need to use special mechanisms to guarantee that communication happens between these threads, as you would on a message passing system.
  • Memory writes that happen in one thread can "leak through" and be seen by another thread, but this is by no means guaranteed. Without explicit communication (i.e. using locks on the shared data), you can't guarantee which writes get seen by other threads, or even the order in which they get seen.
The Java volatile modifier guarantees that communication happens between threads. When one thread writes to a volatile variable, and another thread sees that write, the first thread is telling the second about all of the contents of memory up until it performed the write to that volatile variable. So if a variable is declared as volatile then is guaranteed that any thread which reads the field will see the most recently written value.

What is happens-before relation?
volatile’s job is to guarantee “happens-before” behavior. This means three things:
  1. Write operations are executed before read operations.
  2. Compilers are not allowed to re-order accesses to the field.
  3. Caches must be flushed before reading the field
Note
The keyword volatile will not perform any mutual exclusive lock on the variable. Most recent value is ensured because it ignores caching. So if a variable is declared volatile, it takes the value from the main memory, rather than cache and delivers the recent value or latest value.

As of Java 5 write access to a volatile variable will also update non-volatile variables which were modified by the same thread. This can also be used to update values within a reference variable, e.g. for a volatile variable person. In this case you must use a temporary variable person and use the setter to initialize the variable and then assign the temporary variable to the final variable. This will then make the address changes of this variable and the values visible to other threads.

Difference between volatile in old and new Java Memory Model
Pre-java 5, volatile had different meaning, but java developers changed its meaning. Lets look at the change:
Old java volatile New java volatile
A volatile variable cannot be cached. (same)
A volatile variable cannot be reordered with another variable but may be reordered with volatile variable. A volatile variable cannot be reordered. (notice the change)
Volatile observes happens-before-relationship.
See -

Process vs threads

The distinction between processes and threads is important.

  • Process: A process runs independently and isolated of other processes. It cannot directly access shared data in other processes. The resources of the process are allocated to it via the operating system, e.g. memory and CPU time.
  • Threads: threads are so called lightweight processes which have their own call stack but an access shared data. Every thread has its own memory cache. If a thread reads shared data it stores this data in its own memory cache. A thread can re-read the shared data, when this happens in Java will be explained in Java memory model part of this article.
Within a Java application you work with several threads to archive parallel processing or asynchronously behavior.

Wednesday, May 25, 2011

Common Class Loading Issues (java)

  • ClassNotFoundException
    • Thrown when an application tries to explicitly load a class using class name string and class (.class file) is not found in the classpath.
      Eg. Thrown when an application tries to load a class through its string name using:
      • The forName method in Class.
      • The findSystemClass method in ClassLoader.
      • The loadClass method in ClassLoader.

      By throwing a ClassNotFoundException, the class loader informs us that the bytecode required to define the class is not present in the locations where the class loader is looking for it. There may be classes in a system that cannot be seen by a class loader. This is because a class loader only sees classes that are loaded by itself or loaded by class loaders to which it has a reference. In the class loading delegation model, the classes that are visible to a class loader are those that are loaded by itself or loaded by its parent – in other words, a class loader cannot look down.
    • Can be easily checked by enabling verbose:class JVM argument

  • NoClassDefFoundError
    • Thrown if the ClassLoader instance tries to implicitly load in the definition of a class and no definition of the class could be found.
      The searched for class definition existed when the currently executing class was compiled but the definition can no longer be found. Essentially this means that a NoClassDefFoundError is thrown as a result of a unsuccessful implicit class load.
  • ClassCastException
    • Thrown as a result of incompatible types being found in a type comparison. It indicates that the code has attempted to cast an object to a subclass of which it is not an instance. (remember ClassLoader Namespace)
    • Two classes of the same fully qualified name are not equal to each other if they are loaded by different ClassLoaders. They cannot be cast to each other and such operations would result in a ClassCastException
  • UnsatisfiedLinkError
    It occurs during the resolving stage of the linking phase when a program tries to load an absent or misplaced native library.
  • ClassCircularityError
    It is thrown if a class if a class or interface could not be loaded because it would be its own superclass or superinterface.
  • ClassFormatError
    • This exception is thrown during the verification stage of the linking phase of class loading. The binary data can be malformed if the bytecodes have been changed --if the major or minor number has been changed, for instance. This could occur if the bytecodes had been deliberately hacked, for example, or if an error had occurred when transferring the class file over a network.
    • The only way to fix this problem is to obtain a corrected copy of the bytecodes, possibly by recompiling.


Chitika