Implementation of Custom HashMap code issues

Question

I am preparing my own custom HashMap implementation in Java. Below is my imlementation.

public class Entry<K,V> {

private final K key;
private V value; 
private Entry<K,V> next; 

public Entry(K key, V value, Entry<K,V> next) {
    this.key = key;
    this.value = value; 
    this.next = next;
}

public V getValue() {
    return value;
}

public void setValue(V value) {
    this.value = value;
}

public Entry<K, V> getNext() {
    return next;
}

public void setNext(Entry<K, V> next) {
    this.next = next;
}

public K getKey() {
    return key;
}
}



public class MyCustomHashMap<K,V> {

    private int DEFAULT_BUCKET_COUNT = 10;

    private Entry<K,V>[] buckets; 

    public MyCustomHashMap() { 
        buckets = new Entry[DEFAULT_BUCKET_COUNT];
        for (int i = 0;i<DEFAULT_BUCKET_COUNT;i++)
            buckets[i] = null;      
    }

    public void put(K key,V value){

        /**
         * This is the new node. 
         */
        Entry<K,V> newEntry = new Entry<K,V>(key, value, null);

        /**
         * If key is null, then null keys always map to hash 0, thus index 0
         */
        if(key == null){
            buckets[0] = newEntry;
        }

        /** 
         * get the hashCode of the key.
         */
        int hash = hash(key);

        /**
         * if the index does of the bucket does not contain any element then assign the node to the index.  
         */
        if(buckets[hash] == null) {
            buckets[hash] = newEntry;
        } else { 

            /**
             * we need to traverse the list and compare the key with each of the keys till the keys match OR if the keys does not match then we need 
             * to add the node at the end of the linked list. 
             */

            Entry<K,V> previous = null;
            Entry<K,V> current = buckets[hash];

            while(current != null) {

                boolean done = false;

                while(!done) {

                    if(current.getKey().equals(key)) {
                        current.setValue(value); 
                        done = true; // if the keys are same then replace the old value with the new value;   
                    } else if (current.getNext() == null) {
                        current.setNext(newEntry);
                        done = true; 
                    }                   
                    current = current.getNext();
                    previous = current; 
                }
            } 
            previous.setNext(newEntry);
        }


    }

    public V getKey(K key) {

        int hash = hash(key);

        if(buckets[hash] == null) {
            return null;
        } else {
            Entry<K,V> temp = buckets[hash];
            while(temp != null) {
                if(temp.getKey().equals(key))
                    return temp.getValue();  // returns value corresponding to key. 
                temp = temp.getNext();
            }
            return null;  //return null if key is not found. 
        }

    }


    public void display() {

        for(int i = 0; i < DEFAULT_BUCKET_COUNT; i++) {

            if(buckets[i] != null) {
                Entry<K,V> entry = buckets[i];

                while(entry != null){
                    System.out.print("{"+entry.getKey()+"="+entry.getValue()+"}" +" ");
                    entry=entry.getNext();
                }
            }
        }
    }

    public int bucketIndexForKey(K key) {
        int bucketIndex = key.hashCode() % buckets.length;
        return bucketIndex; 
    }


     /**
      * 
      * @param key
      * @return
      */
     private int hash(K key){
         return Math.abs(key.hashCode()) % buckets.length;
     }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyCustomHashMap<String, Integer> myCustomHashMap = new MyCustomHashMap<String, Integer>();
        myCustomHashMap.put("S", 22);
        myCustomHashMap.put("S", 1979);
        myCustomHashMap.put("V", 5);
        myCustomHashMap.put("R", 31);


        System.out.println("Value corresponding to key R: "+myCustomHashMap.getKey("R"));

        System.out.println("Value corresponding to key V: "+myCustomHashMap.getKey("V"));

        System.out.println("Displaying the contents of the HashMap:: ");

        myCustomHashMap.display();

    }

}

1) I feel that put (K key,V value) is somewhat flawed. Please do kindly validate and let me know what's wrong here. On entering the same key its giving me wrong result. I have not yet tested it for collision cases having different keys.

2) It is said that we rehash the hashCode so that it eliminates wrong implementation of hashCode. how do I do it because if I give hashCode of key i.e. hash(key.hashCode()) then it dosn't take as it can't compute hashCode of int. How to do this?

Any help would be highly appreciated.

Thanks Sid

Answer 1

1. You handle null key incorrectly :

   if(key == null){
       buckets[0] = newEntry;
   }
   

It's possible that buckets[0] already contains entries, in which case you will lose those entries.

2. The following loop has some issues :

       Entry<K,V> previous = null;
       Entry<K,V> current = buckets[hash];
   
       while(current != null) {
   
           boolean done = false;
   
           while(!done) {
   
               if(current.getKey().equals(key)) {
                   current.setValue(value); 
                   done = true; 
               } else if (current.getNext() == null) {
                   current.setNext(newEntry);
                   done = true; 
               }                   
               current = current.getNext();
               previous = current; // you are not really setting previous to
                                   // to the previous Entry in the list - you
                                   // are setting it to the current Entry
           }
       } 
       previous.setNext(newEntry); // you don't need this statement. You
                                   // already have a statement inside the
                                   // loop that adds the new Entry to the list
   

It looks like removing any statements related to previous will fix this loop.

EDIT:

As kolakao commented, in order for your implementation to be efficient (i.e. require expected constant time for get and put), you must resize the HashMap when the number of entries exceeds some threshold (in order for the average number of entries in each bucket to be bound by a constant).

It is said that we rehash the hashCode so that it eliminates wrong implementation of hashCode. how do I do it because if I give hashCode of key i.e. hash(key.hashCode()) then it dosn't take as it can't compute hashCode of int. How to do this?

The idea of re-hashing doesn't involve calling hashCode for the hashCode of the key. It involves running some hardcoded function on the value obtained by key.hashCode().

For example, in Java 7 implementation of HashMap, the following function is used :

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

Then you use it with :

int hash = hash(key.hashCode());
int bucket = hash % buckets.length;