Hashing in HashMap:
HashMap stores key value pair.When you create a HashMap , it creates Entry class Array( table [] ) of 16 elements.
Note: We will have more of practical approach.
Video
Demo1:
Output:
{}
It creates a table array(Entry []table) and each array element is known as bucket. So the default numbers of bucket is 16 table[0] to table[15]. When you insert null as key it will be inserted at index 0 that is table[0].
Now we will insert the Employee class object in HashMap as Key and String as value.
Demo2:
Output:
{Employee [id=2, name=Johny]=second Employee, Employee [id=3, name=Stella]=third Employee, Employee
[id=1, name=Robert]=first Employee}
When you add in HashMap Bucket , entry element is added in bucket. Entry is a singly linked list element. So we can say HashMap is Array of Singly linked list.HashMap is not ordered. From the above it is clear that the output is not in the sequence in which they were added in HashMap.So let us try to understand on what basis does HashMap inserts data.Bucket number(table[?]) is decided on the basis of key and we are inserting Employee object as Key.To find the bucket number it uses hashcode of the object and performs hash function and indexfor function. Hashcode of an object is calculated on the basis of the overriden hashcode function in Employee class.
Demo3:
package com.hashdemo;
import java.util.HashMap;
/**
*
* @author Ganesh.Rashinker
*
*/
public class HashingDemo3 {
//hash as in HashMap
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
//indexFor as in HashMap
static int indexFor(int h, int length) {
return h & (length - 1);
}
public static void main(String[] args) {
HashMap<Employee, String> map = new HashMap<Employee, String>();
Employee emp1 = new Employee(1, "Robert");
int emp1hcode = emp1.hashCode();
System.out.println("hashcode of emp1: " + emp1hcode);
int hash = hash(emp1hcode);
System.out.println("hash value of emp1: " + hash);
int index = indexFor(hash, 16);
System.out.println("bucket number for emp1: " + index);
System.out.println("+++++++++++++++++++++++++++++++++++");
Employee emp2 = new Employee(2, "Johny");
int emp2hcode = emp2.hashCode();
System.out.println("hashcode of emp2: " + emp2hcode);
int hash2 = hash(emp2hcode);
System.out.println("hash value of emp2: " + hash2);
int index2 = indexFor(hash2, 16);
System.out.println("bucket number for emp2: " + index2);
System.out.println("+++++++++++++++++++++++++++++++++++");
Employee emp3 = new Employee(3, "Stella");
int emp3hcode = emp3.hashCode();
System.out.println("hashcode of emp3: " + emp3hcode);
int hash3 = hash(emp3hcode);
System.out.println("hash value of emp3: " + hash3);
int index3 = indexFor(hash3, 16);
System.out.println("bucket number for emp3: " + index3);
System.out.println("+++++++++++++++++++++++++++++++++++");
map.put(emp1, "first Employee");
map.put(emp2, "second Employee");
map.put(emp3, "third Employee");
System.out.println(map);
}
}
Output:
hashcode of emp1: -1841844862
hash value of emp1: -1707535703
bucket number for emp1: 9
+++++++++++++++++++++++++++++++++++
hashcode of emp2: 71751853
hash value of emp2: 67795061
bucket number for emp2: 5
+++++++++++++++++++++++++++++++++++
hashcode of emp3: -1808502149
hash value of emp3: -1672048248
bucket number for emp3: 8
+++++++++++++++++++++++++++++++++++
{Employee [id=2, name=Johny]=second Employee, Employee [id=3, name=Stella]=third Employee, Employee
[id=1, name=Robert]=first Employee}
On the basis of above analysis , the bucket number is decided using hashcode , hash and indexFor
function.
Let us understand what is the benefit of hash function.We will take three hashcode which do not differ in lower bits. We will take 1 , 17 , 33 , 65
Demo4:
package com.hashdemo;
/**
*
* @author Ganesh.Rashinker
*
*/
public class HashingDemo4 {
// hash as in HashMap
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// indexFor as in HashMap
static int indexFor(int h, int length) {
return h & (length - 1);
}
public static void main(String[] args) {
int hashcode1 = 1;
int hashcode2 = 17;
int hashcode3 = 33;
int hashcode4 = 65;
System.out.println("+++++++++++++++++++++++++++++++++++++++++");
System.out.println("Binary value of hashcode1 " + Integer.toBinaryString(hashcode1));
System.out.println("Binary value of hashcode1 " + Integer.toBinaryString(hashcode2));
System.out.println("Binary value of hashcode1 " + Integer.toBinaryString(hashcode3));
System.out.println("Binary value of hashcode1 " + Integer.toBinaryString(hashcode4));
System.out.println("+++++++++++++++++++++++++++++++++++++++++");
System.out.println("Finding the bucket number on the basis of hashcode directly");
System.out.println("Bucket number for hashcode1: " + indexFor(hashcode1, 16));
System.out.println("Bucket number for hashcode2: " + indexFor(hashcode2, 16));
System.out.println("Bucket number for hashcode3: " + indexFor(hashcode3, 16));
System.out.println("Bucket number for hashcode4: " + indexFor(hashcode4, 16));
System.out.println("+++++++++++++++++++++++++++++++++++++++++");
System.out.println("Finding the hash value on the basis of hash function");
System.out.println("hash value for hashcode1: " + hash(hashcode1));
System.out.println("hash value for hashcode2: " + hash(hashcode2));
System.out.println("hash value for hashcode3: " + hash(hashcode3));
System.out.println("hash value for hashcode4: " + hash(hashcode4));
System.out.println("+++++++++++++++++++++++++++++++++++++++++");
System.out.println("Finding the bucket number on the basis of hash function");
System.out.println("Bucket number for hashcode1: " + indexFor(hash(hashcode1), 16));
System.out.println("Bucket number for hashcode2: " + indexFor(hash(hashcode2), 16));
System.out.println("Bucket number for hashcode3: " + indexFor(hash(hashcode3), 16));
System.out.println("Bucket number for hashcode4: " + indexFor(hash(hashcode4), 16));
System.out.println("+++++++++++++++++++++++++++++++++++++++++");
}
}
Output:
+++++++++++++++++++++++++++++++++++++++++
Binary value of hashcode1 1
Binary value of hashcode1 10001
Binary value of hashcode1 100001
Binary value of hashcode1 1000001
+++++++++++++++++++++++++++++++++++++++++
Finding the bucket number on the basis of hashcode directly
Bucket number for hashcode1: 1
Bucket number for hashcode2: 1
Bucket number for hashcode3: 1
Bucket number for hashcode4: 1
+++++++++++++++++++++++++++++++++++++++++
Finding the hash value on the basis of hash function
hash value for hashcode1: 1
hash value for hashcode2: 16
hash value for hashcode3: 35
hash value for hashcode4: 69
+++++++++++++++++++++++++++++++++++++++++
Finding the bucket number on the basis of hash function
Bucket number for hashcode1: 1
Bucket number for hashcode2: 0
Bucket number for hashcode3: 3
Bucket number for hashcode4: 5
+++++++++++++++++++++++++++++++++++++++++
When you do &(bitwise operator) operation of values 1 , 17 , 33 and 65 with 15(16-1 which is index-1) the lower four bits are only considered and hashcode1 , hashcode2 , hashcode3 , hashcode4 does not differ in lower bits and thus have 1 as the bucket number. When we apply hash function of these four hashcode it chages their value. The hash function is having right shift operator where it adds one more 1 at lower bits in our example and change the value.The benefit of hash function is to reduce the collisions by changing the values of hashcode using shift operator where it tries to perform 20 , 12 , 7 and 4 right shifts.
HashMap stores key value pair.When you create a HashMap , it creates Entry class Array( table [] ) of 16 elements.
Note: We will have more of practical approach.
Video
Demo1:
package com.a.b;
package com.hashdemo;
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 HashingDemo1 {
public static void main(String[] args) {
HashMap<Employee, String> map = new HashMap<Employee, String>();
System.out.println(map);
}
}
package com.hashdemo;
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 HashingDemo1 {
public static void main(String[] args) {
HashMap<Employee, String> map = new HashMap<Employee, String>();
System.out.println(map);
}
}
Output:
{}
It creates a table array(Entry []table) and each array element is known as bucket. So the default numbers of bucket is 16 table[0] to table[15]. When you insert null as key it will be inserted at index 0 that is table[0].
Now we will insert the Employee class object in HashMap as Key and String as value.
Demo2:
package com.hashdemo;
import java.util.HashMap;
/**
*
* @author Ganesh.Rashinker
*
*/
public class HashingDemo2 {
public static void main(String[] args) {
HashMap<Employee, String> map = new HashMap<Employee, String>();
Employee emp1 = new Employee(1, "Robert");
Employee emp2 = new Employee(2, "Johny");
Employee emp3 = new Employee(3, "Stella");
map.put(emp1, "first Employee");
map.put(emp2, "second Employee");
map.put(emp3, "third Employee");
System.out.println(map);
}
}
import java.util.HashMap;
/**
*
* @author Ganesh.Rashinker
*
*/
public class HashingDemo2 {
public static void main(String[] args) {
HashMap<Employee, String> map = new HashMap<Employee, String>();
Employee emp1 = new Employee(1, "Robert");
Employee emp2 = new Employee(2, "Johny");
Employee emp3 = new Employee(3, "Stella");
map.put(emp1, "first Employee");
map.put(emp2, "second Employee");
map.put(emp3, "third Employee");
System.out.println(map);
}
}
Output:
{Employee [id=2, name=Johny]=second Employee, Employee [id=3, name=Stella]=third Employee, Employee
[id=1, name=Robert]=first Employee}
When you add in HashMap Bucket , entry element is added in bucket. Entry is a singly linked list element. So we can say HashMap is Array of Singly linked list.HashMap is not ordered. From the above it is clear that the output is not in the sequence in which they were added in HashMap.So let us try to understand on what basis does HashMap inserts data.Bucket number(table[?]) is decided on the basis of key and we are inserting Employee object as Key.To find the bucket number it uses hashcode of the object and performs hash function and indexfor function. Hashcode of an object is calculated on the basis of the overriden hashcode function in Employee class.
Demo3:
package com.hashdemo;
import java.util.HashMap;
/**
*
* @author Ganesh.Rashinker
*
*/
public class HashingDemo3 {
//hash as in HashMap
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
//indexFor as in HashMap
static int indexFor(int h, int length) {
return h & (length - 1);
}
public static void main(String[] args) {
HashMap<Employee, String> map = new HashMap<Employee, String>();
Employee emp1 = new Employee(1, "Robert");
int emp1hcode = emp1.hashCode();
System.out.println("hashcode of emp1: " + emp1hcode);
int hash = hash(emp1hcode);
System.out.println("hash value of emp1: " + hash);
int index = indexFor(hash, 16);
System.out.println("bucket number for emp1: " + index);
System.out.println("+++++++++++++++++++++++++++++++++++");
Employee emp2 = new Employee(2, "Johny");
int emp2hcode = emp2.hashCode();
System.out.println("hashcode of emp2: " + emp2hcode);
int hash2 = hash(emp2hcode);
System.out.println("hash value of emp2: " + hash2);
int index2 = indexFor(hash2, 16);
System.out.println("bucket number for emp2: " + index2);
System.out.println("+++++++++++++++++++++++++++++++++++");
Employee emp3 = new Employee(3, "Stella");
int emp3hcode = emp3.hashCode();
System.out.println("hashcode of emp3: " + emp3hcode);
int hash3 = hash(emp3hcode);
System.out.println("hash value of emp3: " + hash3);
int index3 = indexFor(hash3, 16);
System.out.println("bucket number for emp3: " + index3);
System.out.println("+++++++++++++++++++++++++++++++++++");
map.put(emp1, "first Employee");
map.put(emp2, "second Employee");
map.put(emp3, "third Employee");
System.out.println(map);
}
}
Output:
hashcode of emp1: -1841844862
hash value of emp1: -1707535703
bucket number for emp1: 9
+++++++++++++++++++++++++++++++++++
hashcode of emp2: 71751853
hash value of emp2: 67795061
bucket number for emp2: 5
+++++++++++++++++++++++++++++++++++
hashcode of emp3: -1808502149
hash value of emp3: -1672048248
bucket number for emp3: 8
+++++++++++++++++++++++++++++++++++
{Employee [id=2, name=Johny]=second Employee, Employee [id=3, name=Stella]=third Employee, Employee
[id=1, name=Robert]=first Employee}
On the basis of above analysis , the bucket number is decided using hashcode , hash and indexFor
function.
Let us understand what is the benefit of hash function.We will take three hashcode which do not differ in lower bits. We will take 1 , 17 , 33 , 65
Demo4:
package com.hashdemo;
/**
*
* @author Ganesh.Rashinker
*
*/
public class HashingDemo4 {
// hash as in HashMap
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// indexFor as in HashMap
static int indexFor(int h, int length) {
return h & (length - 1);
}
public static void main(String[] args) {
int hashcode1 = 1;
int hashcode2 = 17;
int hashcode3 = 33;
int hashcode4 = 65;
System.out.println("+++++++++++++++++++++++++++++++++++++++++");
System.out.println("Binary value of hashcode1 " + Integer.toBinaryString(hashcode1));
System.out.println("Binary value of hashcode1 " + Integer.toBinaryString(hashcode2));
System.out.println("Binary value of hashcode1 " + Integer.toBinaryString(hashcode3));
System.out.println("Binary value of hashcode1 " + Integer.toBinaryString(hashcode4));
System.out.println("+++++++++++++++++++++++++++++++++++++++++");
System.out.println("Finding the bucket number on the basis of hashcode directly");
System.out.println("Bucket number for hashcode1: " + indexFor(hashcode1, 16));
System.out.println("Bucket number for hashcode2: " + indexFor(hashcode2, 16));
System.out.println("Bucket number for hashcode3: " + indexFor(hashcode3, 16));
System.out.println("Bucket number for hashcode4: " + indexFor(hashcode4, 16));
System.out.println("+++++++++++++++++++++++++++++++++++++++++");
System.out.println("Finding the hash value on the basis of hash function");
System.out.println("hash value for hashcode1: " + hash(hashcode1));
System.out.println("hash value for hashcode2: " + hash(hashcode2));
System.out.println("hash value for hashcode3: " + hash(hashcode3));
System.out.println("hash value for hashcode4: " + hash(hashcode4));
System.out.println("+++++++++++++++++++++++++++++++++++++++++");
System.out.println("Finding the bucket number on the basis of hash function");
System.out.println("Bucket number for hashcode1: " + indexFor(hash(hashcode1), 16));
System.out.println("Bucket number for hashcode2: " + indexFor(hash(hashcode2), 16));
System.out.println("Bucket number for hashcode3: " + indexFor(hash(hashcode3), 16));
System.out.println("Bucket number for hashcode4: " + indexFor(hash(hashcode4), 16));
System.out.println("+++++++++++++++++++++++++++++++++++++++++");
}
}
Output:
+++++++++++++++++++++++++++++++++++++++++
Binary value of hashcode1 1
Binary value of hashcode1 10001
Binary value of hashcode1 100001
Binary value of hashcode1 1000001
+++++++++++++++++++++++++++++++++++++++++
Finding the bucket number on the basis of hashcode directly
Bucket number for hashcode1: 1
Bucket number for hashcode2: 1
Bucket number for hashcode3: 1
Bucket number for hashcode4: 1
+++++++++++++++++++++++++++++++++++++++++
Finding the hash value on the basis of hash function
hash value for hashcode1: 1
hash value for hashcode2: 16
hash value for hashcode3: 35
hash value for hashcode4: 69
+++++++++++++++++++++++++++++++++++++++++
Finding the bucket number on the basis of hash function
Bucket number for hashcode1: 1
Bucket number for hashcode2: 0
Bucket number for hashcode3: 3
Bucket number for hashcode4: 5
+++++++++++++++++++++++++++++++++++++++++
When you do &(bitwise operator) operation of values 1 , 17 , 33 and 65 with 15(16-1 which is index-1) the lower four bits are only considered and hashcode1 , hashcode2 , hashcode3 , hashcode4 does not differ in lower bits and thus have 1 as the bucket number. When we apply hash function of these four hashcode it chages their value. The hash function is having right shift operator where it adds one more 1 at lower bits in our example and change the value.The benefit of hash function is to reduce the collisions by changing the values of hashcode using shift operator where it tries to perform 20 , 12 , 7 and 4 right shifts.
No comments:
Post a Comment