CodesJava

Easy learning with example program codes

how to resolve collision in hashmap?


package com.codesjava;
 
import java.util.HashMap;
import java.util.Map;
 
public class Test {
	public static void main(String args[]){		
		Site site1 = new Site("codesjava", 1);
		Site site2 = new Site("java", 2);
		Site site3 = new Site("spring", 1);
 
		Map<Site, String> hashMap = new HashMap<>();
		hashMap.put(site1, "First site");
		hashMap.put(site2, "Second site");
		hashMap.put(site2, "Third site");
		hashMap.put(site3, "Fourth site");
		System.out.println("HashMap Elements: " + hashMap);
 
		System.out.println("site1: " + hashMap.get(site1));
		System.out.println("site2: " + hashMap.get(site2));
		System.out.println("site3: " + hashMap.get(site3));
	}
}
 
class Site{
	private String name;
	private int id;
 
	public Site(String name, int id) {
		super();
		this.name = name;
		this.id = id;
	}
 
	public String getName() {
		return name;
	}
 
	public void setName(String name) {
		this.name = name;
	}
 
	public int getId() {
		return id;
	}
 
	public void setId(int id) {
		this.id = id;
	}
 
	@Override
	public String toString() {
		return this.getId() + "-" + this.getName();
	}
 
	@Override
	public int hashCode() {
		//For simplicity we are returning id as hashCode value 
		return this.id;
	}
 
	@Override
	public boolean equals(final Object obj) {
		if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        final Site siteObject = (Site) obj;
        if(this.getName() == siteObject.getName() && 
        		this.getId() == siteObject.getId())
        	return true; 
        else
        	return false;
	}	
}

Output

HashMap Elements: {1-codesjava=First site, 1-spring=Fourth site, 2-java=Third site}
site1: First site
site2: Third site
site3: Fourth site

Index calculation in HashMap:
The hashCode() method returns a hash code value (an integer number) for the object which represents the memory address of the object. It may return a value from the range of integer. But if we create an array with this range, then it may result into OutOfMemoryException. Index value is generated to minimize the size of array. Index is calculated with following expression.

index = hashCode(key) & (n-1)

Where n represents the number of buckets.

Note: Normally, the bucket id is hash code / no of buckets

HashMap insertion in java (HashMap put method):
When an element is inserted into HashMap using put method, index value is calculated first. The object will be placed at index value if no other object is present at that index. Let us understand with above example. Let us look at the statement hashMap.put(site1, “First site”);. Element is inserted at index 1 with following details as there was no element at index 1.

HashMap Internal Working

Now, when second put operation is performed i.e. the statement hashMap.put(site2, “Second site”); executes. The index will be calculated again and it will return 2. As there is no element at index 2 so second element will be inserted at index 2.

HashMap Internal Working

Now, let us see what happens if we executes third insert statement i.e. hashMap.put(site2, “Third site”);. The index value will be calculated and it will again return 2. Collision occurs here in the HashMap as element is already exist at index 2. Collision is resolved based on key value. If key is also same then already existing element will be replaced by new one otherwise the next field of already existing element will now point to the new node element which results into a linked list. For third statement key will also be same and that’s why already existing element will be replaced.

HashMap Internal Working

Now, let us discuss the second case of HashMap collision in which key will be different. We are executing fourth statement here hashMap.put(site3, “Fourth site”);. The index value will be calculated and it will again return 1. Collision occurs here in the HashMap as element is already exist at index 1. Collision is resolved based on key value. Key is different here from the key of already existing element at index 1 and that’s why as discussed earlier the next field of already existing element will now point to the new node element which results into a linked list.

HashMap Internal Working

HashMap reading in java (HashMap get method):
We will use get() method to read the value of an element from HashMap. Index value is calculated first when get method is called with the specified key. Key will be compared to the key of the element at the calculated index value. If key matched is found then value of the element will be return otherwise next field of the element will be checked and if it is not null then key will be compared again with the key of next element and if key matched is found then value of the element will be return otherwise so on until next refers to null.

Please follow and like us:
Posted in Java   


Copyright © 2019 CodesJava DMCA.com Protection Status SiteMap Reference: Java Wiki