Wednesday 6 January 2016

Difference between HashMap and IdentityHashMap

In my previous post, I explained how IdentityHashMap works in Java. In this post, I am going to explain the key differences between HashMap and IdentityHashMap.


1. HashMap uses equals() method to compare keys, where as IdentityHashMap uses == operator to compare keys.
public class Employee {
    private int id;
    private String firstName;
    private String lastName;

    public Employee(int id, String firstName, String lastName) {
        super();
        this.id = id;
        this.firstName = firstName;
        this.lastName = lastName;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getFirstName() {
        return firstName;
    }

    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }

    public String getLastName() {
        return lastName;
    }

    public void setLastName(String lastName) {
        this.lastName = lastName;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result
                + ((firstName == null) ? 0 : firstName.hashCode());
        result = prime * result + id;
        result = prime * result
                + ((lastName == null) ? 0 : lastName.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;
        Employee other = (Employee) obj;
        if (firstName == null) {
            if (other.firstName != null)
                return false;
        } else if (!firstName.equals(other.firstName))
            return false;
        if (id != other.id)
            return false;
        if (lastName == null) {
            if (other.lastName != null)
                return false;
        } else if (!lastName.equals(other.lastName))
            return false;
        return true;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("Employee [id=").append(id).append(", firstName=")
                .append(firstName).append(", lastName=").append(lastName)
                .append("]");
        return builder.toString();
    }

}


import java.util.HashMap;
import java.util.IdentityHashMap;
import java.util.Map;
import java.util.Set;

public class EmployeeTest {
    private static void displayMap(Map<Employee, String> map) {
        Set<Employee> keys = map.keySet();

        for (Employee emp : keys) {
            System.out.println(emp);
        }
    }

    public static void main(String args[]) {
        Employee emp1 = new Employee(1, "Hari Krishna", "Gurram");
        Employee emp2 = new Employee(1, "Hari Krishna", "Gurram");
        Employee emp3 = new Employee(1, "Hari Krishna", "Gurram");
        Employee emp4 = new Employee(1, "Hari Krishna", "Gurram");
        Employee emp5 = new Employee(1, "Hari Krishna", "Gurram");

        Map<Employee, String> hashMap = new HashMap<>();
        Map<Employee, String> identityHashMap = new IdentityHashMap<>();

        hashMap.put(emp1, "Software Engineer");
        hashMap.put(emp2, "Software Engineer");
        hashMap.put(emp3, "Software Engineer");
        hashMap.put(emp4, "Software Engineer");
        hashMap.put(emp5, "Software Engineer");

        identityHashMap.put(emp1, "Software Engineer");
        identityHashMap.put(emp2, "Software Engineer");
        identityHashMap.put(emp3, "Software Engineer");
        identityHashMap.put(emp4, "Software Engineer");
        identityHashMap.put(emp5, "Software Engineer");

        System.out.println("Data in HashMap");
        System.out.println("**************************");
        displayMap(hashMap);

        System.out.println("Data in IdentityHashMap");
        System.out.println("**************************");
        displayMap(identityHashMap);
    }
}


Output

Data in HashMap
**************************
Employee [id=1, firstName=Hari Krishna, lastName=Gurram]
Data in IdentityHashMap
**************************
Employee [id=1, firstName=Hari Krishna, lastName=Gurram]
Employee [id=1, firstName=Hari Krishna, lastName=Gurram]
Employee [id=1, firstName=Hari Krishna, lastName=Gurram]
Employee [id=1, firstName=Hari Krishna, lastName=Gurram]
Employee [id=1, firstName=Hari Krishna, lastName=Gurram]


Please go through the program once, I created 5 Employee instances emp1, emp2, emp3, emp4 and emp5. All the Employee instances have same properties (id=1, firstName=Hari Krishna, lastName=Gurram).

Since HashMap stores the <Key, Value> pair based on equals method of key. Equlas method for Employee instances emp1, emp2, emp3, emp4, emp5 is same for all. HashMap stores only one Employee instance. In case of IdentityHashMap, all emp1, emp2, emp3, emp4 and emp5 are five different objects, reference check for emp1==emp2 is false, so IdentityHashMap store all five employees.

public class EmployeeTest {

    public static void main(String args[]) {
        Employee emp1 = new Employee(1, "Hari Krishna", "Gurram");
        Employee emp2 = new Employee(1, "Hari Krishna", "Gurram");
        Employee emp3 = new Employee(1, "Hari Krishna", "Gurram");
        Employee emp4 = new Employee(1, "Hari Krishna", "Gurram");
        Employee emp5 = new Employee(1, "Hari Krishna", "Gurram");

        System.out.println("emp1.equals(emp2) : " + emp1.equals(emp2));
        System.out.println("emp1.equals(emp3) : " + emp1.equals(emp3));
        System.out.println("emp1.equals(emp4) : " + emp1.equals(emp4));
        System.out.println("emp1.equals(emp5) : " + emp1.equals(emp5));

        System.out.println("emp1==emp2 : " + (emp1 == emp2));
        System.out.println("emp1==emp3 : " + (emp1 == emp3));
        System.out.println("emp1==emp4 : " + (emp1 == emp4));
        System.out.println("emp1==emp5 : " + (emp1 == emp5));
    }
}


Output

emp1.equals(emp2) : true
emp1.equals(emp3) : true
emp1.equals(emp4) : true
emp1.equals(emp5) : true
emp1==emp2 : false
emp1==emp3 : false
emp1==emp4 : false
emp1==emp5 : false


2. IdentityHashMap intentionally violates the general contract which mandates the use of the equals method when comparing objects, where as HashMap follows the equals method.

3. To find the bucket location IdentityHashMap uses System.identityHashCode() method, where as HashMap uses hashCode of the key.

Following is the hashCode calculation in HashMap
static final int hash(Object key) {
         int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Following is the hashCode calculation in IdentityHashMap
private static int hash(Object x, int length) {
         int h = System.identityHashCode(x);
    // Multiply by -127, and left-shift to use least bit as part of hash
    return ((h << 1) - (h << 8)) & (length - 1);
}

4. IdentityHashMap uses Linear probing technique to resolve collisions, where as HashMap uses chaining to resolve collisions.

5. As per javadoc, For many JRE implementations and operation mixes, IdentityHashMap class will yield better performance than HashMap (which uses chaining rather than linear-probing).

6. Since IdentityHashMap doesn’t rely on hashCode and equals methods, key don’t need to be immutable.

7. IdentityHashMap class provides tunuing parameter 'expectedMaxSize', this parameter specifies the expected maximum number of key-value mappings that the map is expected to hold. Putting more than the expected number of key-value mappings into the map may cause the internal data structure to grow, which may be somewhat time-consuming.


You may like

                                                 Home

No comments:

Post a Comment