Implement HashMap in Java

to implement following functions in HashMap:

put(), get(), remove(), size(),keySet(),containsKey()

We will be using Arrays of LinkedList . Each linked List will represent a bucket. After hashing of keys, the key will be added to its corresponding bucket.

Our Node will look like this .

private class HMNode{
      K key;
      V value;
     HMNode(K key, V value){
       this.key=key;
       this.value=value;
     }
   }

Now we will see the basic attributes of our HashMap Class:

public static class HashMap<K,V>{
   private class HMNode{
      K key;
      V value;
     HMNode(K key, V value){
       this.key=key;
       this.value=value;
     }
   }
  private int size=n;
  private LinkedList<HMNode>[] buckets; //--> length of bucket= N
  public HashMap(){
    size=0;
    initbuckets(8);
  }
  private initbuckets(int N){
    buckets= new LinkedList[N];
    for(int i=0;i<N;i++){
      buckets[i] =new LinkedList();
    }
  }
}

put()

first we need to find in which bucket our key is present, then after finding it we will find the index of our key in that bucket. and if the key is already present we update the value of node else we add a new node and increment size by 1. We also need to check that our lambda doesn’t become more than threshold , if it does we call rehash() function. rehash() creates 2N buckets and put all the nodes in these new buckets.

rehash()- When HashMap reaches its threshold limit of .75 or 75% it re-size by creating a new array of double the previous size HashMap, and then start putting every old element into that new bucket array and this is called rehashing and it also applies hash function to find new bucket location.

private int hashfn(K key){
    int hc= key.hashcode();
    return Math.abs(hc)%buckets.length;
  }
  public int getIndexWithinBucket(K key, int bi){
    int di=0;
    for(HMNode node: buckets[bi]){
      if(node.key.equals(key){
        return di;
      }
         di++;
    }
     return -1;
  }
  public void put(K key, V value){
    int bi = hashfn(key);
    int idx = getIndexWithinBucket(key,bi);
    if(di!=-1){
      HMNode node = buckets[bi].get(idx);
      node.value= value;
    }
    else{
      HMNode node = new HMNode(key,value);
      buckets[bi].add(node);
      size++;
    }
    double lambada = size*1.0/buckets.length;
    if (lambda>2.0) {
        rehash();
      //here 2.0  is threshold;
    }
    
  }
  public void rehash(){
  LinkedList<HMNode> temp[] = buckets;
  buckets= initbuckets(2*buckets.length);
  int size=0;
  for(int i=0;i<temp.length;i++){
    for(HMNode node: temp[i]){
      put(node.key,node.value);
    }
  }
 }

get()

first we need to find in which bucket our key is present, then after finding it we will find the index of our key in that bucket. and if the key is present we return its value else we return null.

public V getKey(K key) throws Exception{
    int bi = hashfn(key);
    int idx = getIndexWithinBucket(key,bi);
   if(idx!=-1){
    HMNode node = buckets[bi].get(idx);
    return node.value
   }
   else return null;
 }

containsKey()

first we need to find in which bucket our key is present, then after finding it we will find the index of our key in that bucket. and if the key is present we return true else we return false.

public boolean containsKey(K key) throws Exception{
    int bi = hashfn(key);
    int idx = getIndexWithinBucket(key,bi);
   if(idx==-1) return false;
   else return true;
 }

remove()

first we need to find in which bucket our key is present, then after finding it we will find the index of our key in that bucket. and if the key is present we remove the key from the bucket else we return null.

public V remove(K key) throws Exception{
      int bi = hashfn(key);
    int idx = getIndexWithinBucket(key,bi);
   if(idx!=-1){
    HMNode node = buckets[bi].remove(idx);
     size--;
    return node.value
   }
   else return null;
 }

size()

we just return the size of the Hashmap. We are incrementing size when we call put function and add a new key and we are decrementing size when we call remove function and deleting a already present key.

public int size(){
  return size;
 }

keySet()

We are iterating through all the buckets and and for each bucket , we are taking they keys present in it.

public ArrayList<K> keySet(){
    ArrayList<K> keys= new ArrayList();
   for(int i=0;i<buckets.length;i++){
    for(HMNode node: buckets[i]){
      keys.add(node.key);
    }
   }
   return keys;
 }

Code:

Implementing our own Hash function

In our code we have used java’s inbuilt hashfunction. We can also implement our own hash function. We need to convert key, value pairs into indices.