HashMap Implementation In Java

Chapter: Data Structures Last Updated: 07-07-2018 08:40:59 UTC

Program:

            /* ............... START ............... */
                
import java.util.ArrayList;
import java.util.LinkedList;

public class HashMap<K,V> {
	public class hmnodes{ //HashMap nodes 
		K key;
		V value;
	}
	
	private int size=0; //size of hashmap
	private LinkedList<hmnodes> buckets[];  //array of addresses of list
	
	public HashMap(){
		buckets=new LinkedList[4]; //initially create bucket of any size 
		for(int i=0;i<4;i++)
			buckets[i]=new LinkedList<>(); 
	}
	
	public void put(K key,V value) throws Exception{
		int bi=bucketIndex(key); //find the index,the new key will be inserted in linklist at that index
		int fountAt=find(bi,key); //check if key already exists or not 
		if(fountAt==-1){
			hmnodes temp=new hmnodes(); //if doesn't exist create new node and insert 
			temp.key=key;
			temp.value=value;
			buckets[bi].addLast(temp);
			this.size++;
		}else{
			buckets[bi].get(fountAt).value=value;//if already exist modify the value
		}
		
		double lambda = (this.size*1.0)/this.buckets.length;
		if(lambda>2.0){
			rehash();  //rehashing function which will increase the size of bucket as soon as lambda exceeds 2.0
		}
		
		return;
	}
	

	public V get(K key) throws Exception{
		int bi=bucketIndex(key);
		int fountAt=find(bi,key);
		if(fountAt==-1){
			return null;
		}else{
			return buckets[bi].get(fountAt).value;
		}
	}
	
	public V remove(K key) throws Exception{
		int bi=bucketIndex(key);
		int fountAt=find(bi,key);
		if(fountAt==-1){
			return null;
		}else{
			this.size--;
			return buckets[bi].remove(fountAt).value;
		}
	}
	
	public boolean containskey(K key) throws Exception{
		int bi=bucketIndex(key);
		int fountAt=find(bi,key);
		if(fountAt==-1){
			return false;
		}else{
			return true;
		}
	}
	
	public int size(){
		return this.size;
	}
	
	
	public boolean isempty(){
		return this.size==0;
	}
	
	public ArrayList<K> keyset() throws Exception{
		ArrayList<K> arr=new ArrayList<>();
		for(int i=0;i<buckets.length;i++){
			for(int j=0;j<buckets[i].size();j++){
				arr.add(buckets[i].get(j).key);
			}
		}
		return arr;
	}
	
	public ArrayList<V> valueset() throws Exception{
		ArrayList<V> arr=new ArrayList<>();
		for(int i=0;i<buckets.length;i++){
			for(int j=0;j<buckets[i].size();j++){
				arr.add(buckets[i].get(j).value);
			}
		}
		return arr;
	}
	
	public void display() throws Exception{
		for(int i=0;i<buckets.length;i++){
			System.out.print("Bucket: "+i+" ");
			for(int j=0;j<buckets[i].size();j++){
				hmnodes temp=buckets[i].get(j);
				System.out.print("["+temp.key+"->"+temp.value+"]");
			}
			System.out.println();
		}
	}
	
	public int find(int bi,K key) throws Exception{
		for(int i=0;i<buckets[bi].size();i++){
			if(key.equals(buckets[bi].get(i).key))
				return i;
		}
		return -1;
	}
	
	public int bucketIndex(K key) throws Exception{
		int bi=key.hashCode();
		return Math.abs(bi%buckets.length);
	}

	private void rehash() throws Exception{
		LinkedList<hmnodes> ob[]= buckets;
		buckets=new LinkedList[ob.length*2];
		for(int i=0;i<ob.length*2;i++)
			buckets[i]=new LinkedList<>();
		
		size = 0;
		for(int i=0;i<ob.length;i++){
			for(int j=0;j<ob[i].size();j++){
				put(ob[i].get(j).key,ob[i].get(j).value);
			}
		}
		
	}
	public static void main(String args[]) {
		System.out.println("Hash map implementation in java ");
		HashMap<Integer,String > map = new HashMap<>();
		try {
			map.put(1, "Value 1");
			map.put(2, "Value 2");
			map.put(3, "Value 3");
			map.put(4, "Value 4");
			map.put(5, "Value 5");
			map.put(6, "Value 6");
			
			System.out.println("Contains Key 1"+map.containskey(1));
			System.out.println("Contains Key 5"+map.containskey(5));

			
			
			System.out.println(map.get(1));
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}
                /* ............... END ............... */
        

Output

Hash map implementation in java 
Contains Key 1true
Contains Key 5true
Value 1

Notes:

  • For HashMap implementation we use a class that is used for storing Key and value pairs, it is denoted as HashMap<Key, Value>.
  • HashMap is a Map based collection class that is used for storing Key and value pairs.
  • To Store key and value first we have to create a class with key and values. Check the class implementation hmodes class.
  • Declare a variable to handle the size of the hashmap and linkedlist store the elements of hashamp.
  • In the HashMap() constructor create and initialize the bucket of specific size.
  • bucketIndex(Key) function will returns the index to store the element in the hashmap. We are passing key as the argument in function. First we will find the hashcode of key by using the function hashcode() in java, then will do Modulus (%) operation with bucket size to get the index.
  • find(int index,K key) function is used to check whether key already exists or not. For that it wil iterate buckets and check whether key exists or not if found it will return the index of key or return -1.

Tags

Implement hashmap in java, hashmap Key and Value, hashmap functions

Similar Programs Chapter Last Updated
Linked List Implementation In Java Data Structures 09-03-2018
Queue Implementation In Java Data Structures 02-03-2018
Stack Implementation In Java Data Structures 08-03-2018
Binary Search Tree Java Data Structures 11-02-2018
Insertion Sort In Java Data Structures 10-02-2018
Java Stack Example Data Structures 16-10-2017
Java String Array Sort Data Structures 31-03-2017
Java Hashmap Add Key And Value Data Structures 25-03-2017
Java Binary Tree Vertical Sum Data Structures 11-11-2016
Java Binary Tree Boundary Traversal Data Structures 11-11-2016
Java Binary Tree Lowest Common Ancestor (LCA) Data Structures 11-11-2016
Java Binary Tree Maximum Element Data Structures 11-11-2016
Java Three Dimensional Array Data Structures 28-10-2016
Java Infix Expression To Postfix Expression Data Structures 25-10-2016
Java Linked List Add Element First And Last Data Structures 24-10-2016
Java Maximum Element From Vector Data Structures 24-10-2016
Java Binary Search On Vector Data Structures 24-10-2016
Java Get Elements Of LinkedList Data Structures 23-10-2016
Java Linked List Update Element Data Structures 23-10-2016
Java Delete Elements From LinkedList Data Structures 23-10-2016
Java Double Ended Queue Data Structures 09-10-2016
Java Dynamic Queue Using Array Data Structures 07-10-2016
Java Queue Array Based Implementation Data Structures 07-10-2016
Java Sort Short Array Data Structures 25-09-2016
Java Sort Long Array Data Structures 25-09-2016
Java Sort Int Array Data Structures 19-09-2016
Java Sort Float Array Data Structures 19-09-2016
Java Sort Double Array Data Structures 19-09-2016
Java Sort Char Array Data Structures 19-09-2016
Java Sort Byte Array Data Structures 19-09-2016

1 2 3