Tag Archives: hashcode and equals contract

Java: HashCode and Equals Contract


In Java java.lang.Object is the superclass of all the classes provides two very important methods :

public boolean equals(Object obj)
public int hashCode()

See Also:

Internally these methods are used when need to check equality of objects but developer implementation prospects mainly used when need to implement HashMap because on that time developers have to implement these methods inside your User Defined class. Lot’s of the time when the developer is not aware of the contract of hashcode() and equals() method they make mistake and not received expected results from HashMap. Before going to detail of hashcode() and equals() contract, Let’s discuss first the problems.

Most Common Problem

In this example,  green and red car object is stored successfully in a HashMap, but when the map is asked to retrieve this green car object, the car object is not found in map and returning as null.

import java.util.HashMap;
import java.util.Map;

public class Car {
	private String color;

	public Car(String color) {
		this.color = color;
	}

	public boolean equals(Object obj) {
		if (!(obj instanceof Car))
			return false;
		if (obj == this)
			return true;
		return this.color.equals(((Car) obj).color);
	}
	public static void main(String[] args) {
		Car a1 = new Car("green");//hashcode
		Car a2 = new Car("red");

		// HashMap stores car type and its quantity
		Map m = new HashMap();
		m.put(a1, 10);
		m.put(a2, 20);
		//hashcode diffrent from previos green object consider different object
		System.out.println(m.get(new Car("green")));
	}
}
         

Output

null

The above program prints as null. However, we can check that this car object is stored in the map by inspecting in the debugger:

Java hashCode and Equals Contract

In the above program problem is hashcode() method was not implemented.

Before going to the solution to this problem in detail. We need to understand the equals() and hashcode() method contract.

hashcode() and equals() Method Contract

The contract between equals() and hasCode() is that:

  1.  If two objects are equal, then they must have the same hash code value.
  2.  If two objects have the same hashcode value, they may or may not be equal.

The main idea is Map worked on hashing techniques to find an object faster in comparison to linear search. In this case, because the hashcode() method is no implemented. It will call by default method of object class i.e return different hashcode value for different objects. In this above case both the objects store in HashMap and retrieving will have different hashcode values.

See Also: Java: Hashmap Working

In HashMap, store values in form array of buckets of the object where these array having hashcode value while objects having objects that match with the same hashcode. For example, the Hash Code is like a sequence of boxes for storage where different kinds of stuff can be stored in different boxes. It is more efficient if you organize stuff to a different place instead of the same garage. So it’s a good practice to keep kinds of stuff on related boxes i.e equally distribute the hashCode value.

The solution is to add hashCode() method to the Car class. Here we are getting hash value based on the size of color length as implemented below.

import java.util.HashMap;
import java.util.Map;

public class Car {
	private String color;

	public Car(String color) {
		this.color = color;
	}

	public boolean equals(Object obj) {
		if (!(obj instanceof Car))
			return false;
		if (obj == this)
			return true;
		return this.color.equals(((Car) obj).color);
	}

	public int hashCode(){
		return this.color.length();
}
	public static void main(String[] args) {
		Car a1 = new Car("green");//hashcode
		Car a2 = new Car("red");

		// HashMap stores car type and its quantity
		Map m = new HashMap();
		m.put(a1, 10);
		m.put(a2, 20);
		//hashcode different from previous green object consider different object
		System.out.println(m.get(new Car("green")));
	}

}

Output

10

Java: Hashmap Working


What is Hashing?

Hashing is technique of converting an object into an integer value. For example hashcode() method always return int value. We can also override hashcode() method and implement own logic to get hashcode value.

Note : The integer value helps in indexing and faster searches.

What is HashMap

HashMap is a one type of collection in Java collection framework to store values in key and value pair. HashMap uses hashing technique for storing values. HashMap uses internal data structure as array and LinkedList for storing key and values. HashMap contains an array of nodes, and node presented by a class with respect to key.

See Also : Java: HashMap Class Methods and Examples

Contract between equals() and hashcode() method

Before discussing internal working of HashMap, need to understand hashCode() and equals() method contract in detail.

  • equals(): it’s Object class method to check the equality of two objects by comparing key, whether they are equal or not. It can be overridden.
  • hashCode(): it’s also object class methods which return memory reference of object in integer form. This value received from the hashcode() method is used as the bucket number or address of element inside Map. Hashcode value of null Key is 0.

If you override the equals() method, then it is mandatory to override the hashCod() method.

See Also: Java : java.lang.Object Class & Methods

Buckets: is an Array of the node, where each node has a data structure like a LinkedList. More than one node can use same bucket and may be different in capacity.

Working of HashMap

Insert Key, Value pair in HashMap

We use put() method to insert the Key and Value pair in the HashMap. The default capacity of HashMap is 16 (0 to 15).

Example: In the following example, we want to insert six (Key, Value) pair in the HashMap.

HashMap map = new HashMap();
map.put("Ankur", 35);
map.put("Saurabh", 36);
map.put("Gaurav", 32);
map.put("Raghav", 29);
map.put("Rajendra", 40);
map.put("Shailesh", 33);

When we call the put() method, then it calculates the hash code of the Key i.e “Ankur” hashcode is 63412443. Now to store the Key and value pair in memory, we have to calculate the index based on below formulae.

HashMap Representataion.jpg

Calculating Index Formulae:


Index = hashcode(Key) & (n-1)  
Where n is the size of the array.

Hence the index value for Ankur and others are as below:
Calculate Index for “Ankur”
Index = 63412443& (16-1) = 11
Calculate Index for “Saurabh”
Index = -758033668& (16-1) = 12
Calculate Index for “Gaurav”
Index = 2125849484& (16-1) = 12
Calculate Index for “Raghav”
Index = -1854623835& (16-1) = 5
Calculate Index for “Rajendra”
Index = 201412911& (16-1) = 15
Calculate Index for “Shailesh”
Index = -687212437& (16-1) = 11

The key “Ankur” calculated index value is 11. This key and value pair store in one of the node of HashMap.

Hash Collision

Hash Collisions occured when two or more keys are calculating index as same value.

From above calculated index value, keys “Ankur and “Shailesh” both index value is 11 having hash collision. Similarly for “Saurabh” and “Gaurav” having index value 12. In this case, equals() method compare both Keys are equal or not. If Keys are equal, replace the value with the current value. Otherwise, linked this node object (key and value pair) to the existing node object through the LinkedList.

Similarly, we will store the other keys with respect to below index positions.

HashMap get() method to retrieve values

HashMap get(Key) method is used to retrieve value by Key. This method calculate index position based on key hashcode value and capacity of hashmap and fetch result. If no matching key find out will return result as value null.

Suppose we have to fetch the Key “Ankur.” The following method will be called.


map.get(new Key("Ankur"));

It generates the hash code as 63412443. Now calculate the index value of 63412443 by using index formula. The index value will be 11. get() method search for the index value 11. It compares the given key value sequentially in bucket with respect to index position 11. If any equal key find out in bucket will return value object with respect to that key otherwise finally return null if not no match find out.

Let’s fetch another Key “Raghav.” The hash code of the Key “Raghav” is -1854623835. The calculated index value of -1854623835 is 5. Go to index 5 of the array and compare the first element’s Key with the given Key “Raghav”. It return the value object for match key.

Java : java.lang.Object Class & Methods


java.lang.Object  is the root of the class hierarchy. Every class has Object as a superclass. All objects, including arrays, implement the methods of this class. It’s also called as Object Class.

Methods of Object Class

Below are methods of Object Class for different purpose  as below:

  1. protected Object clone() : Creates and return copy of this object.
  2. boolean equals(Object obj) : Indicate weather other object is equal or not.
  3. protected void finalize() : To make object finalize for garbage collection.
  4. Class getClass() : Returns the runtime class of this Object.
  5. int hashCode() : Returns a hash code value of Object.
  6. void notify() : Wakes up a single thread that is waiting on this object’s monitor. It works in multithread env with tow thread only.
  7. void notifyAll() : Wakes up all threads that are waiting on this object’s monitor. if more than one thread running.
  8. String toString() : Returns string representation of object.
  9. void wait() : Causes the current thread to wait until another thread invokes the notify() method or the notifyAll() method for this object.
  10. void wait(long timeout) : Causes the current thread to wait until another thread invokes the notify() method or the notifyAll() method for this object. or specified time has elapsed.
  11. void wait(long timeout, int nanos) : Causes the current thread to wait until another thread invokes the notify() method or the notifyAll() method for this object. or some other thread interrupts the current thread, or a certain amount of real time has elapsed.

In this below examples you can see how to override and utilize these methods in different ways.

Example of clone() method

Object class clone() method, create and return copy of a object(). For implementing a clone method class have implements Cloneable interface which is a Marker Interface. There are two ways of cloning of object Shallow Cloning and Deep Cloning. For more detail follow below link.

Java : Shallow and Deep Object Cloning

Eample of finalize() method

Garbage collector calls Object class finalize() method before clean object. We can override this method for code clean-up activity like closing files, database connection and socket. Follow below link to know more about finalize() method example and uses:

Java : Garbage Collection finalize() method example and uses

Example of hashCode(), equals() and toString() method

Override toString() method to print object values. Same way we can override hash() code and equals() method also. hashcode and equals() method have contract as:

“If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result. If you only override equals() and not hashCode() your class violates this contract

For example of toString(), hashcode() and equals() follow below link:

Java : How to remove duplicate objects from list?

Example of getClass() method

The getClass() method returns the run time class of an object.  As in below examples returning class name of objects.

import java.util.Calendar;

public class GetClassExample {

	public static void main(String[] args) {
		GetClassExample test=new GetClassExample();

		System.out.println("Class Name :"+test.getClass().getName());

		Calendar calendar=Calendar.getInstance();
		System.out.println("Calendar Class Name :"+calendar.getClass().getName());

		Integer integer=new Integer(10);
		System.out.println("Integer Class Name :"+integer.getClass().getName());

	}
}

Output


Class Name :com.Object.GetClassExample
Calendar Class Name :java.util.GregorianCalendar
Integer Class Name :java.lang.Integer

Example of wait(), notify() and notifyAll() method

Below is example of restaurant using method wait(), notify() and notifyAll(). Where Two waiter thread are running and waiting for  order message when they got order notify will pass the order message and based on available waiter will process order.

public class Order {
    private String msg;
    public Order(String msg){
        this.msg=msg;
    }
    public String getMsg() {
        return msg;
    }
    public void setMsg(String str) {
        this.msg=str;
    }
}

Waiter class that will wait for other threads to invoke notify methods to complete it’s processing. Notice that Waiter thread is owning monitor on Order object using synchronized block.

public class Waiter implements Runnable{
    private Order msg;
    public Waiter(Order msg){
        this.msg=msg;
    }
    @Override
    public void run() {
        String name = Thread.currentThread().getName();
        synchronized (msg) {
            try{
                System.out.println(name+" waiting to get notification at time:"+System.currentTimeMillis());
                msg.wait();
            }catch(InterruptedException e){
                e.printStackTrace();
            }
            System.out.println(name+" waiter thread got notification at time:"+System.currentTimeMillis());
            //process the order now
            System.out.println(name+" processed: "+msg.getMsg());
        }
    }
}

Here notification thread will call notify() method on order message so that available waiter will pick the order.Notice that synchronized block is used to own the monitor of Order object.

public class Notification implements Runnable {
    private Order msg;
    public Notification(Order msg) {
        this.msg = msg;
    }
    @Override
    public void run() {
        String name = Thread.currentThread().getName();
        System.out.println(name+" started");
        try {
            Thread.sleep(1000);
            synchronized (msg) {
                msg.setMsg(name+" Notification work done");
                msg.notify();
                //use notify all when lots of thread are running
                // msg.notifyAll();
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

Below test class having multiple threads of Waiter and notification to execute order.

public class WaitNotifyExample {
	public static void main(String[] args) {
		Order order= new Order("My Order");
	        Waiter waiter1 = new Waiter(order);
	        new Thread(waiter1,"waiter 1").start();

	        Waiter waiter2 = new Waiter(order);
	        new Thread(waiter2, "waiter 2").start();

	        Notification notification = new Notification(msg);
	        new Thread(notification, "notification").start();
	        System.out.println("All the threads are started");
	}
}

When we will execute the above program, we will see below output but program will not complete because there are two waiter threads waiting for Order object and notify() method has wake up only one of them, the other waiter thread is still waiting to get notified.

Output


waiter 2 waiting to get notification at time:1552127934935
waiter 1 waiting to get notification at time:1552127934935
notification started
All the threads are started
waiter 2 waiter thread got notification at time:1552127935946
waiter 2 processed: notification Notification work done

or


waiter 1 waiting to get notification at time:1552127972873
All the threads are started
notification started
waiter 2 waiting to get notification at time:1552127972873
waiter 1 waiter thread got notification at time:1552127973876
waiter 1 processed: notification Notification work done

Conclusion

Here you learn about the Object class and it’s methods. How to use these objects class methods with example and where can we use that.

References

https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html

Java : How to remove duplicate objects from List


In this below example list having duplicate object of AccountTransaction which need to remove from list. Here I am using HashSet because it always keep unique records. Now question comes how to decide uniqueness of object. As you know contract between hashcode() and equals() method deciding uniqueness and equality of object.

Here used Comparable interface to sort values based on transaction date.

hashcode() and equals() contract :

“If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result. If you only override equals() and not hashCode() your class violates this contract.”

Example


import java.math.BigDecimal;
import java.util.Date;

public class AccountTransaction implements Comparable{
	private Date date;
	String transactionType;
	private String reference;
	private BigDecimal amount;

	public AccountTransaction(Date date, String transactionType, String reference, BigDecimal amount) {
		super();
		this.date = date;
		this.transactionType = transactionType;
		this.reference = reference;
		this.amount = amount;
	}
//Overriding toString() method to print object
	@Override
	public String toString() {
		return "AccountTransactions [date=" + date + ", transactionType=" + transactionType + ", reference=" + reference
				+ ", amount=" + amount + "]";
	}
//Overriding hashcode() and equals() method to check equality and uniqueness
//of objects
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((amount == null) ? 0 : amount.hashCode());
		result = prime * result + ((date == null) ? 0 : date.hashCode());
		result = prime * result + ((reference == null) ? 0 : reference.hashCode());
		result = prime * result + ((transactionType == null) ? 0 : transactionType.hashCode());
		return result;
	}
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		AccountTransaction other = (AccountTransaction) obj;
		if (amount == null) {
			if (other.amount != null)
				return false;
		} else if (!amount.equals(other.amount))
			return false;
		if (date == null) {
			if (other.date != null)
				return false;
		} else if (!date.equals(other.date))
			return false;
		if (reference == null) {
			if (other.reference != null)
				return false;
		} else if (!reference.equals(other.reference))
			return false;
		if (transactionType == null) {
			if (other.transactionType != null)
				return false;
		} else if (!transactionType.equals(other.transactionType))
			return false;
		return true;
	}
	//Sort object by date
	@Override
	public int compareTo(AccountTransaction o) {

		return this.getDate().compareTo(o.getDate());
	}

	//use getter and setter of properties
}

Here is the class having sample data which is having duplicate objects in list. calling removeDuplicate() method which is converting list to hashSet() to remove duplicate and then again converting to list then sorting by date.


import java.math.BigDecimal;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Date;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class RemoveDuplicateObjects {

	public static void main(String[] args) {
		List transactionList = new ArrayList();
		try {
			transactionList.add(new AccountTransaction(getDate("2018-10-15 10:50 AM"), "Account Debits", "Pizza hut",new BigDecimal("0.56")));
			transactionList.add(new AccountTransaction(getDate("2018-10-15 10:52 AM"), "Account Debits", "Pizza hut",new BigDecimal("0.56")));
			transactionList.add(new AccountTransaction(getDate("2018-10-15 10:48 AM"), "Account Debits", "Burger king",new BigDecimal("0.56")));
			transactionList.add(new AccountTransaction(getDate("2018-10-15 10:38 AM"), "Account Debits", "Burger king",new BigDecimal("1.56")));
			transactionList.add(new AccountTransaction(getDate("2018-10-15 10:55 AM"), "Account Debits", "Papa Johns",new BigDecimal("2.56")));
			transactionList.add(new AccountTransaction(getDate("2018-10-15 10:35 AM"), "Account Debits", "Pizza hut",new BigDecimal("1.56")));
			transactionList.add(new AccountTransaction(getDate("2018-10-15 10:35 AM"), "Account Credits", "Chase Bank",new BigDecimal("200")));
			//Duplicate record
			transactionList.add(new AccountTransaction(getDate("2018-10-15 10:52 AM"), "Account Debits", "Pizza hut",new BigDecimal("0.56")));
			transactionList.add(new AccountTransaction(getDate("2018-10-15 10:38 AM"), "Account Debits", "Burger king",new BigDecimal("1.56")));
			transactionList.add(new AccountTransaction(getDate("2018-10-15 10:35 AM"), "Account Credits", "Chase Bank",new BigDecimal("200")));

		   System.out.println("Transactions before removing duplicate=============");
		   for(AccountTransaction transaction:transactionList)
		   System.out.println(transaction);
		   System.out.println("Transactions after removing duplicate=============");
		   transactionList=removeDuplicate(transactionList);
		   for(AccountTransaction transaction:transactionList)
			   System.out.println(transaction);

		} catch (Exception ex) {
			ex.printStackTrace();
		}
	}

	private static List removeDuplicate(List transactionList)
	{
		//Convert List to Set
		Set transactionSet=new HashSet(transactionList);
		//Convert Set to Array List
		transactionList=new ArrayList(transactionSet);

		//Sort object by transaction date and time
		Collections.sort(transactionList);

		return transactionList;
	}

	private static Date getDate(String dateStr) throws ParseException {
		return new SimpleDateFormat("yyyy-MM-dd HH:mm a").parse(dateStr);
	}
}

Output


Transactions before removing duplicate=============
AccountTransactions [date=Mon Oct 15 10:50:00 IST 2018, transactionType=Account Debits, reference=Pizza hut, amount=0.56]
AccountTransactions [date=Mon Oct 15 10:52:00 IST 2018, transactionType=Account Debits, reference=Pizza hut, amount=0.56]
AccountTransactions [date=Mon Oct 15 10:48:00 IST 2018, transactionType=Account Debits, reference=Burger king, amount=0.56]
AccountTransactions [date=Mon Oct 15 10:38:00 IST 2018, transactionType=Account Debits, reference=Burger king, amount=1.56]
AccountTransactions [date=Mon Oct 15 10:55:00 IST 2018, transactionType=Account Debits, reference=Papa Johns, amount=2.56]
AccountTransactions [date=Mon Oct 15 10:35:00 IST 2018, transactionType=Account Debits, reference=Pizza hut, amount=1.56]
AccountTransactions [date=Mon Oct 15 10:35:00 IST 2018, transactionType=Account Credits, reference=Chase Bank, amount=200]
AccountTransactions [date=Mon Oct 15 10:52:00 IST 2018, transactionType=Account Debits, reference=Pizza hut, amount=0.56]
AccountTransactions [date=Mon Oct 15 10:38:00 IST 2018, transactionType=Account Debits, reference=Burger king, amount=1.56]
AccountTransactions [date=Mon Oct 15 10:35:00 IST 2018, transactionType=Account Credits, reference=Chase Bank, amount=200]
Transactions after removing duplicate=============
AccountTransactions [date=Mon Oct 15 10:35:00 IST 2018, transactionType=Account Credits, reference=Chase Bank, amount=200]
AccountTransactions [date=Mon Oct 15 10:35:00 IST 2018, transactionType=Account Debits, reference=Pizza hut, amount=1.56]
AccountTransactions [date=Mon Oct 15 10:38:00 IST 2018, transactionType=Account Debits, reference=Burger king, amount=1.56]
AccountTransactions [date=Mon Oct 15 10:48:00 IST 2018, transactionType=Account Debits, reference=Burger king, amount=0.56]
AccountTransactions [date=Mon Oct 15 10:50:00 IST 2018, transactionType=Account Debits, reference=Pizza hut, amount=0.56]
AccountTransactions [date=Mon Oct 15 10:52:00 IST 2018, transactionType=Account Debits, reference=Pizza hut, amount=0.56]
AccountTransactions [date=Mon Oct 15 10:55:00 IST 2018, transactionType=Account Debits, reference=Papa Johns, amount=2.56]

See Also: