,

Friday, 26 December 2014

Internal Working of HashMap (Immutable keys)

Immutable Key
Why Keys should be immutable in HashMap?
We have an Employee class and we are inserting the object of this class as key in HashMap.

Demo 1:
package com.immt;
import java.util.HashMap;
/**
 *
 * @author Ganesh.Rashinker
 *
 */
class Employee {
private int id;
private String name;
public Employee(int id, String name) {
super();
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "Employee [id=" + id + ", name=" + name + "]";
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + id;
result = prime * result + ((name == null) ? 0 : name.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 (id != other.id)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
}
public class MainClass {

public static void main(String[] args) {
Employee emp1 = new Employee(1, "Robert");
HashMap<Employee, String> map = new HashMap<Employee, String>();
map.put(emp1, "First Employee");
System.out.println("map data is: "+ map);
System.out.println("map.containsKey displays: " + map.containsKey(emp1));

}
}

Output:
map data is: {Employee [id=1, name=Robert]=First Employee}
map.containsKey displays: true



On the basis of Employee objects hashcode , hash function and indexFor ,  the data goes in 9th bucket(table[9]).Below is the analysis of same. See the analysis of the same.

Demo 2:
package com.immt;
import java.util.HashMap;
/**
 *
 * @author Ganesh.Rashinker
 *
 */
class Employee {
private int id;
private String name;
public Employee(int id, String name) {
super();
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "Employee [id=" + id + ", name=" + name + "]";
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + id;
result = prime * result + ((name == null) ? 0 : name.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 (id != other.id)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
}
public class MainClass2 {
// hash function as in HashMap
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// indexFor function as in HashMap
static int indexFor(int h, int length) {
return h & (length - 1);
}
public static void main(String[] args) {
Employee emp1 = new Employee(1, "Robert");
HashMap<Employee, String> map = new HashMap<Employee, String>();
int hashCode = emp1.hashCode();
System.out.println("hashcode value of emp1 object: " + hashCode);
int hash = hash(hashCode);
System.out.println("hash value of emp1 object: " + hash);
int bucket = indexFor(hash, 16);
System.out.println("bucket number to insert emp1 object: " + bucket);
map.put(emp1, "First Employee");
System.out.println("map data is: " + map);
System.out.println("map.containsKey displays: " + map.containsKey(emp1));
}
}

Output:
hashcode value of emp1 object: -1841844862
hash value of emp1 object: -1707535703
bucket number to insert emp1 object: 9
map data is: {Employee [id=1, name=Robert]=First Employee}
map.containsKey displays: true

The put method internally uses the hashcode of the object and calculates the hash and indexFor to find the bucket number.



It has inserted in bucket 9. When you use containsKey function , it uses the hashing functionality to find the bucket number.


Now as we have not changed the state of the object , the calulation of hashcode , hash and indexFor will return 9 and it will search in 9th bucket only and will display true.
Now let us see what exactly happens if we change the state of emp1 object.

Demo 3:
package com.immt;
import java.util.HashMap;
/**
 *
 * @author Ganesh.Rashinker
 *
 */
class Employee {
private int id;
private String name;
public Employee(int id, String name) {
super();
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "Employee [id=" + id + ", name=" + name + "]";
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + id;
result = prime * result + ((name == null) ? 0 : name.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 (id != other.id)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
}
public class MainClass3 {
// hash function as in HashMap
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// indexFor function as in HashMap
static int indexFor(int h, int length) {
return h & (length - 1);
}
public static void main(String[] args) {
Employee emp1 = new Employee(1, "Robert");
HashMap<Employee, String> map = new HashMap<Employee, String>();
map.put(emp1, "First Employee");
System.out.println("map data is: " + map);
System.out.println("map.containsKey displays: " + map.containsKey(emp1));
emp1.setName("John");
System.out.println("map data is: " + map);
System.out.println("map.containsKey displays: " + map.containsKey(emp1));
}
}

Output:
map data is: {Employee [id=1, name=Robert]=First Employee}
map.containsKey displays: true
map data is: {Employee [id=1, name=John]=First Employee}
map.containsKey displays: false

We have changed the state of emp1 object by changing the name from Robert to John. Let us analyse , what is happening when we change the state.

Demo 4:(addition in main function only)

public static void main(String[] args) {
Employee emp1 = new Employee(1, "Robert");
HashMap<Employee, String> map = new HashMap<Employee, String>();
map.put(emp1, "First Employee");
System.out.println("map data is: " + map);
System.out.println("map.containsKey displays: " + map.containsKey(emp1));
emp1.setName("John");
System.out.println("map data is: " + map);
System.out.println("map.containsKey displays: " + map.containsKey(emp1));
//checking the below for containsKey method
int hashCode = emp1.hashCode();
System.out.println("hashcode value of emp1 object: " + hashCode);
int hash = hash(hashCode);
System.out.println("hash value of emp1 object: " + hash);
int bucket = indexFor(hash, 16);
System.out.println("bucket number to search emp1 object: " + bucket);
}

Output:
map data is: {Employee [id=1, name=Robert]=First Employee}
map.containsKey displays: true
map data is: {Employee [id=1, name=John]=First Employee}
map.containsKey displays: false
hashcode value of emp1 object: 2315531
hash value of emp1 object: 2172129
bucket number to search emp1 object: 1

The containsKey function uses hashcode , hash and indexFor function to find the bucket number where it should search for the object. The containsKey get a different hashcode , hash and indexFor values as the sate of the object is changed. It will search in a different bucket this time. So when we inserted the object the indexFor calculation was based on one state and after we change the state of the object , the hashcode changes and thus might result in searching in a different bucket and result false. Thus it is suggested that the Class whose object is inserted as key should be immutable , which means you should not be able to change the state.

To make a class Immutable in a general way  , make the class as final and member variable as private and final and remove the setter methods associated to the member variables.

Demo 4:
package com.immt;
import java.util.HashMap;
/**
 *
 * @author Ganesh.Rashinker
 *
 */
final class Employee {
private final int id;
private final String name;
public Employee(int id, String name) {
super();
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
/*public void setId(int id) {
this.id = id;
}*/
public String getName() {
return name;
}
/*public void setName(String name) {
this.name = name;
}*/
@Override
public String toString() {
return "Employee [id=" + id + ", name=" + name + "]";
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + id;
result = prime * result + ((name == null) ? 0 : name.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 (id != other.id)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
}
public class MainClass4 {
public static void main(String[] args) {
Employee emp1 = new Employee(1, "Robert");
HashMap<Employee, String> map = new HashMap<Employee, String>();
map.put(emp1, "First Employee");
System.out.println("map data is: " + map);
System.out.println("map.containsKey displays: " + map.containsKey(emp1));
//emp1.setName("John"); //not allowed as setters are not available in immutable class //System.out.println("map data is: " + map);
//System.out.println("map.containsKey displays: " + map.containsKey(emp1));
}
}

Output:
map data is: {Employee [id=1, name=Robert]=First Employee}
map.containsKey displays: true

Conclusion : 
The Class whose object is inserted as a key should be made immutable , which means that you should not be able to change the state of the object.







3 comments:

  1. Hi Ganesh.. Is there any possibility that the emp object will be searched in the same bucket even after modifying the state of emp object with some different value?

    ReplyDelete
  2. Hi , For two different hashcode , the bucket number(index of Entry [] table ) can be the same.As the indexFor method will try to get the index between 0 to 15 for the HashMap having default 16 buckets.
    /**
    * Returns index for hash code h.
    */
    static int indexFor(int h, int length) {
    return h & (length-1);
    }
    It also depends on the way you implement hashcode method of Employee class.

    ReplyDelete