Saturday, July 6, 2013

String (String Pool,Immutable,Other Concepts,String vs StringBuffer vs StringBuilder)


What is String literal pool:

There are two ways to create a String object in Java:
  • Using the new operator. For example,
    String str = new String("Hello");.
  • Using a string literal or constant expression). For example,
    String str="Hello"; (string literal) or
    String str="Hel" + "lo"; (string constant expression).            
     The creation of two strings with the same sequence of letters without the use of the new keyword will create pointers to the same String in the Java String literal pool. The String literal pool is a way Java conserves resources. 
    If we use the new keyword then String will not be placed in the String pool but then we can use String's intern() method to place that object in the String pool.
    Unfortunately, when you use
    String a=new String("Hello");
    a String object is created out of the String literal pool, even if an equal string already exists in the pool.
    Each time your code create a string literal, the JVM checks the string literal pool first. If the string already exists in the pool, a reference to the pooled instance returns. If the string does not exist in the pool, a new String object instantiates, then is placed in the pool. Java can make this optimization since strings are immutable and can be shared without fear of data corruption. For example
    public class Program
    {
        public static void main(String[] args)
        {
           String str1 = "Hello";  
           String str2 = "Hello"; 
           System.out.print(str1 == str2);
        }
    }
    The result is
    true
     
    There is a table always maintaining a single reference 
    to each unique String object in the global string literal pool  ever 
    created by an instance of the runtime in order to optimize space.  That 
    means that they always have a reference to String objects in string 
    literal pool, therefore,  the string objects in the string literal pool 
    not eligible for garbage collection.
     
     
    Why String is Immutable or Final in JAVA:
    
     Security,Thread safety and String pool being primary reason of making String immutable,And for making immutable you need to make a class final also.
    1) Imagine StringPool facility without making string immutable , its not possible at all because in case of string pool one string object/literal e.g. "Test" has referenced by many reference variables , so if any one of them change the value others will be automatically gets affected i.e. lets say

    String A = "Test"
    String B = "Test"

    Now String B called "Test".toUpperCase() which change the same object into "TEST" , so A will also be "TEST" which is not desirable.

    2)String has been widely used as parameter for many Java classes e.g. for opening network connection, you can pass hostname and port number as string , you can pass database URL as string for opening database connection, you can open any file in Java by passing name of file as argument to File I/O classes.

    In case, if String is not immutable, this would lead serious security threat , I mean some one can access to any file for which he has authorization, and then can change the file name either deliberately or accidentally and gain access of those file. Because of immutability, you don't need to worry about those kind of threats. This reason also gel with, Why String is final in Java, by making java.lang.String final, Java designer ensured that no one overrides any behavior of String class.

    3)Since String is immutable it can safely shared between many threads ,which is very important for multithreaded programming and to avoid any synchronization issues in Java, Immutability also makes String instance thread-safe in Java, means you don't need to synchronize String operation externally. Another important point to note about String is memory leak caused by SubString, which is not a thread related issues but something to be aware of.

    4) Another reason of Why String is immutable in Java is to allow String to cache its hashcode , being immutable String in Java caches its hashcode, and do not calculate every time we call hashcode method of String, which makes it very fast as hashmap key to be used in hashmap in Java.  This one is also suggested by  Jaroslav Sedlacek in comments below. In short because String is immutable, no one can change its contents once created which guarantees hashCode of String to be same on multiple invocation.

    5) Another good reason of Why String is immutable in Java suggested by Dan Bergh Johnsson on comments is: The absolutely most important reason that String is immutable is that it is used by the class loading mechanism, and thus have profound and fundamental security aspects. Had String been mutable, a request to load "java.io.Writer" could have been changed to load "mil.vogoon.DiskErasingWriter"

    Java String interview Question

    1) What is String in Java ? Is String is data type?
    String in Java is not a primitive data type like int, long or double.  String is a class or in more simple term a user defined type. String is defined in java.lang package and wrappers its content in a character array.
    2) Why String is final in Java
    String is final by design in Java, some of the points which makes sense why String is final is Security, optimization and to maintain pool of String in Java.
    3) What is Difference between String and StringBuffer in Java
    Though String and Stringbuffer are two different class they are used in context of concatenating two Strings, Since String is immutable in Java every operation which changes String produces new String, which can be avoided by using Stringbuffer.
    4) What is difference in String on C and Java
    Well C String and Java String are completely different to each other, C String is a null terminated character array while String in Java is an Object
    5) Why char array is better than String for storing password?
    This String interview question is debatable and you might not agree with interviewer but this is also a chance to show that how deep and differently you can think of. One of the reason which people give Why you should store password in char array over String is related to immutability, since its not possible to remove erase contents of String but you can erase contents of char array. See Why char array preferred over String for password for complete discussion.
    6) How do you compare two String in Java ?
    There are multiple ways to compare two String like equals() method, equalsIgnoreCase() etc.Main thing which interviewer checks is that whether candidate mentioned equality operator or not "==", comparing String with equality operator is common mistake.
    7) Can we compare String using == operator? What is risk?
    Equality operator is used to compare primitives and equals() method should be used to compare objects. As we have seen in pitfall of autoboxing in Java that how equality operator can cause subtle issue while comparing primitive to Object, any way String is free from that issue because it doesn't have corresponding primitive type and not participate in autoboxing.In short always use equals method in Java to check equality of two String object.
    8) How substring method work in Java
    Substring shares same character array as original String which can create memory leak if original String is quite big and not required to retain in memory but unintentionally retained by substring which is very small in size and prevents large array from begin claimed during Garbage collection in Java. See How Substring works in Java for more details.
    10)What is String pool in Java
    Another tough Java question asked in  String interview. String pool is a special storage area in Java heap, mostly located on PerGen space, to store String literals like "abc". When Java program creates a new String using String literal, JVM checks for that String in pool and if String literal is already present in pool than same object is returned instead of creating a whole new object. String pool check is only performed when you create String as literal, if you create String using new() operator, a new String object will be created even if String with same content is available in pool.
    9) What does intern() method do in Java
    String object crated by new() operator is by default not added in String pool as opposed to String literal. intern() method allows to put an String object into pool.
    11) Does String is thread-safe in Java
    Since String is immutable, it is thread-safe and it can be shared between multiple thread without external synchronization.

     String vs StringBuffer vs StringBuilder:
    Many Java beginners not aware that String is immutable and final in Java and every modification in String result creates a new String object. So How do you manipulate String in Java without creating String garbage? StringBuilder and StringBuffer is answer of this question. StringBuffer is old class but StringBuilder is newly added in Java 5 along with major improvements like Enum, Generics, varargs methods and Autoboxing in Java.


    Differences between String, StringBuffer and StringBuilder in Java

    String in Java

    Before looking difference between String and StringBuffer or StringBuilder let’s see some fundamental properties of String Class in Java

    1) String is immutable in Java:  String is by design immutable in Java.Immutability offers lot of benefit to the String class e.g. his hashcode value can be cached which makes it a faster hashmap key and one of the reason why String is a popular key in HashMap. Because String is final it can be safely shared between multiple threads  without any extra synchronization.

    2) "+" operator is overloaded for String and used to concatenated two string. Internally "+" operation is implemented using either StringBuffer or StringBuilder.

    3) Strings are backed up by character Array and represented in UTF-16 format. By the way this behavior can cause memory leak in String because same character array is shared between source String and SubString which can prevent source String from being garbage collected.

    4) String class overrides equals() and hashcode() method and two Strings are considered to be equal if they contain exactly same character in same order and in same case. If you want ignore case comparison of two strings consider using equalsIgnoreCase() method. Another worth noting point is that equals method must be consistent with compareTo() method for String because SortedSet and SortedMap e.g. TreeMap uses compareTo method to compare String in Java.

    5) toString() method provides String representation of any object and its declared in Object class and its recommended for other class to implement this and provide String representation.

    6) In Java you can create String from char array, byte array, another string, from StringBuffer or from StringBuilder. Java String class provides constructor for all of these.

    Differences between String and StringBuffer in Java

    Main difference between String and StringBuffer is String is immutable while StringBuffer is mutable means you can modify a StringBuffer object once you created it without creating any new object. This mutable property makes StringBuffer an ideal choice for dealing with Strings in Java. You can convert a StringBuffer into String by its toString() method.

    Difference between StringBuilder and StringBuffer in Java

    StringBuffer is very good with mutable String but it has one disadvantage all its public methods are synchronized which makes it thread-safe but same time slow. In JDK 5 they provided similar class called StringBuilder in Java which is a copy of StringBuffer but without synchronization. Try to use StringBuilder whenever possible it performs better in most of cases than StringBuffer class. You can also use "+" for concatenating two string because "+" operation is internal implemented using either StringBuffer or StringBuilder in Java.

Final keyword in JAVA.Can be used with variables,methods and classes:

Final is a keyword or reserved word in java and can be applied to member variables, methods, class and local variables in Java.
Final variables are often declare with static keyword in java and treated as constant. Here is an example of final variable in Java

public static final String LOAN = "loan";
LOAN = new String("loan") //invalid compilation error

Final methods can not be overridden in subclasses.Final methods are faster than non-final methods because they are not required to be resolved during run-time and they are bonded on compile time.
 
Final class is complete in nature and can not be sub-classed or inherited. Several classes in Java are final e.g. String, Integer and other wrapper classes.

Benefits of final keyword in Java

1. Final keyword improves performance. Not just JVM can cache final variable but also application can cache frequently use final variables.
2. Final variables are safe to share in multi-threading environment without additional synchronization overhead.
3. Final keyword allows JVM to optimized method, variable or class.

Important points on final in Java

1. Final keyword can be applied to member variable, local variable, method or class in Java.
2. Final member variable must be initialized at the time of declaration or inside constructor, failure to do so will result in compilation error.

3. You can not reassign value to final variable in Java.

4. Local final variable must be initializing during declaration.

5. Only final variable is accessible inside anonymous class in Java.

6. Final method can not be overridden in Java.

7. Final class can not be inheritable in Java.

10. All variable declared inside java interface are implicitly final.

12. Final methods are bonded during compile time also called static binding.

13. Final variables which is not initialized during declaration are called blank final variable and must be initialized on all constructor either explicitly or by calling this(). Failure to do so compiler will complain as "final variable (name) might not be initialized".

16. Making a collection reference variable final means only reference can not be changed but you can add, remove or change object inside collection. For example:

private final List Loans = new ArrayList();
list.add(“home loan”);  //valid
list.add("personal loan"); //valid
loans = new Vector();  //not valid

Friday, July 5, 2013

JVM Internals

Each time a Java Application is executed then an instance of JVM ,responsible for its running,is created.A JVM instance is described in terms of subsystems, memory areas, data types, and instructions.The block diagram given below,depicts a view of Internal Architecture of JVM :


While executing a Java program,a JVM requires memory for storing bytecodes,objects ,local variables,method arguments,return values,intermediate computational results and JVM does that memory management on several runtime data areas.
Each instance of the Java virtual machine has one method area and one heap. These areas are shared by all threads running inside the virtual machine. When the virtual machine loads a class file, it parses information about a type from the binary data contained in the class file. It places this type information into the method area. As the program runs, the virtual machine places all objects the program instantiates onto the heap.
A thread's Java stack stores the state of Java (not native) method which includes its local variables, the parameters with which it was invoked, its return value (if any), and intermediate calculations. The state of native method invocations is stored in an implementation-dependent way in native method stacks, in registers or other implementation-dependent memory areas.
A thread's Java stack stores the state of Java (not native) method which includes its local variables, the parameters with which it was invoked, its return value (if any), and intermediate calculations. The state of native method invocations is stored in an implementation-dependent way in native method stacks, in registers or other implementation-dependent memory areas.

Class Loader And Its Responsibilities:
The class loaders can be of two types: a bootstrap or primordial class loader and user defined class loaderEach JVM has a bootstrap class loader which loads trusted classes , including classes from Java API.JVM specs do not tell how to locate these classes and is left to implementation designers.

Heap And Stack:
The heap is the part of memory of JVM where all objects reside.
The stack is consisted of stack frames.When a thread invokes a method,the JVM pushes a new frame onto that thread's Java stack.Each stack frame is consisted of operand stack and the local variable array.All arguments,local variables,intermediate computations and return values if any are kept in these stack corresponding to the method invoked.The stack frame on the top of the stack is called the active stack frame,which is the current place of execution.When the method completes, the virtual machine pops and discards the frame for that method.

How Java Program executes inside JVM:
When JVM executes a Java application, a runtime instance of JVM is born.This runtime instance invoke main() method of Java application.The main() method of an application serves as the starting point for that application's initial thread. The initial thread can in turn fire off other threads.

This thread has a program counter(PC) and Java stack.Whenever main() method is invoked, a stack frame is pushed onto the stack,this then becomes the active tack frame.The program counter in the new Java stack frame will point to the beginning of the method.

There is only one heap corresponding to an instance of JVM and all objects created are stored here.This heap is shared by all threads created in an application.

Inside the Java virtual machine, threads come in two flavors: daemon and non- daemon. A daemon thread is ordinarily a thread used by the virtual machine itself, such as a thread that performs garbage collection. The application, however, can mark any threads it creates as daemon threads. The initial thread of an application--the one that begins at main()--is a non- daemon thread.

A Java application continues to execute (the virtual machine instance continues to live) as long as any non-daemon threads are still running. When all non-daemon threads of a Java application terminate, the virtual machine instance will exit. If permitted by the security manager, the application can also cause its own demise by invoking the exit() method of class Runtime or System.

When main() returns,it terminates the application's only non-daemon thread, which causes the virtual machine instance to exit. 

How JVM performs Thread synchronization:
JVM associates a lock with an object or a class to achieve mutilthreading. A lock is like a token or privilege that only one thread can "possess" at any one time.
The JVM uses locks in conjunction with monitors. A monitor is basically a guardian in that it watches over a sequence of code, making sure only one thread at a time executes the code.Each monitor is associated with an object reference. It is the responsibility of monitor to watch an arriving thread must obtain a lock on the referenced object.
In Java language terminology, the coordination of multiple threads that must access shared data is called synchronization. The language provides two built-in ways to synchronize access to data: with synchronized statements or synchronized methods.
For an instance method, the JVM acquires the lock associated with the object upon which the method is being invoked. For a class method, it acquires the lock associated with the class to which the method belongs. After a synchronized method completes, whether it completes by returning or by throwing an exception, the lock is released.
Two opcodes, monitorenter and monitorexit are used by JVM for accomplishing this task.

How JVM performs Garbage Collection:
Whenever a reference to an object on heap lies dangling or no longer in use by an active program then it becomes eligible for being garbage collected by JVM.JVM specifications do not force any specific kind of garbage collection algorithm though there are several algorithms like reference counting,tracing,compacting,copying,generational etc. in place.
Try using -Xaprof to get a profile of the allocations (objects and sizes) of your application.

Also try -agentlib:hprof=heap=all (or other option, try -agentlib:hprof=help for a list) 

An application has running lot of threads and running out of memory.WHY?:
You may be running into a problem with the default stack size for threads. In Java SE 6, the default on Sparc is 512k in the 32-bit VM, and 1024k in the 64-bit VM. On x86 Solaris/Linux it is 320k in the 32-bit VM and 1024k in the 64-bit VM.

On Windows, the default thread stack size is read from the binary (java.exe). As of Java SE 6, this value is 320k in the 32-bit VM and 1024k in the 64-bit VM.

You can reduce your stack size by running with the -Xss option. For example:

java -server -Xss64k

Note that on some versions of Windows, the OS may round up thread stack sizes using very coarse granularity. If the requested size is less than the default size by 1K or more, the stack size is rounded up to the default; otherwise, the stack size is rounded up to a multiple of 1 MB.

64k is the least amount of stack space allowed per thread.

Difference between JRE, JVM and JDK:
A Java Runtime Environment (JRE) is a prerequisite for running Java applications on any computer.A JRE contains a Java Virtual Machine(JVM),all standard,core java classes and runtime libraries. It does not contain any development tools such as compiler, debugger, etc. JDK(Java Development Kit) is a whole package required to Java Development which essentially contains JRE+JVM,and tools required to compile and debug,execute Java applications.

Wednesday, July 6, 2011

JAVA:Collections-Some Good Basic Questions

What is HashMap and Map?

Map is Interface and Hashmap is class that implements this interface.

What is the significance of ListIterator?

Or

What is the difference b/w Iterator and ListIterator?

Iterator : Enables you to cycle through a collection in the forward direction only, for obtaining or removing elements

ListIterator : It extends Iterator, allow bidirectional traversal of list and the modification of elements

Difference between HashMap and HashTable? Can we make hashmap synchronized?

1. The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls. (HashMap allows null values as key and value whereas Hashtable doesn’t allow nulls).
2. HashMap does not guarantee that the order of the map will remain constant over time.
3. HashMap is non synchronized whereas Hashtable is synchronized.
4. Iterator in the HashMap is fail-safe while the enumerator for the Hashtable isn't.

Note on Some Important Terms
1)Synchronized means only one thread can modify a hash table at one point of time. Basically, it means that any thread before performing an update on a hashtable will have to acquire a lock on the object while others will wait for lock to be released.

2)Fail-safe is relevant from the context of iterators. If an iterator has been created on a collection object and some other thread tries to modify the collection object "structurally”, a concurrent modification exception will be thrown. It is possible for other threads though to invoke "set" method since it doesn’t modify the collection "structurally”. However, if prior to calling "set", the collection has been modified structurally, "IllegalArgumentException" will be thrown.

HashMap can be synchronized by

Map m = Collections.synchronizeMap(hashMap);

What is the difference between set and list?

A Set stores elements in an unordered way and does not contain duplicate elements, whereas a list stores elements in an ordered way but may contain duplicate elements.

Difference between Vector and ArrayList? What is the Vector class?

Vector is synchronized whereas ArrayList is not. The Vector class provides the capability to implement a growable array of objects. ArrayList and Vector class both implement the List interface. Both classes are implemented using dynamically resizable arrays, providing fast random access and fast traversal. In vector the data is retrieved using the elementAt() method while in ArrayList, it is done using the get() method. ArrayList has no default size while vector has a default size of 10. when you want programs to run in multithreading environment then use concept of vector because it is synchronized. But ArrayList is not synchronized so, avoid use of it in a multithreading environment.

What is an Iterator interface? Is Iterator a Class or Interface? What is its use?

The Iterator is an interface, used to traverse through the elements of a Collection. It is not advisable to modify the collection itself while traversing an Iterator.

What is the Collections API?

The Collections API is a set of classes and interfaces that support operations on collections of objects.
Example of classes: HashSet, HashMap, ArrayList, LinkedList, TreeSet and TreeMap.
Example of interfaces: Collection, Set, List and Map.

What is the List interface?

The List interface provides support for ordered collections of objects.

How can we access elements of a collection?

We can access the elements of a collection using the following ways:
1.Every collection object has get(index) method to get the element of the object. This method will return Object.
2.Collection provide Enumeration or Iterator object so that we can get the objects of a collection one by one.

What is the Set interface?

The Set interface provides methods for accessing the elements of a finite mathematical set. Sets do not allow duplicate elements.

What’s the difference between a queue and a stack?

Stack is a data structure that is based on last-in-first-out rule (LIFO), while queues are based on First-in-first-out (FIFO) rule.

What is the Map interface?

The Map interface is used associate keys with values.

What is the Properties class?

The properties class is a subclass of Hashtable that can be read from or written to a stream. It also provides the capability to specify a set of default values to be used.

Which implementation of the List interface provides for the fastest insertion of a new element into the middle of the list?

a. Vector
b. ArrayList
c. LinkedList
d. None of the above

ArrayList and Vector both use an array to store the elements of the list. When an element is inserted into the middle of the list the elements that follow the insertion point must be shifted to make room for the new element. The LinkedList is implemented using a doubly linked list; an insertion requires only the updating of the links at the point of insertion. Therefore, the LinkedList allows for fast insertions and deletions.

How can we use hashset in collection interface?

This class implements the set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the Null element.

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets.

What are differences between Enumeration, ArrayList, Hashtable and Collections and Collection?

Enumeration: It is series of elements. It can be use to enumerate through the elements of a vector, keys or values of a hashtable. You can not remove elements from Enumeration.

ArrayList: It is re-sizable array implementation. Belongs to 'List' group in collection. It permits all elements, including null. It is not thread -safe.

Hashtable: It maps key to value. You can use non-null value for key or value. It is part of group Map in collection.

Collections: It implements Polymorphic algorithms which operate on collections.

Collection: It is the root interface in the collection hierarchy.

What is difference between array & arraylist?

An ArrayList is resizable, where as, an array is not. ArrayList is a part of the Collection Framework. We can store any type of objects, and we can deal with only objects. It is growable. Array is collection of similar data items. We can have array of primitives or objects. It is of fixed size. We can have multi dimensional arrays.

Array: can store primitive ArrayList: Stores object only

Array: fix size ArrayList: resizable

Array: can have multi dimensional

Array: lang ArrayList: Collection framework

Can you limit the initial capacity of vector in java?

Yes you can limit the initial capacity. We can construct an empty vector with specified initial capacity

public vector(int initialcapacity)

What method should the key class of Hashmap override?

The methods to override are equals() and hashCode().

What is the difference between Enumeration and Iterator?

The functionality of Enumeration interface is duplicated by the Iterator interface. Iterator has a remove() method while Enumeration doesn't. Enumeration acts as Read-only interface, because it has the methods only to traverse and fetch the objects, where as using Iterator we can manipulate the objects also like adding and removing the objects.

So Enumeration is used when ever we want to make Collection objects as Read-only.

JAVA:Fail fast and Fail safe Iteratotrs

A Fail Fast Iterator is an iterator that attempts to raise an error if the sequence of elements processed by the iterator is changed during iteration.
Fail-safe means, The ability of a system to fail but not produce a catastrophic result.

An iterator is considered fail-fast if it throws a ConcurrentModificationException under either of the following two conditions:

1. In multithreaded processing: if one thread is trying to modify a Collection while another thread is iterating over it.

2. In single-threaded or in multithreaded processing: if after the creation of the Iterator, the container is modified at any time by any method other than the Iterator's own remove or add methods.

Note in particular what is implied by the second condition: After we create a container's iterator, during a loop that iterates over the container we must only use the remove (and when applicable add) methods defined for the iterator and that we must NOT use the same methods defined for the container itself. To illustrate this point, suppose we declare and initialize a List in the following manner

List list = new ArrayList();

list.add("Peter");

list.add("Paul");

list.add("Mary");

Let's say we wish to iterate over this list. We'd need to declare a ListIterator as follows:

ListIterator iter = list.listIterator();

Having created this iterator, we could now set up a loop like:

while(iter1.hasNext()){

String str = iter1.next();

// do something with str

}

Because iter is fail-fast, we are not allowed to invoke List's add or remove methods inside the loop. Inside the loop, we are only allowed to use ListIterator's add and remove methods. This makes sense because it is the Iterator object that knows where it is in a List as the List is being scanned. The List object itself would have no idea of that.

The Iterators supported by all the work-horse container classes, such as ArrayList, LinkedList, TreeSet, and HashSet, are fail-fast. The Iterator type retrofitted to the older container class Vector is also fail-fast. For associative containers, such as HashMap and the older HashTable, the Iterator type for the Collections corresponding to either the keys or the values or the pairs are fail-fast with respect to the container itself. That means that even if you are iterating over, say, just the keys of the container, any illegal concurrent modifications to the underlying container would be detected.

One final note regarding iterators versus enumerations: It is also possible to use an Enumeration object returned by the elements() method for iterating over the older container types such as Vector. However, Enumerations do not provide a fail-fast method. On the other hand, the more modern Iterator returned by a Vector's iterator() and listIterator() methods are fail-fast. Hence, iterators are recommended over enumerations for iterating over the elements of the older container types.

A PRACTICAL APPROACH----------->Iterators can be designed so that they are fail fast or fail safe. Depending on the underlying implementation of the Iterator, a ConcurrentModificationException is thrown if the Collection is modified while Iterating over the data structure. It pays to understand how an Iterator will behave under both conditions. Lets try to implement fail fast Vs fail safe iterators of our own.

Our data structure for this example is pretty simple. It defines an interface that abstracts set and get operations on a structure. How the underlying classes handle invalid set operations or the size of the structure is implementation dependent

A data structure interface:

1
2
3
4
5
6
public interface Data<T> extends Iterable<T>
{
    int size();
    T getElement(int position);
    void setElement(int position, T t);
}

An underlying implementation of such an Interface, could be say an array of Integers whose size is fixed. Invalid indexes on bounds are not allowed and the internal structure will not grow or shrink. An implementation is given below

An array of integers implementing the interface:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class ArrayOfIntegers implements Data<Integer>
{
    private static int DEFAULT_SIZE = 1024;
    private int mods = 0;
 
    private Integer[] integers = new Integer[DEFAULT_SIZE];
 
    @Override
    public Integer getElement(int position)
    {
        checkRange(position);
        return integers[position];
    }
 
    @Override
    public void setElement(int position, Integer integer)
    {
        checkRange(position);
        mods++;
        integers[position] = integer;
    }
 
    @Override
    public int size()
    {
        return integers.length;
    }
 
    @Override
    public Iterator<Integer> iterator()
    {
        // return new FailFastIter();
        // return new NoFailIter();
        return null;
    }
 
    private void checkRange(int position)
    {
        if (position > DEFAULT_SIZE || position < 0)
        {
            throw new ArrayIndexOutOfBoundsException(position);
        }
    }
 
    // Iterator implementations go here as a private class
}

If we wanted to Iterate over the ArrayOfIntegers structure, there are 2 ways to do it. Either ensure that the underlying data structure Integer[] integers is not modified while we iterate over ArrayOfIntegers, or make a copy of Integer[] integers so that any changes made to the internal structure will not affect the caller in any way. Let us look at 2 private Iterator classes that we can place into the ArrayOfIntegers class that will help us achieve both flavors of Iteration

Fail fast:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
private class FailFastIter implements Iterator<Integer>
{
    int currentIndex = 0;
    int check = -1;
    int size = integers.length;
 
    public FailFastIter()
    {
        check = mods;
    }
 
    @Override
    public boolean hasNext()
    {
        checkForModification();
        if (currentIndex < size)
        {
            return true;
        }
        return false;
    }
 
    @Override
    public Integer next()
    {
        checkForModification();
        Integer result = integers[currentIndex];
        currentIndex++;
        return result;
    }
 
    @Override
    public void remove()
    {
        throw new UnsupportedOperationException();
    }
 
    private void checkForModification()
    {
        if (check != mods)
        {
            throw new ConcurrentModificationException();
        }
    }
}

The fail fast Iterator in this example, refers to the internal data structure directly. Every modification to the internal structure is tracked using the ‘mods‘ variable. Our iterator stores this value when it was initially created using the ‘check‘ variable. Both variables are compared every time the hasNext() or next() methods are called. If they are unequal then it means that the underlying structure was changed. This is when the code throws a ConcurrentModificationException

Fail safe:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
private class NoFailIter implements Iterator<Integer>
{
    int currentIndex = 0;
    Integer[] internal = Arrays.copyOf(integers, size());
    int internalSize = -1;
 
    public NoFailIter()
    {
        internalSize = internal.length;
    }
 
    @Override
    public boolean hasNext()
    {
        if (currentIndex < internalSize)
        {
            return true;
        }
        return false;
    }
 
    @Override
    public Integer next()
    {
        if (hasNext())
        {
            Integer result = internal[currentIndex];
            currentIndex++;
            return result;
        }
        else
        {
            throw new NoSuchElementException();
        }
    }
 
    @Override
    public void remove()
    {
        throw new UnsupportedOperationException();
    }
}

The fail safe iterator makes a copy of the internal array data structure and uses it to iterate over the elements. This prevents any concurrent modification exceptions from being thrown if the underlying data structure changes. Of course, the overhead of copying the entire array is introduced. Both implementation can be tested using a program

Iterator test for both iterators:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class IterTest
{
    public static void main(String... args)
    {
        new IterTest().go();
    }
 
    public void go()
    {
        Data<Integer> dataArray = new ArrayOfIntegers();
        for (int iCounter = 0; iCounter < 100; iCounter++)
        {
            dataArray.setElement(iCounter, iCounter);
        }
        Iterator<Integer> iterator = dataArray.iterator();
        while (iterator.hasNext())
        {
            System.out.println(iterator.next());
            dataArray.setElement(1, 12);
        }
    }
}

By changing the Iterator implementation that the iterator() method returns, this test program will either throw a ConcurrentModificationException or iterate over all the elements without knowing what changed under the hood.

It makes sense to throw ConcurrentModificationException from an Iterator in certain cases. Under other scenarios you just don’t care if the Iterator will fail or survive an internal structure change. Taking a leaf out of the java Collection API, take a look at the Iterator behavior of an ArrayList Vs that of a CopyOnWriteArrayList.

Iterator test for 2 iterators within the JDK API:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class IterTest2
{
    public static void main(String... args)
    {
        new IterTest2().go();
    }
 
    public void go()
    {
        List<String> arList = new ArrayList<String>();
        List<String> copyList = new CopyOnWriteArrayList<String>();
        populate(arList);
        populate(copyList);
        iterate(arList);
        iterate(copyList);
    }
 
    private void populate(List<String> list)
    {
        for (int iCounter = 0; iCounter < 100; iCounter++)
        {
            list.add(new Integer(iCounter).toString());
        }
    }
 
    private void iterate(List<String> list)
    {
        try
        {
            for (String x : list)
            {
                System.out.println(x);
                list.add(x);
            }
        }
        catch (RuntimeException e)
        {
            e.printStackTrace();
        }
    }
}

The CopyOnWriteArrayList does not fail when the internal structure changes, but ArrayList does. This example better highlights the problem of fail fast Vs fail safe iterators. The next time your write a custom iterator for your classes, consider this decision.

Friday, July 1, 2011

JAVA:Static class declarations (Can a class -- inner or outer -- be declared static?)

Q: Can a class (whether an inner or outer class) be declared static?

Astatic means "one per class".

In order to understand the use of the static keyword in class declaration, we need to understand the class declaration itself. You can declare two kinds of classes: top-level classes and inner classes.

Top-level classes

You declare a top-level class at the top level as a member of a package. Each top-level class corresponds to its own java file sporting the same name as the class name.

A top-level class is by definition already top-level, so there is no point in declaring it static; it is an error to do so. The compiler will detect and report this error.

Inner classes

You define an inner class within a top-level class. Depending on how it is defined, an inner class can be one of the following four types:

1. Anonymous. Anonymous classes are declared and instantiated within the same statement. They do not have names, and they can be instantiated only once.

The following is an example of an anonymous class:

okButton.addActionListener( new ActionListener(){
public void actionPerformed(ActionEvent e){
dispose();
} });
Because an anonymous class doesn't have a normal class declaration where it's possible to use static, it cannot be declared static.

2. Local. Local classes are the same as local variables, in the sense that they're created and used inside a block. Once you declare a class within a block, it can be instantiated as many times as you wish within that block. Like local variables, local classes aren't allowed to be declared public, protected, private, or static.

Here's a code example:

//some code block .......{    class ListListener implements ItemListener {
List list;
public ListListener(List l) {
list = l; }
public void itemStateChanged(ItemEvent e) {
String s = l.getItemSelected();
doSomething(s);
}
}
List list1 = new List();
list list2 = new List();
list1.addItemListener(new ListListener(list1));
list2.addItemListener(new ListListener(list2));
}
3. Member. Member classes are defined within the body of a class. You can use member classes anywhere within the body of the containing class. You declare member classes when you want to use variables and methods of the containing class without explicit delegation.

The member class is the only class that you can declare static. When you declare a member class, you can instantiate that member class only within the context of an object of the outer class in which this member class is declared. If you want to remove this restriction, you declare the member class a static class.

When you declare a member class with a static modifier, it becomes a nested top-level class and can be used as a normal top-level class as explained above.

4. Nested top-level. A nested top-level class is a member classes with a static modifier. A nested top-level class is just like any other top-level class except that it is declared within another class or interface. Nested top-level classes are typically used as a convenient way to group related classes without creating a new package.

If your main class has a few smaller helper classes that can be used outside the class and make sense only with your main class, it's a good idea to make them nested top-level classes. To use the nested top-level class, write: TopLevelClass.NestedClass.

See the following example:

public class Filter {  
Vector criteria = new Vector();
public addCriterion(Criterion c) {
criteria.addElement(c); }
public boolean isTrue(Record rec) {
for(Enumeration e=criteria.elements();
e.hasMoreElements();) {
if(! ((Criterion)e.nextElement()).isTrue(rec))
return false; }
return true; }
public static class Criterion {
String colName, colValue;
public Criterion(Stirng name, String val) {
colName = name; colValue = val; }
public boolean isTrue(Record rec) {
String data = rec.getData(colName);
if(data.equals(colValue)) return true;
return false;
} } }
And when you want to use it:
Filter f = new Filter();
f.addCriterion(new Filter.Criterion("SYMBOL", "SUNW"));
f.addCriterion(new Filter.Criterion("SIDE", "BUY"));
..... if(f.isTrue(someRec)) //do some thing .....
One important note: The static keyword does not do to a class declaration what it does to a variable or a method declaration.