What happens when we use foreach loop to traverse Arraylist ?

Generally we have Iterator class to traverse any Collection object, For ArrayList also we can use Iterator.

But what happens, if we use foreach loop to iterate it?

code snippet:1

ArrayList<String> ar = new ArrayList<String>(100);
        ar.add("a");
        ar.add("b");
        ar.add("c");
        ar.add("d");

        for (String str : ar) {
            System.out.println(str);
            ar.remove("c"); // generates concurrent modification
        }
//


output: 
a
Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.AbstractList$Itr.checkForComodification(Unknown Source)
    at java.util.AbstractList$Itr.next(Unknown Source)
    at ArrayListLooping.main(ArrayListLooping.java:14)

From the above code, even for adding new element in the foreach loop also we face this exception.



Because, this foreach loop sets loop count number to size of ar object i.e 4 for it's life time. And when try to remove any element from ar also the loop number will be same, so we will get ConcurrentModificationException.


Noraml for loop usage on ArrayList.

code snippet:2

for (int i = 0; i < ar.size(); i++) {
            System.out.println("loop:" + i + " size:" + ar.size());
            System.out.println(ar.get(i));
            if (ar.contains("c")) {
                ar.remove("c");
            }
        }// it loops based on the ar size
//

The above code will execute and successfully removes "c". This looping runs based on the size of ar object for every loop.


Now, you decide which one to use.

How to set Environment Variables in Unix / Linux Operating System ?

Setting Environment variables in Unix / Linux:

Here I show you how to set any environment variable in Linux OS.

First, we must know how many places are there to set environment variables in Unix.

I mean, 
 In windows we have two types 
     1) User Variables
     2) System Variables

        Here, user variables are only for that user. And system variables are for entire system and for all users exist in that Operating System.

Generally we know how to set these variables in windows, because it is GUI based setup.

But in Unix / Linux we can't do like that. Instead we have to place these variables in a shell script file. So that, those scripting statements are executed and those variables are available. 


Placing Unix Environment variables:

User Level:
                                In every user's Home directory we have some hidden files like             .bash_history, .bash_logout, .bashrc, .profile 

           Choose any one file from .bashrc or .profile from above files.
and add variable setup statement at the end of that file along with the comment and save it.

Before going to use these environment variables, we must logout the account and login.

for example:
To set JAVA_HOME :
      #Setting JAVA_HOME variable
      export JAVA_HOME=~/jdk1.6xx

To set PATH for java's bin directory
     #Adding java to PATH variable
      export PATH=$PATH:$JAVA_HOME/bin


System Level:
                                 In every Unix System we have profile under the directory /etc.

/etc/profile - is a shell script file.

Here also, we have to add environment variable setup statement at the end of that file. To avail these environment variables, we must restart the system.

Checking of these Environment Variables:

      Use echo command to see whether the environment variable is set or not.

example:
       #echo $JAVA_HOME
    or 
      #echo $PATH


Note: 
In the csh shell: use - setenv PATH=$PATH:$JAVA_HOME/bin
In the bash shell (Linux): use - export PATH=$PATH:$JAVA_HOME/bin
In the sh or ksh shell: use - PATH=$PATH:$JAVA_HOME/bin





   

What is Encapsulation ?

Encapsulation:

- Binding of data and methods as single unit.
e.g: class

Advantage: 
- we can use the same varaible or names in different classes.



If any class contains DataHiding + Abstraction , we call it as Encapsulation.
e.g: javabean  or POJO (plain old java object)

Advantage:  
- It increases security
- Enhancement is easy.
- Improves maintainability.

What is Abstraction ?

Abstraction : 

- Hiding unnecessary data from the user.
- Hiding implementation details.
- Abstraction is a process of hiding the implementation details and showing only functionality to the user.
- it shows only important things to the user and hides the internal details.


Advantages:

            - It increases security.
            - Enhancement is easy.
            - Improve maintainability.

There are two ways to achieve abstraction in java.

1) Abstract (Partially or may be Fully abstraction)

2) Interface (Fully abstraction)

An Abstract Class Example

In an object-oriented drawing application, you can draw circles, rectangles, lines, Bezier curves, and many other graphic objects. These objects all have certain states (for example: position, orientation, line color, fill color) and behaviors (for example: moveTo, rotate, resize, draw) in common. Some of these states and behaviors are the same for all graphic objects—for example: position, fill color, and moveTo. Others require different implementations—for example, resize or draw. All GraphicObjects must know how to draw or resize themselves; they just differ in how they do it. This is a perfect situation for an abstract superclass. You can take advantage of the similarities and declare all the graphic objects to inherit from the same abstract parent object—for example, GraphicObject, as shown in the following figure.

An abstract method in Java doesn't have body , its just a declaration. In order to use abstract method you need to override that method in SubClass.

So when do you use abstraction ?

*** when Yo  know something needs to be there but  not sure how exactly it should look like.

*** e.g. when I am creating a class called Vehicle, I know there should be methods like start() and Stop() but don't know start and stop mechanism of every vehicle since they could have different start and stop mechanism e..g some can be started by kick or some can be by pressing buttons .

sources:  http://javarevisited.blogspot.com/2010/10/abstraction-in-java.html#ixzz2dPnl6Rjb http://docs.oracle.com/javase/tutorial/java/IandI/abstract.html http://www.javatpoint.com/abstract-class-in-java

NullPointerException comes under checked exception or unchecker exception or error ?

NullPointerException:

NullPointerException is very common exception we see in development,  One thing we don't observe is that this exception raises at runtime.

So we can say NullPointerException comes under RuntimeException. It is not an error, because Java runtime is displaying the exception on to the console,  errors are not displayed on to console , errors are nothing but logical errors, JVM doesn't know how to handle them,  Developers responsibility to handle errors. 


If we see in the Exception hierarchy NullPointerException is the child class of RuntimeException which can be throwable but at runtime.

What are the Exception handler components in java? and how many handler components are there ?

 try, catch, finally :

try, catch, finally are the three exception handler components in java.


These 3 are mandatory components to write exception handler code.

     In try block we write resources statement, and in catch block we catch the exception object raised in try block , and in finally block we write resources release code.

Difference between throws and throw ?

throws:

         If a method does not handle a checked exception, the method must declare it using the throws keyword. The throws keyword appears at the end of a method's signature.



throw:

        You can throw an exception, either a newly instantiated one or an exception that you just caught, by using the throw keyword.

       To throw a custom exception , first we need to write a class  which extends one of the child class of Exception class or we can extend Exception class. And we can directly create an object to it and then thow inside a method where we need to throw it using 'throw' keyword.

for example:

    class AuthenticationException extends Exception. and we want to throw custom exception ,

use ' throw new AuthenticationException(); '

and here we can write parametrized constructor also.


So throw keyword is to throw library exceptions, and throw keyword is used to throw custom exceptions.

When an object to be the target of the "foreach" statement?

for-each loop:

Implementing Iterable interface allows an object to be the target of the "foreach" statement.

java.lang
Interface Iterable<T>

All Known Subinterfaces:

BeanContext, BeanContextServices, BlockingDeque<E>, BlockingQueue<E>, Collection<E>, Deque<E>, List<E>, NavigableSet<E>, Queue<E>, Set<E>, SortedSet<E>

So we can Iterate List, Set, SortedSet, Collection..etc Objects.

sources :http://docs.oracle.com/javase/6/docs/api/java/lang/Iterable.html

What is difference between Iterator and Enumeration?

Iterator vs Enumeration:

                 functionality of Enumeration interface is duplicated by the Iterator interface.                

                  Only major difference between Enumeration and iterator is 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 by using Iterator we can manipulate the objects like adding and removing the objects from collection e.g. Arraylist.

                                                     Also Iterator is more secure and safe as compared to Enumeration because it  does not allow other thread to modify the collection object while some thread is iterating over it and throws ConcurrentModificationException. This is by far most important fact for me for deciding between Iterator vs Enumeration in Java.

Enumeration:

Method Summary
boolean	hasMoreElements()           Tests if this enumeration contains more elements.
E	nextElement()           Returns the next element of this enumeration if this enumeration object has at least one more element to provide.

Iterator:

Method Summary
boolean	hasNext()           Returns true if the iteration has more elements.
E	next()           Returns the next element in the iteration.
void	remove()           Removes from the underlying collection the last element returned by the iterator (optional operation).

sources:
 http://javarevisited.blogspot.com/2011/11/collection-interview-questions-answers.html#ixzz2dLkFqR00
http://docs.oracle.com/javase/6/docs/api/java/util/Iterator.html
http://docs.oracle.com/javase/6/docs/api/java/util/Enumeration.html

Difference between HashMap and HashTable?

Difference between HashMap:

                  Both HashMap and Hashtable implements Map interface but there are some significant difference between them which is important to remember before deciding whether to use HashMap or Hashtable in Java. Some of them is thread-safety, synchronization and speed.

                   1.The HashMap class is roughly equivalent to Hashtable, except that it is non synchronized and permits nulls. (HashMap allows null values as key and value whereas Hashtable doesn't allow nulls).

                          2. One of the major differences between HashMap and Hashtable is that HashMap is non synchronized whereas Hashtable is synchronized, which means Hashtable is thread-safe and can be shared between multiple threads but HashMap can not be shared between multiple threads without proper synchronization.

                   3.One more notable difference between Hashtable and HashMap is that because of thread-safety and synchronization Hashtable is much slower than HashMap if used in Single threaded environment. So if you don't need synchronization and HashMap is only used by one thread, it out perform Hashtable in Java.

                  4.HashMap does not guarantee that the order of the map will remain constant over time.

sources: http://javarevisited.blogspot.in/2010/10/difference-between-hashmap-and.html

HashMap can be synchronized by

Map m = Collections.synchronizeMap(hashMap);

How HashMap works in java?

HashMap
--------------------

                          HashMap works on principle of hashing, we have put(key, value) and get(key) method for storing and retrieving Objects from HashMap. When we pass Key and Value object  to put() method on Java HashMap, HashMap implementation calls hashCode method on Key object and applies returned hashcode into its own hashing function to find a bucket location for storing Entry object, important point to mention is that HashMap in Java stores both key and value object as Map.Entry in bucket which is essential to understand the retrieving logic.

                      Since hashcode is same, bucket location would be same and collision will occur in HashMap, Since HashMap use LinkedList to store object, this entry (object of Map.Entry comprise key and value )  will be stored in LinkedList.

                                  we will call get() method and then HashMap uses Key Object's hashcode to find out bucket location and retrieves Value object but then you need to remind him that there are two Value objects are stored in same bucket.

                      After finding bucket location , we will call keys.equals() method to identify correct node in LinkedList and return associated value object for that key in Java HashMap.


                            Using immutable, final object with proper equals() and hashcode() implementation would act as perfect Java HashMap  keys and improve performance of Java HashMap  by reducing collision. Immutability also allows caching there hashcode of different keys which makes overall retrieval process very fast and suggest that String and various wrapper classes e.g. Integer very good keys in JavaHashMap.


sources: http://javarevisited.blogspot.in/2011/02/how-hashmap-works-in-java.html

What is an Exception?

Exception:

      Exception is an event, which occurs during an excecution of a program, that disrupts the the normal flow of the program's instructions.

When an error occurs within a method,  the method will create an object and hands it off to the runtime system.

     This object is called exception object.

This object holds some information about error, error type, and state of the program when error occured.


Throwing an exception:

    Creating an object and handling it to the runtime system is called  throwing an exception.

After a method throws an exception, the runtime system attempts to find something to handle it. The set of possible "somethings" to handle the exception is the ordered list of methods that had been called to get to the method where the error occurred. The list of methods is known as the call stack.

The runtime system searches the call stack for a method that contains a block of code that can handle the exception. This block of code is called an exception handler. The search begins with the method in which the error occurred and proceeds through the call stack in the reverse order in which the methods were called. When an appropriate handler is found, the runtime system passes the exception to the handle .

 And try, catch, finally are used handle exception

There are 3 categories of Exceptions

1) Checked Exceptions:
       Checked exceptions are subject to the Catch or Specify Requirement. All exceptions are checked exceptions, except for those indicated by Error, RuntimeException, and their subclasses.
       These are exceptional conditions that a well-written application should anticipate and recover from.

2) Error:
       Errors are not subject to the Catch or Specify Requirement. Errors are those exceptions indicated by Error and its subclasses.
      These are exceptional conditions that are external to the application

3) runtime Exception:
        Runtime exceptions are not subject to the Catch or Specify Requirement. Runtime exceptions are those indicated by RuntimeException and its subclasses.
       These are exceptional conditions that are internal to the application, and that the application usually cannot anticipate or recover from.

Exception Hierarchy:

All exception classes are subtypes of the java.lang.Exception class. The exception class is a subclass of the Throwable class. Other than the exception class there is another subclass called Error which is derived from the Throwable class.
Errors are not normally trapped form the Java programs. These conditions normally happen in case of severe failures, which are not handled by the java programs. Errors are generated to indicate errors generated by the runtime environment. Example : JVM is out of Memory. Normally programs cannot recover from errors.
The Exception class has two main subclasses : IOException class and RuntimeException Class.

sources : http://docs.oracle.com/javase/tutorial/essential/exceptions/index.html
                 http://www.tutorialspoint.com/java/java_exceptions.htm 

Why do we need SerialVersionUID in Java ?

      

SerialVersionUID :

         The serialization runtime associates with each serializable class a version number, called a serialVersionUID, which is used during deserialization to verify that the sender and receiver of a serialized object have loaded classes for that object that are compatible with respect to serialization.

       A serializable class can declare its own serialVersionUID explicitly by declaring a field named “serialVersionUID” that must be static, final, and of type long:

ANY-ACCESS-MODIFIER static final long serialVersionUID = 42L;

        It is strongly recommended that all serializable classes explicitly declare serialVersionUID values, since the default serialVersionUID computation is highly sensitive to class details that may vary depending on compiler implementations, and can thus result in unexpected InvalidClassExceptions during deserialization. Therefore, to guarantee a consistent serialVersionUID value across different java compiler implementations, a serializable class must declare an explicit serialVersionUID value. It is also strongly advised that explicit serialVersionUID declarations use the private modifier where possible, since such declarations apply only to the immediately declaring class.serialVersionUID fields are not useful as inherited members.


take an example :

A.java:  //version1

package com.nagarjuna.java.core;

import java.io.Serializable;

public class A implements Serializable {//version1

    //private static final long serialVersionUID = 11L;
   

}//end class

try to make serialize the object of the above class using below code....


SerializationDemo.java:

package com.nagarjuna.java.core;

import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectOutputStream;

public class SerializationDemo {

    public static void main(String[] args) throws FileNotFoundException, IOException {
   
        A b1 = new A();
        ObjectOutputStream o = new ObjectOutputStream(new FileOutputStream("Demo1.srz"));
        o.writeObject(b1);
        o.close();
        System.out.println("object serialization done...");
    }

}//end class





Now modify the class A, and try to Deserialize "Demo1.srz"...

A.java:   //version2
package com.nagarjuna.java.core;

import java.io.Serializable;

public class A implements Serializable {//version1

    //private static final long serialVersionUID = 11L;
      private int x=44;
   

}//end class


package com.nagarjuna.java.core;

import java.io.FileInputStream;
import java.io.IOException;
import java.io.ObjectInputStream;

public class DeserailizationDemo {

    public static void main(String[] args) throws IOException, ClassNotFoundException {
          A b1 = new A();

        ObjectInputStream in = new ObjectInputStream(new FileInputStream("Demo1.srz"));
        b1 = (A) in.readObject();
        System.out.println("object deserialized...");

    }
}//end class

Now we will get below error...

Exception in thread "main" java.io.InvalidClassException: com.nagarjuna.A; local class incompatible: stream classdesc serialVersionUID = -2586413528665436440, local class serialVersionUID = -1225490151988851177
    at java.io.ObjectStreamClass.initNonProxy(Unknown Source)
    at java.io.ObjectInputStream.readNonProxyDesc(Unknown Source)
    at java.io.ObjectInputStream.readClassDesc(Unknown Source)
    at java.io.ObjectInputStream.readOrdinaryObject(Unknown Source)
    at java.io.ObjectInputStream.readObject0(Unknown Source)
    at java.io.ObjectInputStream.readObject(Unknown Source)
    at com.n1.ExternizationDemo.main(DeserailizationDemo.java:15)





for this reason we have to use SerialVersionUID, From the above example remove comment at serialVersionUID in class 'A', and try  again. You won't get errors, because we mentioned that class A is of serialVersionUID=11L, and nothing changed in code.


source : http://shivasoft.in/blog/java/explain-serialversionuid-in-java

What is Ant? or Project Biulding tool.

        

             Apache Ant is a software tool for automating software build processes. It is similar to Make but is implemented using the Java language, requires the Java platform, and is best suited to building Java projects.

         The most immediately noticeable difference between Ant and Make is that Ant uses XML to describe the build process and its dependencies, whereas Make uses Makefile format. 

By default the XML file is named build.xml.

             There is much more to building software than just typing in and then compiling the source code. There is a number of steps required to transform the source into a deployable and useable software solution.

The following is a hypothetical build process you might use with a simple software system

1. Get the source. You may need to download or fetch the source from a source code repository. For this, you might need to know the tag or version of the source code you want to build.
2. Prepare a build area. You will probably want to create a set of directories, perhaps according to some standardized directory layout.
3. Configure the build. In this step, you will determine what optional components can be built based on the current environment. You might want to set build numbers and version numbers to be included in the build.
4. Validate the source code. You may have a standard style guide and you wish to ensure all code conforms to this before you build a release.
5. Compile the source code
6. Build the compiled code into libraries potentially including non-code resources such as properties, images and sound files.
7. Run the system's tests to validate the build.
8. Build the documentation for the software. This may range from something as simple as collecting text files up to processing content through some form of publishing system to produce the documentation in its final form
9. Package up all of the components of the software – code, resources, images, documentation, etc. – into a deployable package. You might need to produce several packages in different formats for different target users
10. Deploy the software to some standard location for use or distribution

This is a high-level view of a software build process. A real-life build process may of course require many more and varied steps. Each of these steps may involve many individual operations. 

-------------------

Why do we need Maven or Ant, if we already have Eclipse?

1. Because your collegue might prefer NetBeans or IDEA
2. Because the settings might vary from one eclipse install to another
3. Because you might want to get your dependencies automatically
4. Because you want to automate the complete build: build, jar, apply static code analysis, run the unit tests, generate the documentation, copy to some directory, tune some properties depending on the environment, etc.
5. Because once it's automated, you can use a continuous integration system which builds the application at each change or every hour to make sure everything still builds and the tests still pass...

Eclipse is a development environment. But it's not a build tool

------------------- 

Ant can get source code from version control
               CVS, Subversion, Synergy, Perforce, ClearCase and many more Ant can compile source code
Ant can run unit tests
              JUnit3, JUnit4, TestNG, or any arbitrary test application
Ant can package compiled code and resources
               jars, wars, ears, tars, zips, whatever

-------------------

sources: http://www.exubero.com/ant/antintro-s5.html
                 http://en.wikipedia.org/wiki/Apache_Ant
                 http://codefeed.com/tutorial/ant_intro.html
                 http://stackoverflow.com/questions/10764576/why-do-we-need-maven-or-ant-if-we-already-have-eclipse

Collections in Java Easiest way to remember....

Collection Interfaces

Implementations

Methods available

Algorithms Efficiency

What is Timestamp? In computers...domain....!

      
  TimeStamp...

       A timestamp is a sequence of characters or encoded information identifying when a certain event occurred, usually giving date and time of day, sometimes accurate to a small fraction of a second. The term derives from rubber stamps used in offices to stamp the current date, and sometimes time, in ink on paper documents, to record when the document was received. A common example of this type of timestamp is a postmark on a letter. However, in modern times usage of the term has expanded to refer to digital date and time information attached to digital data. For example, computer files contain timestamps that tell when the file was last modified, and digital cameras add timestamps to the pictures they take, recording the date and time the picture was taken.

or


        A timestamp is the current time of an event that is recorded by a computer.
Timestamps are employed extensively within computers and over networks for various types of synchronization. For example, they are assigned to packets in some network protocols in order to facilitate the reassembly of the data (e.g., human speech) in the proper sequence by the receiving host (i.e., computer). Also, they are used by database management systems (DBMS) to determine the transaction order in the event of a system failure (e.g., a computer crash caused by a loss of electrical power or disk failure).
Timestamps are also routinely used to provide information about files, including when they were created and last accessed or modified. This information is included in the inode, which is a data structure on a filesystem on a Unix-like operating system that stores all the information about a file except its name and its actual data.
Another important application is events that are recorded in system log files. The timestamps in such files can be extremely useful for monitoring system security and for forensic purposes.
The time as recorded by timestamps can be measured in terms of the time of day or relative to some starting point. And it is measured with high precision in small fractions of a second.
The accuracy of the time is maintained through a variety of mechanisms, including the high-precision clocks built into computers and the network time protocol (NTP). NTP uses coordinated universal time (UTC) to synchronize computer clock times to a millisecond (and sometimes to a fraction of a millisecond) and uses UDP (user datagram protocol), one of the core Internet protocols, as its transport mechanism.


sources: http://www.linfo.org/timestamp.html
                 http://en.wikipedia.org/wiki/Timestamp

Something about Trees in Datastructures

Hi ,

In this post I am going to tell you something about Tree.

Tree is a Data-structure used when need good performance for ..
       - To add an Element
       - To remove an Element
       - To containment test.

In java we use TreeSet, It is an implementation for Set Interface.
This class provides Set implementation by inter usage of Tree datastructure.

When we go for usage of this Tree, We must know something about it.

We start with Tree:

Tree:
A tree is a collection of nodes. The collection can be empty. or
A tree consists of a distinguished node r, called root, zero or more noneempty (sub)trees T1. or
A tree is recursively.

A tree can have any number of child nodes.
for example:

Usage:
Trees can be used to evaluate arithmetic expressions.
Trees are used to implement the file system of several popular operation system.


Binary Tree:

Binary trees are slightly differ from normal Trees.

In Binary tree , the maximum number of child nodes at any level will be Two.

   A binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes,

    A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees" on either side. A null pointer represents a binary tree with no elements -- the empty tree. The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree. 

So that, It is called BianaryTree.
Binary ( two -->   either 0 or 1  like)
Element insertion will be bases on  left ---> right manner.

• A node contains two references (to left and right child nodes.

Binary Search Tree (BST):

  A binary search tree (BST), sometimes also called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:^[1]

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• The left and right subtree must each also be a binary search tree.
• There must be no duplicate nodes.

Generally, the information represented by each node is a record rather than a single data element. However, for sequencing purposes, nodes are compared according to their keys rather than any part of their associated records.

The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.

   This BST is came from Binary Tree, but it follows  left --> right manner based on the value of element in every node.

Generally every node has 3 fields.
    one - data ( mandatory filed)
    two - link to left node (optional)
    three - link to right node (optional)

suppose:
To insert some elements into a BST ....

   elements - 37, 24, 42, 7, 2, 40, 43, 32, 120

the insertion will be like in the picture below

- start the root node with the value 37, because there is no root or child nodes.

- next while inserting 24,  check the value of root node, here root value is higher the 24, then check for left node, here only one root node and no child nodes, so this 24 will go to left to the root node.

- similarly 42, it checks the value at root node, it is higher than the value of root node, then check for any right child node, here no right child node and only we have root and it's left child node, So thid 42 goes to right child of the root node.

- similarly following element insertion is same , It follows recursion at every node.

- like wise we create a tree as above in the picture.

Here For retrieval of elements in the above tree, it follows 3 types of retrievals.

1) Pre-order ( data--> left --> right)
2) In-order ( left--> data --> right) , retrieved values are in a order. ( sorted)
3) Post-order (left--> right -->data)


from the above example :

  pre-order will be : 37, 24, 7, 2, 32, 42, 40, 43, 120
  in-order will be : 2,7,24, 32, 37, 40, 42, 43, 120 (sorted)*
  post-order will be: 2, 7, 32, 24, 40, 120, 43, 42, 37


sources:
http://en.wikipedia.org/wiki/Binary_search_tree
http://www.iro.umontreal.ca/~pift1025/bigjava/Ch21/ch21.html
http://www.learnalgorithms.in
       

Difference between Algorithms and DataStructures

What is an algorithm ?
    What are algorithms ? Why is the study of algorithms worthwhile ? What is the role of algorithms relative to other technologies used in computers ?

    Well, informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output. We can also view an algorithm as a tool for solving a well-specified computational problem. The statement of the problem specifies in general terms the desired input/output relationship. The algorithm describes a specific computational procedure for achieving that input/output relationship.

What is a data structure ?
    A data structure is a way to store and organize data in order to facilitate access and modifications.Data structures are the heart of any sophisticated program. Selecting the right data structure can make an enormous difference in the complexity of the resulting implementation. Pick the right data representation, and your task will be easy to program. Pick the wrong representation, and you may spend enormous amounts of time and code covering up for your lousy initial decision. Data Structures are used to efficiently work with the data being used in our program.

    Stack, Queue, Tree etc. are few examples of the data structures having different capabilities and consequently being used for different applications in programming. You can learn more about them in the Data Structures section.

Does any specific programming language favor any algorithm/ Data Structure ?
    And answer is NO! Algorithms and Data Structures are no way related to a particular language in specific. But yes, a language may provide some inbuilt tools or APIs which support any data structure type. But it never means that you can not develop the same APIs in any other language. You may choose any programming language to learn the algorithms and programming.

source:http://www.learnalgorithms.in

HashTable usage and Collision in it.

 

HashTable

Hashtable is an implementation of a key-value pair data structure in java. You can store and retrieve a ‘value’ using a ‘key’ and it is an identifier of the value stored. It is obvious that the ‘key’ should be unique.

java.util.Hashtable extends Dictionary and implements Map. Objects with non-null value can be used as a key or value. Key of the Hashtable must implement hashcode() and equals() methods.

Hashing and Hashtable

Before seeing java’s Hashtable in detail you should understand hashing in general. Assume that, v is a value to be stored and k is the key used for storage / retrieval, then h is a hash function where v is stored at h(k) of table. To retrieve a value compute h(k) so that you can directly get the position of v. So in a key-value pair table, you need not sequentially scan through the keys to identify a value.

h(k) is the hashing function and it is used to find the location to store the corresponding value v. h(k) cannot compute to a indefinite space. Storage allocated for a Hashtable is limited within a program. So, the hasing function h(k) should return a number within that allocated spectrum(logical address space).

Collision in Hashtable

When we try to restrict the hashing function’s output within the allocated address spectrue limit, there is a possibility of a collision. For two different keys k1 and k2, if we have h(k1) = h(k2), then this is called collision in hashtable. What does this mean, our hashing function directs us store two different values (keys are also different) in the same location.

When we have a collision, there are multiple methodologies available to resolve it. To name a few hashtable collision resolution technique, ‘separate chaining’, ‘open addressing’, ‘robin hood hashing’, ‘cuckoo hashing’, etc. Java’s hashtable uses ‘separate chaining’ for collision resolution in Hashtable.

Collision Resolution in java’s Hashtable

Java uses separate chaining for collision resolution. Recall a point that Hashtable stores elements in buckets. In separate chaining, every bucket will store a reference to a linked list. Now assume that you have stored an element in bucket 1. That means, in bucket 1 you will have a reference to a linked list and in that linked list you will have two cells. In those two cells you will have key and its corresponding value.

Why do you want to store the key? Because when there is a collision i.e., when two keys results in same hashcode and directs to the same bucket (assume bucket 1) you want to store the second element also in the same bucket. You add this second element to the already created linked list as the adjacent element.

Now when you retrieve a value it will compute the hash code and direct you to a bucket which has two elements. You scan those two elements alone sequentially and compare the keys using their equals() method. When the key mathches you get the respective value. Hope you have got the reason behind the condition that your object must have hashCode() and equals() method.

Java has a private static class Entry inside Hashtable. It is an implementation of a list and you can see there, it stores both the key and value.

for more clarity open http://research.cs.vt.edu/AVresearch/hashing/buckethash.php

Hashtable performance

To get better performance from your java Hashtable, you need to
1) use the initialCapacity and loadFactor arguments
2) use them wisely

while instantiating a Hashtable.

initialCapacitiy is the number of buckets to be created at the time of Hashtable instantiation. The number of buckets and probability of collision is inversly proportional. If you have more number of buckets than needed then you have lesser possibility for a collision.

For example, if you are going to store 10 elements and if you are going to have initialCapacity as 100 then you will have 100 buckets. You are going to calculate hashCoe() only 10 times with a spectrum of 100 buckets. The possibility of a collision is very very less.

But if you are going to supply initialCapacity for the Hashtable as 10, then the possibility of collision is very large. loadFactor decides when to automatically increase the size of the Hashtable. The default size of initialCapacity is 11 and loadFactor is .75 That if the Hashtable is 3/4 th full then the size of the Hashtable is increased.

New capacity in java Hashtable is calculated as follows:

int newCapacity = oldCapacity * 2 + 1;

If you give a lesser capacity and loadfactor and often it does the rehash() which will cause you performance issues. Therefore for efficient performance for Hashtable in java, give initialCapacity as 25% extra than you need and loadFactor as 0.75 when you instantiate.

source from http://javapapers.com/core-java/java-hashtable/#comment-37896