Tuesday, December 2, 2014

Write a program for deadlock


class Resource1 extends Thread {
  public void run() {
    System.out.println("Resource1" + getName());
    synchronized (Resource1.class) {
      try {
        Thread.sleep(10);
      }
      catch (InterruptedException e) {
        e.printStackTrace();
      }
      synchronized (Resource2.class) {
      }
    }
  }
}
class Resource2 extends Thread {
  public void run() {
    System.out.println("Resource2" + getName());
    synchronized (Resource2.class) {
      try {
        Thread.sleep(10);
      }
      catch (InterruptedException e) {
        e.printStackTrace();
      }
      synchronized (Resource1.class) {
      }
    }
  }
}
public class Deadlock_example {
  public static void main(String[] args) {
    Resource1 r1 = new Resource1();
    Resource2 r2 = new Resource2();
    r1.start();
    r2.start();
  }
}

Count the number of chars in string..

public class Countnumber {
  public static void main(String args[]){
    String s = "aabbbccccdddddeeeeeeffffffffff";
    Map<Character, Integer> m =new HashMap<Character, Integer>();
    char c;
   
    int count = 1;
    for(int i= 0;i<s.length();i++){
     
      c = s.charAt(i);
      if(m.containsKey(c)){
        count = (int) m.get(c);
        count++;
      }else{
        count = 1;
      }
      m.put(c, count);
    }
    Iterator it = m.entrySet().iterator();
    while (it.hasNext()) {
        Map.Entry pairs = (Map.Entry)it.next();
        System.out.println(pairs.getKey() + " = " + pairs.getValue());
    }
    for(Map.Entry<Character, Integer> entry : m.entrySet()){
      System.out.println(entry.getKey() + " = " + entry.getValue());
    }
  }
}
O/p  ::
f = 10
d = 5
e = 6
b = 3
c = 4
a = 2

Green Vs Native Threads

Green threads Will function on systems that don't support OS level threads.

Another advantage of native threads is that multiple processes would execute in parallel in a multi-core machine.
On the other hand, green threads are executed on a single core the entire time and it is the VM that gives a multi-threading notion.
So actually there is only singe executing in case of green threads.

Native threads uses OS scheduling algorithm. Modern day OSes support pre-emptive scheduling.
Green threads can use any kind of scheduling algorithm

Native threads usually have complicated synchronization and resource sharing. Multiple processes would require kernel level locks for synchronization.
Synchronizations are pretty easier in case of green threads.

For purely sequential code, green threads are slightly faster than native threads.

For multithreaded code that involves frequent synchronization, green threads are likely to be faster than native threads.
Methods such as Object.notify() are much faster for green threads as compared to native threads.

Green threads Cannot support multi-processor machines

Green threads are generally a bit more "lightweight" than native threads

Green threads are scales to large numbers of threads than native threads.

Future Methods

A future method runs in the background, asynchronously. You can call a future method for executing long-running operations, such as callouts to external Web services or any operation you’d like to run in its own thread, on its own time. 

To define a future method, simply annotate it with the future annotation, as follows.
global class FutureClass
{
    @future
    public static void myFutureMethod()
    {   
         // Perform some operations
    }
}

The difference between the Runnable and Callable interfaces in Java..

  • A Callable needs to implement call() method while a Runnable needs to implement run() method.
  • A Callable can return a value but a Runnable cannot.
  • A Callable can throw checked exception but a Runnable cannot.
  • A Callable can be used with ExecutorService#invokeXXX methods but a Runnable cannot be.
    public interface Runnable {
        void run();
    }
    
    public interface Callable<V> {
        V call() throws Exception;
    }
     
    NOTE : Inside your class you can make the calls to Callable and Runnable
     on a single thread executor, making this mechanism similar to a serial 
    dispatch queue. So as long as the caller calls your Runnable wrapped 
    methods the calling thread will execute really fast without blocking. As
     soon as it calls a Callable wrapped in Future method it will have to 
    block till all the other queued items are executed. Only then the method
     will return with values. This is a synchronization mechanism. 

Monday, October 20, 2014

Hashing :How hash map works in java or How get() method works internally


How Hashmap works in Java

HashMap works on the principle of Hashing .  To understand Hashing , we should understand the three terms first   i.e  Hash Function , Hash Value and Bucket .

What is Hash Function , Hash Value  and Bucket ?

hashCode() function  which returns an integer value is the Hash function. The important point to note that ,  this method is present in Object class ( Mother of all class ) .

This is the code for the hash function(also known as hashCode method) in Object Class :

    public native int hashCode();

The most important point to note from the above line :  hashCode method return  int value .
So the Hash value is the int value returned by the hash function .


    So summarize the terms in the diagram below :
                  


how hash  map works in java









What is bucket ?
A bucket is used to store key value pairs . A bucket can have multiple key-value pairs . In hash map, bucket used simple linked list to store objects .

After understanding the terms we are ready to move next step , How hash map works in java or How get() works internally in java .



Code inside Java Api (HashMap class internal implementation) for HashMap get(Obejct key) method

1.  Public  V get(Object key)
   {
2.     if (key ==null)
3.     //Some code
    
4.     int hash = hash(key.hashCode());
    
5.     // if key found in hash table then  return value
6.     //    else return null
   }

Hash map works on the principle of hashing 

HashMap get(Key k) method calls hashCode method on the key object and applies returned hashValue to its own static hash function to find a bucket location(backing array) where keys and values are stored in form of a nested class called Entry (Map.Entry) . So you have concluded that from the previous line that Both key and value is stored in the bucket as a form of  Entry object . So thinking that Only value is stored  in the bucket is not correct and will not give a good impression on the interviewer .

* Whenever we call get( Key k )  method on the HashMap object . First it checks that whether key is null or not .  Note that there can only be one null key in HashMap .  

If key is null , then Null keys always map to hash 0, thus index 0.

If key is not null then , it will call hashfunction on the key object , see line 4 in above method i.e. key.hashCode()  ,so after key.hashCode() returns hashValue , line 4 looks like

4.                int hash = hash(hashValue)

 , and now ,it applies returned hashValue into its own hashing function .

We might wonder why we are calculating the hashvalue again using hash(hashValue). Answer is ,It defends against poor quality hash functions.

Now step 4 final  hashvalue is used to find the bucket location at which the Entry object is stored . Entry object stores in the bucket like this (hash,key,value,bucketindex) .  

Interviewer:    What if  when two different keys have the same hashcode ?

Solution, equals() method comes to rescue.Here candidate gets puzzled. Since bucket is one and we have two objects with the same hashcode .Candidate usually forgets that bucket is a simple linked list.

The bucket is the linked list effectively . Its not a LinkedList as in a java.util.LinkedList - It's a separate (simpler) implementation just for the map .

So we traverse through linked list , comparing keys in each entries using keys.equals() until it return true.  Then the corresponding entry object Value is returned .


how hashmap works internally in java







One of  our readers Jammy  asked a very good  question 

When the functions 'equals' traverses through the linked list does it traverses from start to end one by one...in other words brute method. Or the linked list is sorted based on key and then it traverses?

Answer is when an element is added/retrieved, same procedure follows:


a. Using key.hashCode() [ see above step 4],determine initial hashvalue for the key

b. Pass intial hashvalue as hashValue  in    hash(hashValue) function, to calculate the final hashvalue.

c. Final hash value is then passed as a first parameter in the indexFor(int ,int )method .
    The second parameter is length which is a constant in HashMap Java Api , represented by                             DEFAULT_INITIAL_CAPACITY

    The default  value of DEFAULT_INITIAL_CAPACITY is 16 in HashMap Java Api .

 indexFor(int,int) method  returns the first entry in the appropriate bucket. The linked list in the bucket is then iterated over - (the end is found and the element is added or the key is matched and the value is returned )


Explanation about indexFor(int,int) is below :

/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
    return h & (length-1);
}


The above function indexFor() works because Java HashMaps always have a capacity, i.e. number of buckets, as a power of 2.
 Let's work with a capacity of 256,which is 0x100, but it could work with any power of 2. Subtracting 1
from a power of 2 yields the exact bit mask needed to bitwise-and with the hash to get the proper bucket index, of range 0 to length - 1.
256 - 1 = 255
0x100 - 0x1 = 0xFF
E.g. a hash of 257 (0x101) gets bitwise-anded with 0xFF to yield a bucket number of 1.



Interviewer:    What if  when two  keys are same and have the same hashcode ?
If key needs to be inserted and already inserted hashkey's hashcodes are same, and keys are also same(via reference or using equals() method)  then override the previous key value pair with the current key value pair.

The other important point to note is that in Map ,Any class(String etc.) can serve as a key if and only if it overrides the equals() and hashCode() method .


Interviewer:  How will you measure the performance of HashMap?

According to Oracle Java docs,  

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. 

The capacity is the number of buckets in the hash table( HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.), and the initial capacity is simply the capacity at the time the hash table is created. 


The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

In HashMap class, the default value of load factor is (.75) .

Find the Missing Number 1 to n

You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list. Write an efficient code to find the missing integer.

Example:
I/P    [1, 2, 4, ,6, 3, 7, 8]
O/P    5


METHOD 1(Use sum formula)

Algorithm:
1. Get the sum of numbers 
       total = n*(n+1)/2
2  Subtract all the numbers from sum and
   you will get the missing number.
 
Example::
 
total = n*(n+1)/2 = 8*9/2 = 36
sum = 31
 
Missing number = total - sum =  36-31 = 5

Count of repetable words from a string

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


public class test {
public static void main(String[] args)
{
String s = "i an Apples is an an Apple";

String ar[] = s.split(" ");
List<String> valuesList = Arrays.asList(ar);

Map<String, Integer> unique = new HashMap<String, Integer>();

for (String string : valuesList) {
if(unique.get(string) == null)
unique.put(string, 1);
else
unique.put(string, unique.get(string) + 1);
}
System.out.println("Values = " + unique);

}

Monday, June 30, 2014

Can you serialize static fields of a class?

Since static fields are not part of object state, 
they are part of class, serialization ignores the static fields.

Friday, June 27, 2014

what happens when visibility of public method is reduced in subclass (public to private)?

public class Test1 {
  public static void main(String[] args) {
  }
   public void add(){
   }
}

class Test2 extends Test1 {
    private void add(){
    }
}

Compile time error :

Cannot reduce the visibility of the inherited method from Test1

String literal pool

There are slight differences between the various methods of creating a String object. String allocation, like all object allocation, proves costly in both time and memory. The JVM performs some trickery while instantiating string literals/objects to increase performance and decrease memory overhead. To cut down the number of String objects created, JVM maintains a special memory called “String literal pool” or “String constant pool”.
Each time your code creates 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 is returned. If the string does not exist in the pool, a new String object is created and placed in the pool. JVM keeps at most one object of any String in this pool. String literals always refer to an object in the string pool.
For example,

Direct Method of creating String object

1
String s1 = "iByteCode";
How this works?
  • JVM checks the String constant pool first and if the string does not exist, it creates a new String object “iByteCode” and a reference is maintained in the pool. The variable ‘s1′ also refers the same object.
  • This statement creates one String object “iByteCode”.
  • Now, let’s see what happens if we have a statement like this:
  • 1
    String s2 = "iByteCode";
  • JVM checks the String constant pool first and since the string already exists, a reference to the pooled instance is returned to s2.
  • This statement does not create any String object in the memory and ‘s2′ refers the same object as ‘s1′.
  • To check this, you can compare two String references using == operator to check whether two references are referring to the same String object in the memory.
1
2
3
4
String s1 = "iByteCode";
String s2 = "iByteCode";
if(s1 == s2)
    System.out.println("s1 and s2 referring to the same object.");
s1 and s2 referring to the same object.


Java can make this optimization since strings are immutable and can be shared without fear of data corruption. For example, if several reference variables refer to the same String object then it would be bad if any of them changes the String’s value. This is the reason for making String objects as immutable.

Creating String using constructor

1
String s = new String("iByteCode");
In this case, because we used ‘new’ keyword a String object is created in the heap memory even if an equal string object already exists in the pool and ‘s’ will refer to the newly created one.
1
2
3
String str1 = "iByteCode";
String str2 = new String("iByteCode");
System.out.println(str1 == str2);
false
String objects created with the new operator do not refer to objects in the string pool but can be made to using String’s intern() method. The java.lang.String.intern() returns an interned String, that is, one that has an entry in the global String literal pool. If the String is not already in the global String literal pool, then it will be added. For example,
1
2
3
4
String s1 = new String("iByteCode");
String s2 = s1.intern();
String s3 = "iByteCode";
System.out.println(s2 == s3);
true



In the above example, if the change the statement 2 as,
1
String s2 = s1;
Reference variable ‘s2′ will refer to the string object in the heap instead of string literal pool and s1 == s2 will print true.

An object is eligible for garbage collection when it is no longer referenced from an active part of the application. In the case of String literals, they always have a reference to them from the String Literal Pool and are, therefore, not eligible for garbage collection.
All the string literals are created and their references are placed in the pool while JVM loads the class. So, even before a statement like this String s1 = new String(“iByteCode”); is executed, the string literal pool contains a reference to “iByteCode”.

Wednesday, June 11, 2014

1) Why String is immutable in java?

Two reasons:
1) String pool requires string to be immutable otherwise shared reference can be changed from anywhere.
2) security because string is shared on different area like file system, networking connection, database connection , having immutable string allows you to be secure and safe because no one can change reference of string once it gets created. if string had been mutable anyone can surpass the security be logging in someone else name and then later modifying file belongs to other.

how to crate thread class without extending Thread or implementing Runnable interface

7. Threads pools with the Executor Framework


Tip

You find this examples in the source section in Java project called de.vogella.concurrency.threadpools.

Thread pools manage a pool of worker threads. The thread pools contains a work queue which holds tasks waiting to get executed.
A thread pool can be described as a collection of Runnable objects (work queue) and a connections of running threads. These threads are constantly running and are checking the work query for new work. If there is new work to be done they execute this Runnable. The Thread class itself provides a method, e.g. execute(Runnable r) to add a new Runnable object to the work queue.
The Executor framework provides example implementation of the java.util.concurrent.Executor interface, e.g. Executors.newFixedThreadPool(int n) which will create n worker threads. The ExecutorService adds life cycle methods to the Executor, which allows to shutdown the Executor and to wait for termination.

Tip

If you want to use one thread pool with one thread which executes several runnables you can use the Executors.newSingleThreadExecutor() method.

Create again the Runnable.

package de.vogella.concurrency.threadpools;

/** * MyRunnable will count the sum of the number from 1 to the parameter * countUntil and then write the result to the console. * <p> * MyRunnable is the task which will be performed * * @author Lars Vogel * */
public class MyRunnable implements Runnable { private final long countUntil; MyRunnable(long countUntil) { this.countUntil = countUntil; } @Override public void run() { long sum = 0; for (long i = 1; i < countUntil; i++) { sum += i; } System.out.println(sum); } }

Now you run your runnables with the executor framework.

package de.vogella.concurrency.threadpools;

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class Main {
  private static final int NTHREDS = 10;

  public static void main(String[] args) {
    ExecutorService executor = Executors.newFixedThreadPool(NTHREDS);
    for (int i = 0; i < 500; i++) {
      Runnable worker = new MyRunnable(10000000L + i);
      executor.execute(worker);
    }
    // This will make the executor accept no new threads
    // and finish all existing threads in the queue
    executor.shutdown();
    // Wait until all threads are finish
    executor.awaitTermination();
    System.out.println("Finished all threads");
  }
} 

Monday, June 9, 2014

User defined Checked and User defined unchecked exceptions in java with examples

 You can create your own exceptions in Java. Keep the following points in mind when writing your own exception classes:
  1. All exceptions must be a child of Throwable.
  2. If you want to write a checked exception that is automatically enforced by the Handle or Declare Rule, you need to extend the Exception class.
  3. If you want to write a runtime exception, you need to extend the RuntimeException class.

We can define our own Exception class as below:
class MyException extends Exception{ 
 }

You just need to extend the Exception class to create your own Exception class. These are considered to be checked exceptions. The following InsufficientFundsException class is a user-defined exception that extends the Exception class, making it a checked exception. An exception class is like any other class, containing useful fields and methods.

Example:

 // File Name InsufficientFundsException.java
 import java.io.*;

 public class InsufficientFundsException extends Exception 
 {
   private double amount;
   public InsufficientFundsException(double amount)
   {
      this.amount = amount;
   } 
   public double getAmount()
   {
      return amount;
   }
 }

To demonstrate using our user-defined exception, the following CheckingAccount class contains a withdraw() method that throws an InsufficientFundsException.

 // File Name CheckingAccount.java
 import java.io.*;

 public class CheckingAccount
 {
   private double balance;
   private int number;
   public CheckingAccount(int number)
   {
      this.number = number;
   }
   public void deposit(double amount)
   {
      balance += amount;
   }
   public void withdraw(double amount) throws InsufficientFundsException 
   {
      if(amount <= balance)
      {
         balance -= amount;
      }
      else
      {
         double needs = amount - balance;
         throw new InsufficientFundsException(needs); 
      }
   }
   public double getBalance()
   {
      return balance;
   }
   public int getNumber()
   {
      return number;
   }
 }

The following BankDemo program demonstrates invoking the deposit() and withdraw() methods of CheckingAccount.

 // File Name BankDemo.java
 public class BankDemo
 {
   public static void main(String [] args)
   {
      CheckingAccount c = new CheckingAccount(101);
      System.out.println("Depositing $500...");
      c.deposit(500.00);
      try
      {
         System.out.println("\nWithdrawing $100..."); 
         c.withdraw(100.00);
         System.out.println("\nWithdrawing $600...");
         c.withdraw(600.00);
      }catch(InsufficientFundsException e)
      {
         System.out.println("Sorry, but you are short $"
                                  + e.getAmount());
         e.printStackTrace();
      }
    }
 }
 

Sunday, June 8, 2014

How hashmap works in java

Sections in this post
  1. Single statement answer
  2. What is Hashing
  3. A little about Entry class
  4. What put() method actually does
  5. How get() methods works internally
  6. Key Notes

Single statement answer

If anybody asks me to describe “How HashMap works?“, I simply answer: “On principle of Hashing“. As simple as it is. Now before answering it, one must be very sure to know at least basics of Hashing. Right??

What is Hashing

Hashing in its simplest form, is a way to assigning a unique code for any variable/object after applying any formula/algorithm on its properties. A true Hashing function must follow this rule:
Hash function should return the same hash code each and every time, when function is applied on same or equal objects. In other words, two equal objects must produce same hash code consistently.
Note: All objects in java inherit a default implementation of hashCode() function defined in Object class. This function produce hash code by typically converting the internal address of the object into an integer, thus producing different hash codes for all different objects.

A little about Entry class

A map by definition is : “An object that maps keys to values”. Very easy.. right?
So, there must be some mechanism in HashMap to store this key value pair. Answer is YES. HashMap has an inner class Entry, which looks like this:
static class Entry implements Map.Entry
{
        final K key;
        V value;
        Entry next;
        final int hash;
        ...//More code goes here
}
Surely Entry class has key and value mapping stored as attributes. Key has been marked as final and two more fields are there: next and hash. We will try to understand the need of these fields as we go forward.

What put() method actually does

Before going into put() method’s implementation, it is very important to learn that instances of Entry class are stored in an array. HashMap class defines this variable as:
   /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry[] table;
Now look at code implementation of put() method:
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
/**
     * Associates the specified value with the specified key in this map. If the
     * map previously contained a mapping for the key, the old value is
     * replaced.
     *
     * @param key
     *            key with which the specified value is to be associated
     * @param value
     *            value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or <tt>null</tt>
     *         if there was no mapping for <tt>key</tt>. (A <tt>null</tt> return
     *         can also indicate that the map previously associated
     *         <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<k , V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
 
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }
Lets note down the steps one by one:
- First of all, key object is checked for null. If key is null, value is stored in table[0] position. Because hash code for null is always 0.
- Then on next step, a hash value is calculated using key’s hash code by calling its hashCode() method. This hash value is used to calculate index in array for storing Entry object. JDK designers well assumed that there might be some poorly written hashCode() functions that can return very high or low hash code value. To solve this issue, they introduced another hash() function, and passed the object’s hash code to this hash() function to bring hash value in range of array index size.
- Now indexFor(hash, table.length) function is called to calculate exact index position for storing the Entry object.
- Here comes the main part. Now, as we know that two unequal objects can have same hash code value, how two different objects will be stored in same array location [called bucket].
Answer is LinkedList. If you remember, Entry class had an attribute “next”. This attribute always points to next object in chain. This is exactly the behavior of LinkedList.
So, in case of collision, Entry objects are stored in LinkedList form. When an Entry object needs to be stored in particular index, HashMap checks whether there is already an entry?? If there is no entry already present, Entry object is stored in this location.
If there is already an object sitting on calculated index, its next attribute is checked. If it is null, and current Entry object becomes next node in LinkedList. If next variable is not null, procedure is followed until next is evaluated as null.
What if we add the another value object with same key as entered before. Logically, it should replace the old value. How it is done? Well, after determining the index position of Entry object, while iterating over LinkedList on calculated index, HashMap calls equals method on key object for each Entry object. All these Entry objects in LinkedList will have similar hash code but equals() method will test for true equality. If key.equals(k) will be true then both keys are treated as same key object. This will cause the replacing of value object inside Entry object only.
In this way, HashMap ensure the uniqueness of keys.

How get() methods works internally

Now we have got the idea, how key-value pairs are stored in HashMap. Next big question is : what happens when an object is passed in get method of HashMap? How the value object is determined?
Answer we already should know that the way key uniqueness is determined in put() method , same logic is applied in get() method also. The moment HashMap identify exact match for the key object passed as argument, it simply returns the value object stored in current Entry object.
If no match is found, get() method returns null.
Let have a look at code:
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
/**
     * Returns the value to which the specified key is mapped, or {@code null}
     * if this map contains no mapping for the key.
     *
     * <p>
     * More formally, if this map contains a mapping from a key {@code k} to a
     * value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise it returns
     * {@code null}. (There can be at most one such mapping.)
     *
     * </p><p>
     * A return value of {@code null} does not <i>necessarily</i> indicate that
     * the map contains no mapping for the key; it's also possible that the map
     * explicitly maps the key to {@code null}. The {@link #containsKey
     * containsKey} operation may be used to distinguish these two cases.
     *
     * @see #put(Object, Object)
     */
    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        for (Entry<k , V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }
Above code is same as put() method till if (e.hash == hash && ((k = e.key) == key || key.equals(k))), after this simply value object is returned.

Key Notes

  1. Data structure to store Entry objects is an array named table of type Entry.
  2. A particular index location in array is referred as bucket, because it can hold the first element of a LinkedList of Entry objects.
  3. Key object’s hashCode() is required to calculate the index location of Entry object.
  4. Key object’s equals() method is used to maintain uniqueness of Keys in map.
  5. Value object’s hashCode() and equals() method are not used in HashMap’s get() and put() methods.
  6. Hash code for null keys is always zero, and such Entry object is always stored in zero index in Entry[].

Thursday, June 5, 2014

What do you understand by iterator fail-fast property?

Fail-fast Iterators fail as soon as they realized that structure of Collection has been changed since iteration has begun. Structural changes means adding, removing or updating any element from collection while one thread is Iterating over that collection.
Fail-fast behavior is implemented by keeping a modification count and if iteration thread realizes the change in modification count it throws ConcurrentModificationException.

Wednesday, April 2, 2014

Java Security Guidelines: Developing and Using Java More Securely


Rule 1: Don't Depend on Initialization
Most Java developers think that there is no way to allocate an object without running a constructor. This is not true: There are several ways to allocate uninitialized objects.
The easy way to protect yourself against this problem is to write your classes so that before any object does anything, it verifies that it has been initialized. You can do this as follows:
  • Make all variables private. If you want to allow outside code to access variables in an object, this should be done via get/set methods. (This keeps outside code from accessing uninitialized variables.) If you're following Rule 3, you'll make the get and set methods final.
  • Add a new private boolean variable, called initialized, to each object.
  • Have each constructor set the initialized variable as its last action before returning.
  • Have each nonconstructor method verify that initialized is true, before doing anything. (Note that you may have to make exceptions to this rule for methods that are called by your constructors. If you do this, it is best to make the constructors call only private methods.)
  • If your class has a static initializer, you will need to do the same thing at the class level. Specifically, for any class that has a static initializer, follow these steps:
  • Make all static variables private. If you want to allow outside code to access static variables in the class, this should be done via static get/set methods. This keeps outside code from accessing uninitialized static variables. If you're following Rule 3, you'll make the get and set methods final.
  • Add a new private static boolean variable, called classInitialized to the class.
  • Have the static constructor set the classInitialized variable as its last action before returning.
  • Have each static method, and each constructor, verify that classInitialized is true, before doing anything. (Note: Constructors are required to call a constructor of the superclass or another constructor of the same class as their first action. Therefore, you will have to do that before you check classInitialized.)


Rule 2: Limit Access to Your Classes, Methods, and Variables
Every class, method, and variable that is not private provides a potential entry point for an attacker. By default, everything should be private. Make something non-private only if there is a good reason, and document that reason.


Rule 3: Make Everything Final, Unless There's a Good Reason Not To
If a class or method is non-final, an attacker could try to extend it in a dangerous and unforeseen way. By default, everything should be final. Make something non-final only if there is a good reason, and document that reason.
You might think that you can prevent an attacker from extending your class or its methods by declaring the class non-public. However, if a class is not public, it must be accessible from within the same package, and as we shall see, Rule 4 says not to rely on package-scope access restrictions for security.
This advice may seem harsh. After all, the rule is asking you to give up extensibility, which is one of the main benefits of using an object-oriented language like Java. When you're trying to provide security, however, extensibility is your enemy; it just provides an attacker with more ways to cause trouble.


Rule 4: Don't Depend on Package Scope
Classes, methods, and variables that are not explicitly labeled as public, private, or protected are accessible within the same package. Don't rely on this for security. Java classes are not closed, so an attacker could introduce a new class inside your package, and use this new class to access the things you thought you were hiding. (A few packages, such as java.lang, are closed by default, and a few JVMs let you close your own packages. However, you're better off assuming that packages are not closed.)
Package scope makes a lot of sense from a software-engineering standpoint, since it prevents innocent, accidental access to things that you want to hide. But don't depend on it for security. Maybe we'll get sealed classes in the future.


Rule 5: Don't Use Inner Classes
Some Java language books say that inner classes can only be accessed by the outer classes that enclose them. This is not true. Java byte code has no concept of inner classes, so inner classes are translated by the compiler into ordinary classes that happen to be accessible to any code in the same package. And Rule 4 says not to depend on package scope for protection.
But wait, it gets worse. An inner class gets access to the fields of the enclosing outer class, even if these fields are declared private. And the inner class is translated into a separate class. In order to allow this separate class access to the fields of the outer class, the compiler silently changes these fields from private to package scope! It's bad enough that the inner class is exposed, but it's even worse that the compiler is silently overruling your decision to make some fields private. Don't use inner classes if you can help it. (Ironically, the new Java 2 doPrivileged() API usage guidelines suggest that you use an inner class to write privileged code. That's one reason we don't like the doPrivileged() API.)


Rule 6: Avoid Signing Your Code
Code that is not signed will run without any special privileges. And if your code has no special privileges, then it is much less likely to do damage.
Of course, some of your code might have to acquire and use privileges to perform some dangerous operation. Work hard to minimize the amount of privileged code, and audit the privileged code more carefully than the rest.


Rule 7: If You Must Sign Your Code, Put It All in One Archive File
The goal of this rule is to prevent an attacker from carrying out a mix-and-match attack in which the attacker constructs a new applet or library that links some of your signed classes together with malicious classes, or links together signed classes that you never meant to be used together. By signing a group of classes together, you make this attack more difficult.
Existing code-signing systems do an inadequate job of preventing mix-and-match attacks, so this rule cannot prevent such attacks completely. But using a single archive can't hurt.
Some code-signing systems let you examine other classes to see who signed them. If you are using a code-signing system that allows this, you can put code into the static constructors of your classes to verify that the "surrounding" classes have been signed by the same person as expected. Examining signers is one way to avoid the example shown in Figure 7.1. This doesn't completely prevent mix-and-match attacks, since an adversary can still mix together classes that you signed at different times; for example, by mixing version 1 of Class A with version 2 of Class B. If you're worried about this kind of interversion mix-and-match attack, you can put each class's "version stamp" in a public final variable and then have each class check the version stamps of its surrounding classes.

Fig 7.1
Figure 7.1 A mix and match attack.

In one type of mix and match attack, signed code with special privilege is linked or otherwise grouped together with unsigned code. The danger is that the unsigned code will be replaced in the group, leading to undefined and possibly dangerous behavior.


Rule 8: Make Your Classes Uncloneable
Java's object-cloning mechanism can allow an attacker to manufacture new instances of classes you define, without executing any of your constructors. If your class is not cloneable, the attacker can define a subclass of your class, and make the subclass implement java.lang.Cloneable. This allows the attacker to make new instances of your class. The new instances are made by copying the memory images of existing objects; although this is sometimes an acceptable way to make a new object, it often is not.
Rather than worry about this, you're better off making your objects uncloneable. You can do this by defining the following method in each of your classes:

public final void clone() throws java.lang.CloneNotSupportedException {
     throw new java.lang.CloneNotSupportedException();
}
If you want your class to be cloneable, and you've considered the consequences of that choice, then you can still protect yourself. If you're defining a clone method yourself, make it final. If you're relying on a nonfinal clone method in one of your superclasses, then define this method:

public final void clone() throws java.lang.CloneNotSupportedException {
     super.clone();
}
This prevents an attacker from redefining your clone method.


Rule 9: Make Your Classes Unserializeable
Serialization is dangerous because it allows adversaries to get their hands on the internal state of your objects. An adversary can serialize one of your objects into a byte array that can be read. This allows the adversary to inspect the full internal state of your object, including any fields you marked private as well as the internal state of any objects you reference.
To prevent this, you can make your object impossible to serialize. The way to do this is to declare the writeObject method:

private final void writeObject(ObjectOutputStream out)
throws java.io.IOException {
     throw new java.io.IOException("Object cannot be serialized");
}
This method is declared final so that a subclass defined by the adversary cannot override it.


Rule 10: Make Your Classes Undeserializeable
This rule is even more important than the preceding one. Even if your class is not serializeable, it may still be deserializeable. An adversary can create a sequence of bytes that happens to deserialize to an instance of your class. This is dangerous, since you do not have control over what state the deserialized object is in. You can think of deserialization as another kind of public constructor for your object; unfortunately, it is a kind of constructor that is difficult for you to control.
You can prevent this kind of attack by making it impossible to deserialize a byte stream into an instance of your class. You can do this by declaring the readObject method:

private final void readObject(ObjectInputStream in)
throws java.io.IOException {
     throw new java.io.IOException("Class cannot be deserialized");
}
As in Rule 9, this method is declared final to prevent the adversary from overriding it.


Rule 11: Don't Compare Classes by Name
Sometimes you want to compare the classes of two objects to see whether they are the same, or you want to see whether an object has a particular class. When you do this, you need to be aware that there can be multiple classes with the same name in a JVM. It is a mistake to compare classes by name since different classes can have the same name.
A better way is to compare class objects for equality directly. For example, given two objects, a and b, if you want to see whether they are the same class, you should use this code:

if(a.getClass() == b.getClass()){
     // objects have the same class
}else{
     // objects have different classes
}
You should also be on the lookout for cases of less-direct by-name comparisons. Suppose, for example, you want to see whether an object "has the class Foo." Here is the wrong way to do it:

if(obj.getClass().getName().equals("Foo"))   // Wrong!
     // objects class is named Foo
}else{
     // object's class has some other name
}
Here is a better way to do it:

if(obj.getClass() == this.getClassLoader().loadClass("Foo")){
     // object's class is equal to the class that this class calls "Foo"
}else{
     // object's class is not equal to the class that 
     // this class calls "Foo"
}
Note the legalistic comments in the last example. Whenever you use classnames, you are opening yourself up to mix-and-match attacks, as described in Rule 7. You should also know that the Java language forces you to use classnames all the time: in variable declarations, instanceof expressions, and exception-catching blocks. Only the designers of Java can prevent mix-and-match attacks, but you can avoid making the problem worse by avoiding by-name class comparisons.


Rule 12: Secrets Stored in Your Code Won't Protect You
You might be tempted to store secrets such as cryptographic keys in the code for your application or library. Secrets stored in this way are completely accessible to anyone who runs your code. There is nothing to stop a malicious programmer or virtual machine from looking inside your code and learning its secrets.
Code obfuscation is another way to store a secret in your code; in the case of obfuscation, the secret is simply the algorithm used by your code. There's not much harm in using an obfuscator, but you shouldn't believe that it provides strong protection. There is no real evidence that it is possible to obfuscate Java source code or byte code so that a dedicated adversary with good tools cannot reverse the obfuscation.