Java Training Classes By Quontra Solutions: November 2014

Monday, 24 November 2014

How HashSet works in java

HashSet:

HashSet implements Set interface which does not allow duplicate value.It is not synchronized and is not thread safe.
Definition of duplicate can be quite tricky sometimes.Lets consider two cases here.

In case of primitive types(such as interger, String)
In case of custom defined objects.

In case of primitive types:

In case of primitives type, it is very straight forward.Lets see with help of example:

Lets create a java program:

view plainprint?

package org.arpit.java2blog;
import java.util.HashSet;
public class HashSetMain {
public static void main(String[] args) {
HashSet<String> nameSet=new HashSet<String>();
nameSet.add(“Arpit”);
nameSet.add(“Arpit”);
nameSet.add(“john”);
System.out.println(“size of nameSet=”+nameSet.size());
System.out.println(nameSet);
}
}

When you run above program, you will get following output:

view plainprint?

size of nameSet=2
[Arpit, john]

So we tried to add String “Arpit” twice, but as HashSet does not allow duplicate value, it will add “Arpit” once in HashSet
In case of Custom Objects:
For understanding how HashSet will work in case of custom objects, you need to understand hashcode and equals method in java.Lets create a class called Country and implement only equals method in it.

view plainprint?

package org.arpit.java2blog;
public class Country {
String name;
long population;
public String getName() {
return name;
}
public void setName(String name){
this.name = name;
}
public long getPopulation() {
return population;
}
public void setPopulation(long population) {
this.population = population;
}
public String toString()
{
return name;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Country other = (Country) obj;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
}

create main class:

view plainprint?

package org.arpit.java2blog;
import java.util.HashSet;
public class HashSetCountryMain {
public static void main(String[] args)
{
HashSet<Country> countrySet=new HashSet<Country>();
Country india1=new Country();
india1.setName(“India”);
Country india2=new Country();
india2.setName(“India”);
countrySet.add(india1);
countrySet.add(india2);
System.out.println(“size of nameSet=”+countrySet.size());
System.out.println(countrySet);
}
}

When you run above program, you will get following output:

view plainprint?

size of nameSet=2
[India, India]

Now you must be wondering even through two objects are equal why HashSet contains two values instead of one.This is because First HashSet calculates hashcode for that key object, if hashcodes are same then only it checks for equals method and because hashcode for above two country objects uses default hashcode method,Both will have different memory address hence different hashcode.
Now lets add hashcode method in above Country class

view plainprint?

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}

Run above main program again, you will get following output:

view plainprint?

size of nameSet=1
[India]

So now we have good understanding of HashSet, lets see its internal representation:

Internal working of HashSet:

When you add any duplicate element to HashSet, add() method returns false and do not add duplicate element to HashSet.

How add method return false? For this, we need to see HashSet’s add method in JavaAPI

view plainprint?

public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
private transient HashMap<E,Object> map;
// PRESENT is dummy value which will be used as value in map
private static final Object PRESENT = new Object();
/**
* Constructs a empty map.so hash
*
*/
public HashSet() {
map = new HashMap<E,Object>();
}
// return false if e is already present in HashSet
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
// other HashSet methods
}

So from above code, It is clear that HashSet uses HashMap for checking duplicate elements.As we know that in HashMap , key should be unique. So HashSet uses this concept, When element is added to HashSet, it is added to internal HashMap as Key.This HashMap required some value so a dummy Object(PRESENT) is used as value in this HashMap.
PRESENT is dummy value which is used value for internal map.
Lets see add method:

view plainprint?

// return false if e is already present in HashSet
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

So here there will be two cases

map.put(e,PRESENT) will return null, if element not present in that map. So map.put(e, PRESENT) == null will return true ,hence add method will return true and element will be added in HashSet.
map.put(e,PRESENT) will return old value ,if element is already present in that map. So map.put(e, PRESENT) == null will return false, hence add method will return false and element will not be added in HashSet.

For more Visit: http://www.quontrasolutions.com/blog/category/java

Difference between ArrayList and Vector in java

ArrayList

ArrayList is implementation of list interface.
ArrayList is not synchonized(so not thread safe)
ArrayList is implemented using array as internal data structure.It can be dynamically resized .
ArrayList increases half of its size when its size is increased.

Vector

Vector is implementation of list interface.
Vector is synchonized(so thread safe)
Vector is implemented using array as internal data structure.It can be dynamically resized.
Vector doubles size of array when its size is increased.

ArrayList vs Vector:

Parameter	Vector	ArrayList
Synchonized	Yes	No
ThreadSafe	Yes	No
Performance	It is slower than arraylist	It is faster than Vector
Changes in internal size of array when resized	Vector doubles size of its internal array when its size is increased	ArrayList increases half of its size when its size is increased.

Which is better? ArrayList or Vector?

It actually depends on our need.Vector is slower than ArrayList as its methods are synchronized so if we don’t work in multi threaded environment then ArrayList is better choice.

Best Practice:

When we initialize ArrayList or Vector,always initialize with largest capacity java program will need as incrementing size is costlier operation.

Can we synchronize ArrayList?

Yes,ArrayList can also be synchonized with help of method Collections.synchronizedList(arraylist)

For more Visit: http://www.quontrasolutions.com/blog/category/java

Comparable in java

Comparable interface:

Class whose objects to be sorted must implement this interface.In this,we have to implement compareTo(Object) method.
For example:

view plainprint?

public class Country implements Comparable<Country>{
@Override
public int compareTo(Country country) {
return (this.countryId < country.countryId ) ? -1: (this.countryId > country.countryId ) ? 1:0 ;
}}

If any class implements comparable inteface then collection of that object can be sorted automatically using Collection.sort() or Arrays.sort().Object will be sort on the basis of compareTo method in that class.
Objects which implement Comparable in java can be used as keys in a SortedMap like TreeMap or SortedSet like TreeSet without implementing any other interface.
Sorting logic must be in same class whose objects are being sorted. Hence this is called natural ordering of objects

Java code:

For Comparable:

We will create class country having attribute id and name.This class will implement Comparable interface and implement CompareTo method to sort collection of country object by id.
1. Country.java

view plainprint?

package org.arpit.java2blog;
//If this.cuntryId < country.countryId:then compare method will return -1
//If this.countryId > country.countryId:then compare method will return 1
//If this.countryId==country.countryId:then compare method will return 0
public class Country implements Comparable<Country>{
int countryId;
String countryName;
public Country(int countryId, String countryName) {
super();
this.countryId = countryId;
this.countryName = countryName;
}
@Override
public int compareTo(Country country) {
return (this.countryId < country.countryId ) ? -1: (this.countryId > country.countryId ) ? 1:0 ;
}
public int getCountryId() {
return countryId;
}
public void setCountryId(int countryId) {
this.countryId = countryId;
}
public String getCountryName() {
return countryName;
}
public void setCountryName(String countryName) {
this.countryName = countryName;
}
}

2.ComparableMain.java

view plainprint?

package org.arpit.java2blog;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class ComparableMain {
/**
* @author Arpit Mandliya
*/
public static void main(String[] args) {
Country indiaCountry=new Country(1, “India”);
Country chinaCountry=new Country(4, “China”);
Country nepalCountry=new Country(3, “Nepal”);
Country bhutanCountry=new Country(2, “Bhutan”);
List<Country> listOfCountries = new ArrayList<Country>();
listOfCountries.add(indiaCountry);
listOfCountries.add(chinaCountry);
listOfCountries.add(nepalCountry);
listOfCountries.add(bhutanCountry);
System.out.println(“Before Sort : “);
for (int i = 0; i < listOfCountries.size(); i++) {
Country country=(Country) listOfCountries.get(i);
System.out.println(“Country Id: “+country.getCountryId()+“||”+“Country name: “+country.getCountryName());
}
Collections.sort(listOfCountries);
System.out.println(“After Sort : “);
for (int i = 0; i < listOfCountries.size(); i++) {
Country country=(Country) listOfCountries.get(i);
System.out.println(“Country Id: “+country.getCountryId()+“|| “+“Country name: “+country.getCountryName());
}
}
}

Output:

view plainprint?

Before Sort :
Country Id: 1||Country name: India
Country Id: 4||Country name: China
Country Id: 3||Country name: Nepal
Country Id: 2||Country name: Bhutan
After Sort :
Country Id: 1|| Country name: India
Country Id: 2|| Country name: Bhutan
Country Id: 3|| Country name: Nepal
Country Id: 4|| Country name: China

For more Visit: http://www.quontrasolutions.com/blog/category/java

Difference between Comparator and Comparable in java

Comparable interface:

Class whose objects to be sorted must implement this interface.In this,we have to implement compareTo(Object) method.
For example:

view plainprint?

public class Country implements Comparable<Country>{
@Override
public int compareTo(Country country) {
return (this.countryId < country.countryId ) ? -1: (this.countryId > country.countryId ) ? 1:0 ;
}}

Comparator interface:

Class whose objects to be sorted do not need to implement this interface.Some third class can implement this interface to sort.e.g.CountrySortByIdComparator class can implement Comparator interface to sort collection of country object by id. For example:

view plainprint?

public class CountrySortByIdComparator implements Comparator<Country>{
@Override
public int compare(Country country1, Country country2) {
return (country1.getCountryId() < country2.getCountryId() ) ? -1: (country1.getCountryId() > country2.getCountryId() ) ? 1:0 ;
}
}

Using Comparator interface,we can write different sorting based on different attributes of objects to be sorted.You can use anonymous comparator to compare at particular line of code. For example:

view plainprint?

Country indiaCountry=new Country(1, “India”);
Country chinaCountry=new Country(4, “China”);
Country nepalCountry=new Country(3, “Nepal”);
Country bhutanCountry=new Country(2, “Bhutan”);
List<Country> listOfCountries = new ArrayList<Country>();
listOfCountries.add(indiaCountry);
listOfCountries.add(chinaCountry);
listOfCountries.add(nepalCountry);
listOfCountries.add(bhutanCountry);
//Sort by countryName
Collections.sort(listOfCountries,new Comparator<Country>() {
@Override
public int compare(Country o1, Country o2) {
return o1.getCountryName().compareTo(o2.getCountryName());
}
});

Comparator vs Comparable

Parameter	Comparable	Comparator
Sorting logic	Sorting logic must be in same class whose objects are being sorted. Hence this is called natural ordering of objects	Sorting logic is in separate class. Hence we can write different sorting based on different attributes of objects to be sorted. E.g. Sorting using id,name etc.
Implementation	Class whose objects to be sorted must implement this interface.e.g Country class needs to implement comparable to collection of country object by id	Class whose objects to be sorted do not need to implement this interface.Some other class can implement this interface. E.g.-CountrySortByIdComparator class can implement Comparator interface to sort collection of country object by id
Sorting method	int compareTo(Object o1) This method compares this object with o1 object and returns a integer.Its value has following meaning 1. positive – this object is greater than o1 2. zero – this object equals to o1 3. negative – this object is less than o1	int compare(Object o1,Object o2) This method compares o1 and o2 objects. and returns a integer.Its value has following meaning. 1. positive – o1 is greater than o2 2. zero – o1 equals to o2 3. negative – o1 is less than o1
Calling method	Collections.sort(List) Here objects will be sorted on the basis of CompareTo method	Collections.sort(List, Comparator) Here objects will be sorted on the basis of Compare method in Comparator
Package	Java.lang.Comparable	Java.util.Comparator

Java code:

For Comparable:

We will create class country having attribute id and name.This class will implement Comparable interface and implement CompareTo method to sort collection of country object by id.

1. Country.java

view plainprint?

package org.arpit.javapostsforlearning;
//If this.cuntryId < country.countryId:then compare method will return -1
//If this.countryId > country.countryId:then compare method will return 1
//If this.countryId==country.countryId:then compare method will return 0
public class Country implements Comparable<Country>{
int countryId;
String countryName;
public Country(int countryId, String countryName) {
super();
this.countryId = countryId;
this.countryName = countryName;
}
@Override
public int compareTo(Country country) {
return (this.countryId < country.countryId ) ? -1: (this.countryId > country.countryId ) ? 1:0 ;
}
public int getCountryId() {
return countryId;
}
public void setCountryId(int countryId) {
this.countryId = countryId;
}
public String getCountryName() {
return countryName;
}
public void setCountryName(String countryName) {
this.countryName = countryName;
}
}

2.ComparableMain.java

view plainprint?

package org.arpit.javapostsforlearning;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class ComparableMain {
/**
* @author Arpit Mandliya
*/
public static void main(String[] args) {
Country indiaCountry=new Country(1, “India”);
Country chinaCountry=new Country(4, “China”);
Country nepalCountry=new Country(3, “Nepal”);
Country bhutanCountry=new Country(2, “Bhutan”);
List<Country> listOfCountries = new ArrayList<Country>();
listOfCountries.add(indiaCountry);
listOfCountries.add(chinaCountry);
listOfCountries.add(nepalCountry);
listOfCountries.add(bhutanCountry);
System.out.println(“Before Sort : “);
for (int i = 0; i < listOfCountries.size(); i++) {
Country country=(Country) listOfCountries.get(i);
System.out.println(“Country Id: “+country.getCountryId()+”||”+”Country name: “+country.getCountryName());
}
Collections.sort(listOfCountries);
System.out.println(“After Sort : “);
for (int i = 0; i < listOfCountries.size(); i++) {
Country country=(Country) listOfCountries.get(i);
System.out.println(“Country Id: “+country.getCountryId()+”|| “+”Country name: “+country.getCountryName());
}
}
}

Output:

view plainprint?

Before Sort :
Country Id: 1||Country name: India
Country Id: 4||Country name: China
Country Id: 3||Country name: Nepal
Country Id: 2||Country name: Bhutan
After Sort :
Country Id: 1|| Country name: India
Country Id: 2|| Country name: Bhutan
Country Id: 3|| Country name: Nepal
Country Id: 4|| Country name: China

For Comparator:

We will create class country having attribute id and name and will create another class CountrySortByIdComparator which will implement Comparator interface and implement compare method to sort collection of country object by id and we will also see how to use anonymous comparator.

1.Country.java

view plainprint?

package org.arpit.javapostsforlearning;
public class Country{
int countryId;
String countryName;
public Country(int countryId, String countryName) {
super();
this.countryId = countryId;
this.countryName = countryName;
}
public int getCountryId() {
return countryId;
}
public void setCountryId(int countryId) {
this.countryId = countryId;
}
public String getCountryName() {
return countryName;
}
public void setCountryName(String countryName) {
this.countryName = countryName;
}
}

2.CountrySortbyIdComparator.java

view plainprint?

package org.arpit.javapostsforlearning;
import java.util.Comparator;
//If country1.getCountryId()<country2.getCountryId():then compare method will return -1
//If country1.getCountryId()>country2.getCountryId():then compare method will return 1
//If country1.getCountryId()==country2.getCountryId():then compare method will return 0
public class CountrySortByIdComparator implements Comparator<Country>{
@Override
public int compare(Country country1, Country country2) {
return (country1.getCountryId() < country2.getCountryId() ) ? -1: (country1.getCountryId() > country2.getCountryId() ) ? 1:0 ;
}
}

3.ComparatorMain.java

view plainprint?

package org.arpit.javapostsforlearning;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class ComparatorMain {
/**
* @author Arpit Mandliya
*/
public static void main(String[] args) {
Country indiaCountry=new Country(1, “India”);
Country chinaCountry=new Country(4, “China”);
Country nepalCountry=new Country(3, “Nepal”);
Country bhutanCountry=new Country(2, “Bhutan”);
List<Country> listOfCountries = new ArrayList<Country>();
listOfCountries.add(indiaCountry);
listOfCountries.add(chinaCountry);
listOfCountries.add(nepalCountry);
listOfCountries.add(bhutanCountry);
System.out.println(“Before Sort by id : “);
for (int i = 0; i < listOfCountries.size(); i++) {
Country country=(Country) listOfCountries.get(i);
System.out.println(“Country Id: “+country.getCountryId()+”||”+”Country name: “+country.getCountryName());
}
Collections.sort(listOfCountries,new CountrySortByIdComparator());
System.out.println(“After Sort by id: “);
for (int i = 0; i < listOfCountries.size(); i++) {
Country country=(Country) listOfCountries.get(i);
System.out.println(“Country Id: “+country.getCountryId()+”|| “+”Country name: “+country.getCountryName());
}
//Sort by countryName
Collections.sort(listOfCountries,new Comparator<Country>() {
@Override
public int compare(Country o1, Country o2) {
return o1.getCountryName().compareTo(o2.getCountryName());
}
});
System.out.println(“After Sort by name: “);
for (int i = 0; i < listOfCountries.size(); i++) {
Country country=(Country) listOfCountries.get(i);
System.out.println(“Country Id: “+country.getCountryId()+”|| “+”Country name: “+country.getCountryName());
}
}
}

Output:

view plainprint?

Before Sort by id :
Country Id: 1||Country name: India
Country Id: 4||Country name: China
Country Id: 3||Country name: Nepal
Country Id: 2||Country name: Bhutan
After Sort by id:
Country Id: 1|| Country name: India
Country Id: 2|| Country name: Bhutan
Country Id: 3|| Country name: Nepal
Country Id: 4|| Country name: China
After Sort by name:
Country Id: 2|| Country name: Bhutan
Country Id: 4|| Country name: China
Country Id: 1|| Country name: India
Country Id: 3|| Country name: Nepal

For more Visit: http://www.quontrasolutions.com/blog/category/java

Difference between HashMap and HashSet in java

HashMap

HashMap implements Map interface which maps key to value.It is not synchronized and is not thread safe.Duplicate keys are not allowed and null keys as well as values are allowed. For more details, you can also read How HashMap works in java.
view plainprint?

HashMap<Interger,String> employeeHashmap=new HashMap<Integer,String>();
employeeHashmap.put(1,”Arpit”);
employeeHashmap.put(2,”John”);

HashSet

HashSet implements Set interface which does not allow duplicate value.It is not synchronized and is not thread safe.For more details, you can also read How HashSet works in java.
view plainprint?

HashSet<String> employeeSet=new HashSet<String>();
employeeSet.add(“Arpit”);
employeeSet.add(“Arpit”);
employeeSet.add(“john”);

Above employeeSet will have 2 elements in it as Set does not allow duplicate values.
add method is used to add element to HashSet.If It return true then element is added successfully but if it return false then you are trying to insert duplicate value.
view plainprint?

public boolean add(Object o)

One main thing about HashSet is objects which we are going to add in HashSet must implement Hashcode() and equals() method so that we can check for duplicate values.If we are adding custom objects to HashSet then we must override() Hashcode() and equals() method according to our need.If we do not override then object will take default implementation which may not desirable.

HashMap vs HashSet:

Parameter	HashMap	HashSet
Interface	This is core difference among them.HashMap implements Map interface	HashSet implement Set interface
Method for storing data	It stores data in a form of key->value pair.So it uses put(key,value) method for storing data	It uses add(value) method for storing data
Duplicates	HashMap allows duplicate value but not duplicate keys	HashSet does not allow duplicate values.
Performance	It is faster than hashset as values are stored with unique keys	It is slower than HashMap
HashCode Calculation	In hash map hashcode value is calculated using key object	In this,hashcode is calculated on the basis of value object.Hashcode can be same for two value object so we have to implement equals() method.If equals() method return false then two objects are different.

How HashMap works in java

Most common interview questions are “How HashMap works in java”, “How get and put method of HashMap work internally”. Here I am trying to explain internal functionality with an easy example. Rather than going through theory, we will start with example first, so that you will get better understanding and then we will see how get and put function work in java.

Lets take a very simple example. I have a Country class, we are going to use Country class object as key and its capital name(string) as value. Below example will help you to understand, how these key value pair will be stored in hashmap.

1. Country.java

view plainprint?

package org.arpit.java2blog;
public class Country {
String name;
long population;
public Country(String name, long population) {
super();
this.name = name;
this.population = population;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public long getPopulation() {
return population;
}
public void setPopulation(long population) {
this.population = population;
}
// If length of name in country object is even then return 31(any random number) and if odd then return 95(any random number).
// This is not a good practice to generate hashcode as below method but I am doing so to give better and easy understanding of hashmap.
@Override
public int hashCode() {
if(this.name.length()%2==0)
return 31;
else
return 95;
}
@Override
public boolean equals(Object obj) {
Country other = (Country) obj;
if (name.equalsIgnoreCase((other.name)))
return true;
return false;
}
}

If you want to understand more about hashcode and equals method of object, you may refer hashcode() and equals() method in java
2. HashMapStructure.java(main class)

view plainprint?

import java.util.HashMap;
import java.util.Iterator;
public class HashMapStructure {
/**
* @author Arpit Mandliya
*/
public static void main(String[] args) {
Country india=new Country(“India”,1000);
Country japan=new Country(“Japan”,10000);
Country france=new Country(“France”,2000);
Country russia=new Country(“Russia”,20000);
HashMap<country tring=“”> countryCapitalMap=new HashMap<country tring=“”>();
countryCapitalMap.put(india,“Delhi”);
countryCapitalMap.put(japan,“Tokyo”);
countryCapitalMap.put(france,“Paris”);
countryCapitalMap.put(russia,“Moscow”);
Iterator<country> countryCapitalIter=countryCapitalMap.keySet().iterator();//put debug point at this line
while(countryCapitalIter.hasNext())
{
Country countryObj=countryCapitalIter.next();
String capital=countryCapitalMap.get(countryObj);
System.out.println(countryObj.getName()+“—-“+capital);
}
}
}
</country></country></country>

Now put debug point at line 23 and right click on project->debug as-> java application. Program will stop execution at line 23 then right click on countryCapitalMap then select watch.You will be able to see structure as below.

Now From above diagram, you can observe following points

There is an Entry[] array called table which has size 16.
This table stores Entry class’s object. HashMap class has a inner class called Entry.This Entry have key value as instance variable. Lets see structure of entry class Entry Structure.

view plainprint?

static class Entry implements Map.Entry
{
final K key;
V value;
Entry next;
final int hash;
…//More code goes here
}

Whenever we try to put any key value pair in hashmap, Entry class object is instantiated for key value and that object will be stored in above mentioned Entry[](table). Now you must be wondering, where will above created Enrty object get stored(exact position in table). The answer is, hash code is calculated for a key by calling Hascode() method. This hashcode is used to calculate index for above Entry[] table.
Now, If you see at array index 10 in above diagram, It has an Entry object named HashMap$Entry.
We have put 4 key-values in hashmap but it seems to have only 2!!!!This is because if two objects have same hashcode, they will be stored at same index. Now question arises how? It stores objects in a form of LinkedList(logically).

So how hashcode of above country key-value pairs are calculated.

view plainprint?

Hashcode for Japan = 95 as its length is odd.
Hashcode for India =95 as its length is odd
HashCode for Russia=31 as its length is even.
HashCode for France=31 as its length is even.

Below diagram will explain LinkedList concept clearly.

So now if you have good understanding of hashmap structure,Lets go through put and get method.

Put :

Lets see implementation of put method:

view plainprint?

/**
* 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;
}

now lets understand above code step by step

Key object is checked for null. If key is null then it will be stored at table[0] because hashcode for null is always 0.
Key object’s hashcode() method is called and hash code is calculated. This hashcode is used to find index of array for storing Entry object. It may happen sometimes that, this hashcode function is poorly written so JDK designer has put another function called hash() which takes above calculated hash value as argument.If you want to learn more about hash() function, you can refer hash and indexFor method in hashmap.
indexFor(hash,table.length) is used to calculate exact index in table array for storing the Entry object.
As we have seen in our example, if two key objects have same hashcode(which is known as collision) then it will be stored in form of linkedlist.So here, we will iterate through our linkedlist.

If there is no element present at that index which we have just calculated then it will directly put our Entry object at that index.
If There is element present at that index then it will iterate until it gets Entry->next as null.Then current Entry object become next node in that linkedlist
What if we are putting same key again, logically it should replace old value. Yes,it will do that.While iterating it will check key equality by calling equals() method(key.equals(k)), if this method returns true then it replaces value object with current Entry’s value object.

Get:

Lets see implementation of get now:

view plainprint?

/**
* Returns the value to which the specified key is mapped, or {@code null}
* if this map contains no mapping for the key.
*
*
* 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.)
*
*
* A return value of {@code null} does not necessarily 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;
}

As you got the understanding on put functionality of hashmap. So to understand get functionality is quite simple. If you pass any key to get value object from hashmap.

Key object is checked for null. If key is null then value of Object resides at table[0] will be returned.
Key object’s hashcode() method is called and hash code is calculated.
indexFor(hash,table.length) is used to calculate exact index in table array using generated hashcode for getting the Entry object.
After getting index in table array, it will iterate through linkedlist and check for key equality by calling equals() method and if it returns true then it returns the value of Entry object else returns null.

Key points to Remeber:

HashMap has a inner class called Entry which stores key-value pairs.
Above Entry object is stored in Entry[ ](Array) called table
An index of table is logically known as bucket and it stores first element of linkedlist
Key object’s hashcode() is used to find bucket of that Entry object.
If two key object ‘s have same hashcode , they will go in same bucket of table array.
Key object ‘s equals() method is used to ensure uniqueness of key object.
Value object ‘s equals() and hashcode() method is not used at all

For more Visit: http://www.quontrasolutions.com/blog/category/java

How HashSet works in java

HashSet:

In case of primitive types(such as interger, String)
In case of custom defined objects.

In case of primitive types:

In case of primitives type, it is very straight forward.Lets see with help of example:

Lets create a java program:

view plainprint?

package org.arpit.java2blog;
import java.util.HashSet;
public class HashSetMain {
public static void main(String[] args) {
HashSet<String> nameSet=new HashSet<String>();
nameSet.add(“Arpit”);
nameSet.add(“Arpit”);
nameSet.add(“john”);
System.out.println(“size of nameSet=”+nameSet.size());
System.out.println(nameSet);
}
}

When you run above program, you will get following output:

view plainprint?

size of nameSet=2
[Arpit, john]

view plainprint?

package org.arpit.java2blog;
public class Country {
String name;
long population;
public String getName() {
return name;
}
public void setName(String name){
this.name = name;
}
public long getPopulation() {
return population;
}
public void setPopulation(long population) {
this.population = population;
}
public String toString()
{
return name;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Country other = (Country) obj;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
}

create main class:

view plainprint?

package org.arpit.java2blog;
import java.util.HashSet;
public class HashSetCountryMain {
public static void main(String[] args)
{
HashSet<Country> countrySet=new HashSet<Country>();
Country india1=new Country();
india1.setName(“India”);
Country india2=new Country();
india2.setName(“India”);
countrySet.add(india1);
countrySet.add(india2);
System.out.println(“size of nameSet=”+countrySet.size());
System.out.println(countrySet);
}
}

When you run above program, you will get following output:

view plainprint?

size of nameSet=2
[India, India]

view plainprint?

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}

Run above main program again, you will get following output:

view plainprint?

size of nameSet=1
[India]

So now we have good understanding of HashSet, lets see its internal representation:

Internal working of HashSet:

When you add any duplicate element to HashSet, add() method returns false and do not add duplicate element to HashSet.

How add method return false? For this, we need to see HashSet’s add method in JavaAPI

view plainprint?

public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
private transient HashMap<E,Object> map;
// PRESENT is dummy value which will be used as value in map
private static final Object PRESENT = new Object();
/**
* Constructs a empty map.so hash
*
*/
public HashSet() {
map = new HashMap<E,Object>();
}
// return false if e is already present in HashSet
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
// other HashSet methods
}

view plainprint?

// return false if e is already present in HashSet
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

So here there will be two cases

map.put(e,PRESENT) will return null, if element not present in that map. So map.put(e, PRESENT) == null will return true ,hence add method will return true and element will be added in HashSet.
map.put(e,PRESENT) will return old value ,if element is already present in that map. So map.put(e, PRESENT) == null will return false, hence add method will return false and element will not be added in HashSet.

For more Visit: http://www.quontrasolutions.com/blog/category/java

hash and indexFor method in HashMap

This post is for the people who already have good understanding of how HashMap works in java and want to understand more about hash and indexFor method.In this post, we will see how hash and indexFor method works internally in hashmap. hash and indexFor methods belong to HashMap class. Why JDK developers need to have another hash function when key object’s have there own hashcode method.
Lets see code for hash and indexFor

view plainprint?

/**
* Applies a supplemental hash function to a given hashCode, which
* defends against poor quality hash functions. This is critical
* because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}

As java doc says about hash:
Applies a supplemental hash function to a given hashCode, which defends against poor quality hash functions. This is critical because HashMap uses power-of-two length hash tables, that otherwise encounter collisions for hashCodes that do not differ in lower bits. Note: Null keys always map to hash 0, thus index 0.
Lets understand this with the help of example: Lets say key object’s hashcode() returns only 3 values 31,63 and 95. 31,63 and 95 are integers, so all are 32 bits.
31=00000000000000000000000000011111
63=00000000000000000000000000111111
95=00000000000000000000000001011111
Now lets say our hashmap’s lenth is 16(2^4, Hashmap’s length will be always in power of two)

What if we do not use hash function:

Now if we do not use hash function then

indexFor will return :

31=00000000000000000000000000011111 => 1111=15
63=00000000000000000000000000111111 => 1111=15
95=00000000000000000000000001011111 => 1111=15
Why so?
because when we call indexFor function.It will do AND between 31&15 , 63&15 and 95&15.
For ex. 95&15
00000000000000000000000001011111 &00000000000000000000000000001111
so (2^n-1) will always have sequence of 1’s in it.so what matters here it last n bits as 0&1 is always 0.
In above example, all have 1111 in end that is why they are returning same index.
so although we have different hashcode,each Entry object will be stored at 15 index only.

What if we use hash function:

If we use hash function then :

On each hashcode, first hash will be applied.

31=00000000000000000000000000011111 => 00000000000000000000000000011110
63=00000000000000000000000000111111 => 00000000000000000000000000111100
95=00000000000000000000000001011111 => 00000000000000000000000001011010
now after passing new hash to indexFor.It will return :
00000000000000000000000000011110 =>1110=14
00000000000000000000000000111100 =>1100=12
00000000000000000000000001011010 =>1010=10
After applying hash function, above hashcodes are returning different index so hash function is redistributing elements in hashmap thus less collisions and better performance.
The main purpose of hash operation is to make the hashcode differences visible in the least significant bits so that the hashmap elements can be distributed evenly across the buckets

Read more at http://www.java2blog.com/2014/02/hash-and-indexfor-method-in-hashmap.html#L3QvIz8dX3KEIlM3.99

For more Visit: http://www.quontrasolutions.com/blog/category/java