How HashSet works internally in Java

Hello Friends,

In this tutorial,we will see how java.util.HashSet works internally.

I would strongly recommend anybody reading this tutorial to read first How HashMap works Internally in java

HashSet is backed by a HashMap.What this statement means is that whenever we create instance of HashSet,an instance of HashMap is created in background.

HashSet class has reference variable of HashMap class as instance variable,which is declared as below

private transient HashMap<E,Object> map;

So basically whenever we instantiate HashSet using any of it's constructor,this map will be instantiated with HashMap object.




How HashMap Works internally in Java

Dear Friends,

In this post,we will discuss about java.util.HashMap.How does HashMap works internally in Java.




Fail-Safe,Fail-Fast Iterators in Java and ConcurrentModificationException

In this article ,I would try to explain FAIL-FAST and FAIL-SAFE behavior of iterators.

Let us first try to understand what is Iterator?





Iterator is an interface defined in java.util package,with following methods declared in it :

boolean hasNext();
E next();
void remove();

ArrayList Read Operations explored

Hello Friends,

In this article,we will see all the read operations which can be performed on one of the very commonly used collection i.e. ArrayList.If you want to see all the write operations which can be performed on an ArrayList,you can go through my previous article ArrayList Write operations explored.



ArrayList Write Operations explored

Hello Friends,

We will discuss today on various operations which can be performed on an ArrayList

For easy understanding,I am dividing operations into two parts:

1) Write Operations
2) Read Operations

In this article,We will discuss only on Write operations.


1) Write Operations




ArrayList features every Java developer must know

Hello Friends,

In this tutorial ,we will discuss following features of one of the very commonly and vastly used collection ArrayList.

1. What is ArrayList
2.What is the capacity of ArrayList.
3. How ArrayList capacity grows dynamically.
4. What is difference between capacity and size of ArrayList.
5. Ordered nature of ArrayList.
6. Duplicate values are allowed in ArrayList.
7. Null values are allowed in ArrayList.
8. ArrayList is not synchronized

What is ArrayList? 


Arraylist is one of the collection provided by Collection framework of Java represented by java.util.ArrayList.





We can think of ArrayList as dynamically growing array.
If we create array,we need to give size of the array on instantiation as below 
Integer[] arr = new Integer[10];

Which means that we can add maximum up to 10 elements in this array like below

arr[0] = 1;
arr[1] = 2;
.
.
arr[9] =9;

Now if we will try to add 11th element in this array as below
arr[10] = 10;
This will throw exception at run time ,something like
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
Which shows that once we have created/instantiated an array of particular size,we can add maximum number of elements equal to the defined size of array only and not more than that.

But this is not the case with ArrayList.You can instantiate an ArrayList as below and still can  add n number of elements in it.

List<String> list = new ArrayList<String>();
To understand how it happens lets see first ,

What is Capacity of ArrayList

When we instantiate an ArrayList,it is instantiated with initial capacity of 10,which means an array of size 10 is created to store 10 elements initially or in other words memory for 10 elements is allocated.

Below are the constructors of the java.util.ArrayList from source code of java.util.ArrayList,

Constructor 1 :

     /**
     * Constructs an empty list with the specified initial capacity. 
     * 
     * @param  initialCapacity  the initial capacity of the list 
     * @throws IllegalArgumentException if the specified initial capacity 
     *         is negative 
     */ 
    public ArrayList(int initialCapacity) { 
        super(); 
        if (initialCapacity < 0) 
            throw new IllegalArgumentException("Illegal Capacity: "+ 
                                               initialCapacity); 
        this.elementData = new Object[initialCapacity]; 
    }
Constructor 2 :

 /**
  * Constructs an empty list with an initial capacity of ten.
  */
  public ArrayList() {
      this(10);
  }
Instantiating way 1 :

So if we create instance of ArrayList class as below

List<String> list = new ArrayList<String>();
It will call Constructor 2,which will call constructor 1 with parameter 10.

In the first constructor below line is actually instantiating an array elementData of size 10.

this.elementData = new Object[initialCapacity];
Here elementData is an instance variable of the java.util.ArrayList class and is declared as below

/**
  * The array buffer into which the elements of the ArrayList are stored.
  * The capacity of the ArrayList is the length of this array buffer.
 */
private transient Object[] elementData;

Instantiating way 2 :

If we will instantiate ArrayList like below

List<String> list = new ArrayList<String>(-1);
It will call Constructor 1 with parameter -1.Now as in Constructor 1,it is checking that initialCapacity should not be less than zero and if so, then throw IllegalArgumentException explicitly,hence you will get following exception

java.lang.IllegalArgumentException: Illegal Capacity: -1
 at java.util.ArrayList.<init>(ArrayList.java:110)
However ,If we want to instantiate an ArrayList with initial capacity greater than 10,as we might be already aware in starting that our ArrayList is going to take large amount of data,then we can do like below


List<String> list = new ArrayList<String>(30);
Above line will call constructor 1 and will instantiate an array with size of 30.

Actually ArrayList can contain any number of items as long there is enough memory for it and when doing large initial insertions we can tell ArrayList to allocate a larger memory space to begin with to avoid wasting CPU cycles when it tries to allocate more space for the next item.

How ArrayList capacity grows dynamically ?

That is interesting question actually and answer is equally interesting :)
So say we created an ArrayList(Intial capacity 10) and added 10 elements as below

List<String> list = new ArrayList<String>();
list.add("1");
After above line, 
Size of ArrayList list : 1
Capacity of ArrayList list : 10

list.add("2");
After above line, 
Size of ArrayList list : 2
Capacity of ArrayList list : 10

list.add("3");
After above line, 
Size of ArrayList list : 3
Capacity of ArrayList list : 10
.
.
.
list.add("10");
After above line, 
Size of ArrayList list : 10
Capacity of ArrayList list : 10

So far so good,as intial capacity of ArrayList was 10,we added 10 elements in it.Now lets add 11th element in it

list.add("11");
After above line, 
Size of ArrayList list : 11
Capacity of ArrayList list : 15

Let us see how capacity increased from 10 to 15.

Below is the source code of add method which gets executed on call to add method.As you can see from within add method call is made to ensureCapacityInternal method with parameter "size+1".Here size is the size of the list i.e number of elements actually contained in the list.so when we added 11th element in the list ,parameter passed to ensureCapacityInternal will be 11(10 +1).

Source Code starts
   /**
     * Appends the specified element to the end of this list. 
     * 
     * @param e element to be appended to this list 
     * @return <tt>true</tt> (as specified by {@link Collection#add}) 
     */ 
    public boolean add(E e) { 
        ensureCapacityInternal(size + 1);  // Increments modCount!! 
        elementData[size++] = e; 
        return true; 
    } 

    private void ensureCapacityInternal(int minCapacity) { 
        modCount++; 
        // overflow-conscious code 
        if (minCapacity - elementData.length > 0) 
            grow(minCapacity); 
    } 

   /**
     * Increases the capacity to ensure that it can hold at least the 
     * number of elements specified by the minimum capacity argument. 
     * 
     * @param minCapacity the desired minimum capacity 
     */ 
    private void grow(int minCapacity) { 
        // overflow-conscious code 
        int oldCapacity = elementData.length; 
        int newCapacity = oldCapacity + (oldCapacity >> 1); 
        if (newCapacity - minCapacity < 0) 
            newCapacity = minCapacity; 
        if (newCapacity - MAX_ARRAY_SIZE > 0) 
            newCapacity = hugeCapacity(minCapacity); 
        // minCapacity is usually close to size, so this is a win: 
        elementData = Arrays.copyOf(elementData, newCapacity); 
    }
Source Code ends

Now lets see what ensureCapacityInternal method is doing.It will call grow method if following condition is true
 if (minCapacity - elementData.length > 0) 

in our case 
minCapacity = 11
elementData.length = 10

so minCapacity - elementData.length = 11-10 =1 which is greater  than zero,hence condition will be true on addition of 11th element and grow method will be called.

Now lets explore grow method

int oldCapacity = elementData.length;

in our case
oldCapacity  = 10

int newCapacity = oldCapacity + (oldCapacity >> 1); 

in our case
newCapacity =10 + 0.5*10 =15

Here >> is right shift operator which reduces a number to its half

if (newCapacity - minCapacity < 0) 
In our case
newCapacity - minCapacity = 15-11 =4 which is not less than zero hence next line inside if statement will not be called.

newCapacity = minCapacity; 

if (newCapacity - MAX_ARRAY_SIZE > 0)
 
In our case
newCapacity - MAX_ARRAY_SIZE  = 15 - 2147483639 = -2147483624,which is not greater than zero,hence next line within If statement will not be executed.
newCapacity = hugeCapacity(minCapacity); 

Note : MAX_ARRAY_SIZE is defined in ArrayList class as below
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 

Next control will reach on below line and this line will create new Array object with capacity 15 using static copyOf method of Arrays class.It will copy the elements of old array to this new array and elementData will start referring to this new Array.Hence there is increase in capacity from 10 to 15 now.
       
 elementData = Arrays.copyOf(elementData, newCapacity); 

Next time when 16th element will be added,new size will be calculated as below

15+0.5*15 = 22

and so on.

Note : Differenr JDK implementations can have different logic the way capacity increases.I am using open JDK 7 implementation here.

So we understood from above discussion that how capacity of ArrayList increases.One thing we need to understand here also is difference between capacity and size of Arraylist,which is described as below.

Difference between Size and Capacity of ArrayList

As we discussed above,ArrayList is actually backed by an array ,i.e. elements of ArrayList are actually stored in array.The capacity of ArrayList is the size of this array which stores elements of ArrayList.The capacity of ArrayList at any time will be at least equal to the size of the ArrayList,which in other words means that capacity of ArrayList can never ever be less than size of the ArrayList.This is due to the reason that whenever it's size reaches maxmimum capacity,capacity is increased by 0.5*old Capacity.

Size of arrayList is the actual number of elements contained within an ArrayList.

Lets see capacity and size of ArrayList as we add elements to it.Here getCapacity method gives capacity of ArrayList using reflection api.Here elementData in the getCapcity method is instance variable of java.util.ArrayList classs.

public static void main(String args[]){
   ArrayList<String> list = new ArrayList<String>();
   list.add("a");
   System.out.println("Capacity = " + getCapacity(list)+" "+"Size = "+list.size());
   list.add("b");
   System.out.println("Capacity = " + getCapacity(list)+" "+"Size = "+list.size());
   list.add("c");
   System.out.println("Capacity = " + getCapacity(list)+" "+"Size = "+list.size());
   list.add("d");
   System.out.println("Capacity = " + getCapacity(list)+" "+"Size = "+list.size());
   list.add("e");
   System.out.println("Capacity = " + getCapacity(list)+" "+"Size = "+list.size());
   list.add("f");
   System.out.println("Capacity = " + getCapacity(list)+" "+"Size = "+list.size());
   list.add("g");
   System.out.println("Capacity = " + getCapacity(list)+" "+"Size = "+list.size());
   list.add("h");
   System.out.println("Capacity = " + getCapacity(list)+" "+"Size = "+list.size());
   list.add("i");
   System.out.println("Capacity = " + getCapacity(list)+" "+"Size = "+list.size());
   list.add("j");
   System.out.println("Capacity = " + getCapacity(list)+" "+"Size = "+list.size());
   list.add("k");
  System.out.println("Capacity = " + getCapacity(list)+" "+"Size = "+list.size());
}

static int getCapacity(ArrayList<?> list) throws Exception {
        Field dataField = ArrayList.class.getDeclaredField("elementData");
        dataField.setAccessible(true);
        return ((Object[]) dataField.get(list)).length;
}

Output :
Capacity = 10 Size = 1
Capacity = 10 Size = 2
Capacity = 10 Size = 3
Capacity = 10 Size = 4
Capacity = 10 Size = 5
Capacity = 10 Size = 6
Capacity = 10 Size = 7
Capacity = 10 Size = 8
Capacity = 10 Size = 9
Capacity = 10 Size = 10
Capacity = 15 Size = 11



ArrayList is an ordered collection .By ordered collection ,it means that when we retrieve elements of ArrayList after inserting elements in it,the order in which elements will be retrieved will be exactly same as the order in which element would have been inserted in it.

Lets check if it is true by executing a simple program 


public static void main(String[] args) {

  List<String> list = new ArrayList<String>();
  list.add("a");
  list.add("b");
  list.add("c");
  for(int i=0;i<list.size();i++){
   System.out.println("Index:"+i+"element:"+list.get(i));
  }
  list.clear();
  System.out.println("changed Order");
  list.add("b");
  list.add("a");
  list.add("c");
  for(int i=0;i<list.size();i++){
   System.out.println("Index:"+i+"element:"+list.get(i));
  }
 }
  
Ouput :

Index:0 element:a
Index:1 element:b
Index:2 element:c
changed Order
Index:0 element:b
Index:1 element:a
Index:2 element:c



So we can see from above output that order in which we inserted elements in ArrayList,while retrieving it maintained same order.

ArrayList allows duplicates

ArrayList allows duplcate values.Lets see below example.
List<String> list = new ArrayList<String>();
list.add("GB");
list.add("GB");

System.out.println("Duplicate Values");
for(String str : list){
  System.out.println(str);
}

Output :

Duplicate Values
GB
GB

ArrayList allows null values

ArrayList allows null values as well.Lets see below below example.

List<String> list = new ArrayList<String>();
list.add("1");
list.add(null);
list.add(null);

System.out.println("Allows null Values");
for(String str : list){
   System.out.println(str);
}

Output :

Allows null Values
1
null
null

ArrayList is not synchronized 

Synchronization is the mechanism used in multi threaded environment such that only one thread can have lock on object at a time and can perform operations on the object.When we say ArrayList is not synchronized ,it means if instance of ArrayList is being used in multi threaded environment,it is possible that while one thread is adding value to it,another thread  would also be accessing this at the same time,so second thread is actually working on obsolete state of object.All the methods provided in the ArrayList class are non synchronized.However if we want to synchronize instance of ArrayList,we can do as below

We can use static synchronizedList method of Collections class.

public static void main(String[] args) {
   List<String> list = new ArrayList<String>();
  list.add("a");
  list.add("b");
  list.add("c");
  list = Collections.synchronizedList(list);
  synchronized(list){ 
   Iterator<String> itrList = list.iterator(); 
   while(itrList.hasNext()){ 
    System.out.println(itrList.next()); 
    } 
 }
}

Alternatively instead of ArrayList, we can use CopyOnWriteArrayList which is thread safe implementation of List<E> interface.

 CopyOnWriteArrayList<String> al = new CopyOnWriteArrayList<String>();
 al.add("a");
 al.add("b");
 al.add("c");
 Iterator<String> iterator = al.iterator(); 
 while (iterator.hasNext())
       System.out.println(iterator.next());
 }

Hope this article was helpful to you guys.Any feedback ,suggestions,questions are most welcome.

Various ways to iterate over commonly used collections viz ArrayList,HashMap,HashSet

Hello Friends,

In this tutorial ,we will see how to iterate over very commonly used collections viz. ArrayList, HashMap and HashSet.





1. How to iterate over an ArrayList

a)  Normal for loop

List list = new ArrayList();
list.add("a");
list.add("b");
for (int i = 0; i < list.size(); i++) {
       System.out.println(list.get(i));
}

b) Using Iterator - before Java 5

List list = new ArrayList();
list.add("a");
list.add("b");
for (Iterator itrList= list.iterator(); itrList.hasNext();) {
 System.out.println(itrList.next());
}

c) Using Iterator with For loop -After Java 5

List<String> list = new ArrayList<String>();
list.add("a");
list.add("b");
for (Iterator<String> itrList= list.iterator(); itrList.hasNext();) {
 System.out.println(itrList.next());
}

d) Using Iterator with while loop -After Java 5

List<String> list = new ArrayList<String>();
list.add("a");
list.add("b");
Iterator<String> itrList = list.iterator();
while(itrList.hasNext()){
   System.out.println(itrList.next());
}

e) Using ListIterator  

To traverse in forward direction

List<String> list = new ArrayList<String>();
list.add("a");
list.add("b");
ListIterator< String> lstItr = list.listIterator();
while(lstItr.hasNext()){
 String str = (String)lstItr.next();
 System.out.println(str);
}

To traverse in backward direction 

List<String> list = new ArrayList<String>();
list.add("a");
list.add("b"); 
ListIterator< String> lstItr = list.listIterator();
while(lstItr.hasPrevious()){
 String str = (String)lstItr.previous();
 System.out.println(str);

}

f) Using enhanced For Loop : Java 5 onwards

List<String> list = new ArrayList<String>();
list.add("a");
list.add("b");
for(String str : list){
 System.out.println(str);
}

g) using Lamda expression : Java 8 onwards

List<String> list = new ArrayList<String>();
list.add("a");
list.add("b");
list.forEach(listVal-> System.out.println(listVal));

2.How to iterate over HashMap


a) Using iterator  -Before Java 5

Map map = new HashMap();
map.put("a","a1");
map.put("b","b1");
Iterator itrMap = map.entrySet().iterator();
while (itrMap .hasNext()) {
    Map.Entry entry = (Map.Entry) itrMap.next();
    String key = (String)entry.getKey();
    String value = (String)entry.getValue();
    System.out.println("Key = " + key + ", Value = " + value);
}


b) Using iterator - After Java 5 

Map<String, String> map = new HashMap<String, String>();
map.put("a","a1");
map.put("b","b1");

Set<Entry<String,String>> entrySet = map.entrySet();
Iterator<Entry<String,String>> itrEntrySet  =entrySet .iterator();
     while (itrEntrySet.hasNext()) {
     Entry<String, String> entry = (Entry<String,String>)itrEntrySet.next();
     System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}

c) Using enhanced for loop - After Java 5 :Iterating over keys as well as values

Map<String, String> map = new HashMap<String, String>();
map.put("a","a1");
map.put("b","b1");
for (Map.Entry<String, String> entry : map.entrySet()) {
    System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}

d) Using enhanced for loop - After Java 5 :Iterating only over keys or values 

Map<String, String> map = new HashMap<String, String>();
map.put("a","a1");
map.put("b","b1");
for (String key : map.keySet()) {
    System.out.println("Key = " + key);
}
//iterating over values only
for (String value : map.values()) {
    System.out.println("Value = " + value);
}

e) Iterating over keys and searching for values 


Map<String, String> map = new HashMap<String, String>();
map.put("a","a1");
map.put("b","b1");
Map<String, String> map = new HashMap<String, String>();
for (String key : map.keySet()) {
    String value = map.get(key);
    System.out.println("Key = " + key + ", Value = " + value);
}

f) Using Lamda expression - Java 8 onwards

Map<String, String> map = new HashMap<String, String>();
map.put("a","a1");
map.put("b","b1");
map.forEach( (k,v) -> System.out.println("Key: " + k + ": Value: " + v));

3.How to iterate over HashSet

a) Using  Iterator  - Before Java 4

Set set = new HashSet();
set.add("x");
set.add("y");
Iterator itrSet = set.iterator();
while (itrSet .hasNext()) {
    System.out.println(itrSet.next());
}  

b) Using Iterator - After Java 5

Set<String> set = new HashSet<String>();
set.add("x"); 
set.add("y");
Iterator<String> itrSet = set.iterator();
while (itrSet .hasNext()) {
      System.out.println(itrSet .next());

c)Using Enhanced For loop - After Java 5

Set<String> set = new HashSet<String>();
set.add("x"); 
set.add("y");
for (String s : set) {
 System.out.println(s);
}

d) Using Lamda expression - After Java 8

Set<String> set = new HashSet<String>();
set.add("x"); 
set.add("y");
set.forEach(val ->System.out.println(val));

Hope this was helpful.Any feedback ,suggestion,questions on the post are most welcome.


How to make object eligible for garbage collection

Dear Friends,

In this tutorial I would try to explain what is garbage collection in Java and How to make objects eligible for Garbage collection.

In the language like C,a programmer need to manually do the memory management himself/herslef by allocating memory programmatically and then de-allocating memory programmatically,but Java provides automatic memory management facility,wherein a programmer need not take care of allocating/de-allocating memory,but there is utility which is part of JVM which do it for programmer automatically and we call is as Mr. Garbage Collector.Don't go on its name,it's a big guy actually,which does pretty decent job for programmer :)


What are Exceptions and types of Exceptions in Java

Hi Friends,

In this tutorial I would try to explain what are exceptions and types of exceptions in Java.

What are Exceptions?

Exception as its name suggest is the exceptional flow in your program rising due to the unexpected run time condition.For Example : FileNotFoundException.You may have written a code which would be reading a file placed at file system and source of that file is some other system.While writing code you are expecting that file at that particular location will always be there,but it is possible due to some issue in another system,that system or application would not have placed file at that location,which will result in FileNotFoundException in your program.Now this is a exceptional flow,as in normal or happy scenario, file would have been there and your program would have read the file and would have exit gracefully.Now you would like your program to complete gracefully if such kind of exceptional scenario arises.for that you can surround your code which is prone to exception by try block and can handle exceptional scenario in Catch block.






Java 7 language features - Try with Resources statement

Hi Friends,

Java has come up with really cool features in version 1.7.Code was named as Dolphin and released on July 28,2011.If you are interested in knowing history of all Java releases,you can go throw my earlier post History of java language.                                      


How to Install Java/JDK on your windows machine

Dear Friends,

Let  us see how we can install Java on a windows machine.I am taking here an example of 32 bit Windows 7 machine and the version of Java that we are going to install here is 1.6

Step 1 : Go to Oracle site .I am pasting here the direct link from where Java6 exe can be downloaded.

http://www.oracle.com/technetwork/java/javase/downloads/java-archive-downloads-javase6-419409.html#jdk-6u45-oth-JPR

Search for file name -> jdk-6u38-windows-i586.exe and download this file to your local drive.



 Step 2 : Double click on this file and following screen will open .Click on Yes.



Step 3 : An installation wizard will open as can be seen in below screenshot.Click on Next.


Step 4 : On the below screen,wizard is trying to install Java by default in C:\Program Files\Java\jdk1.6.0_38 , but if you want to change the path ,you can change here by clicking on Change... button and giving path wherever you want to install Java/Jdk. Also as you can see there should be at least 300 MB of space available for installation ,so make sure you have necessary space available.If you are fine with path and size ,Click on Next.


Step 5 : It will take some time to copy files to required path and finally you will see following screen,where it will ask for installation of JRE. You can change path for JRE installation as well by clicking on Change... button and giving your path.Click on Next


Step 6: You will see following screens.Finally click on finish on second screenshot below



Step 7 : This is time to check whether installation has happened actually or not.Go to C:\Program Files\Java and you will see following.Both JDK and JRE have been installed.


Hope this would have helped you.Your suggestions,feedback ,any further questions are welcome.