How the size of ArrayList grows dynamically?

We all know in java ArrayList does not have limit unlike Array where we can only add fixed number of elements.

ArrayList allows dynamically adding and removing the elements in this list. So question comes HOW?

By default initial capacity of an array is defined with constant DEFAULT_CAPACITY

private static final int DEFAULT_CAPACITY = 10;

If we closely look at the add method in the source code of ArrayList.java. Click here to get whole file.

public boolean add(E e)
    
{
   
     ensureCapacity(size+1);
     elementData[size++] = e;         
     return true;
}

We can see in above code that before adding the element into the ArrayList its calling one method named “ensureCapacity”. This method makes sure what is the current size of the existing elements containing in the array and what is the maximum allowed size for the array at this point of time?

So if we are trying to add more element than its maximum allowed size then maximum allowed size needs to be increased in order to accommodate new elements.

But here we must notice that “elementData” is an array only and array does not grow dynamically.

private transient Object[] elementData; 

Here is the main thing to notice

Internally new array is created with new capacity and then elements from existing array are copied to the new array with bigger capacity.

elementData = Arrays.copyOf(elementData, newCapacity);

New capacity is calculated with below expression:

int newCapacity = (oldCapacity * 3)/2 + 1;

If you want to see this happening, You can try to execute the below code snippet in debug mode and monitor elementData array as shown in below figure.

package com.javageekzone.collection;

import java.util.ArrayList;
import java.util.List;

public class ArrayListExample 
{
 public static void main(String[] args) 
 {
  List list = new ArrayList();

  for (int counter = 1; counter < 1000; counter++) 
  {
   list.add(counter);
  }
 }
}

I hope you now know how the size of ArrayList grows dynamically. Please let me know by comments if you still have any doubts.

Cheers!!!

Read More

Why Set does not allow duplicate value?

In most of the interviews of Java, We are often checked with the in depth knowledge of Collection APIs and its capabilities.

One of the very famous interview questions is: Why Set does not allow duplicate value?

Now, don’t tell me you were also asked the same

We all know Set theory in mathematics that all elements in Set are always unique. The same has been applied to the Set API. Let’s try to understand this with very small java code snippet.

Basically I want to add elements in Set where I want to try adding some duplicates as well as shown below.

package com.javageekzone.collection;

import java.util.HashSet;
import java.util.Set;

public class DuplicateSetElements {
public static void main(String[] args) {
 
 Set subjects=new HashSet();
 
 
 subjects.add("Spring");
 subjects.add("Java");
 subjects.add("Oracle");
 
 System.out.println("Subjects: "+subjects);
 
 subjects.add("Java");
 subjects.add("Cobol");
 subjects.add("Spring");
 
 System.out.println("Subjects: "+subjects);
}
}

In above code we are invoking add method to insert the element. Let’s see the source code of this method in the class HashSet.java.

public class HashSet&ltE&gt extends AbstractSet&ltE&gt implements Set&ltE&gt, Cloneable, java.io.Serializable
{
    private transient HashMap&ltE,Object&gt map;
    
    // Dummy value to associate with an Object in the backing Map
    
    private static final Object PRESENT = new Object();
    
    
    
    public HashSet() {
        map = new HashMap<>();
    }
    
    // More Code goes here ,i.e Other methods in Hash Set
    
    
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
    
    
    
    // More Code goes here ,i.e Other methods in Hash Set
}

Above code is part of rt.jar file in your jre under java/util package. Click here to get full code.

You can see below facts in the HashSet.java

1. When you instantiate HashSet it’s actually instantiating HashMap in the constructor
2. PRESENT is the member variable of the HashSet which is instantiated with type Object and it acts as dummy value which it passes to put method.
3. In the add method implementation internally its calling put method of the HashMap.
4. put method is considering actual value passed in add method as key and PRESENT as value.

So if I try to add the element “java” by add method.

subject.add(“java”)

It will put that element E here “java” as a key in the HashMap and the dummy value PRESENT as a value to the key.

Now if you look at the code of the HashMap’s put(Key k,Value V) method , you will see put method something like this

public V put(K key, V value) 

{

    //Some code goes here

}

Here we can notice that put (key,value) will

1. return NULL if the key is unique and the element is added to the map.
2. return old value of the key if key is duplicate.

Hence , in HashSet add() method ,  it check the return value of map.put(key,value) method with null value i.e

public boolean add(E e) 

{

    return map.put(e, PRESENT)==null;

}

So , if map.put(key,value) returns null ,then

map.put(e, PRESENT)==null will return true and element is added to the HashSet.

So, if map.put(key,value) returns old value of the key ,then

map.put(e, PRESENT)==null will return false and element is  not added to the HashSet .

Conclusion: HashSet internally utilize HashMap to facilitate the storage and uniqueness of the element.

I hope you are clear with this internal mechanism now. If you still have any doubt please feel free to contact me.

Cheers!!!

Read More