How to create your own HashMap ?

Your own HashMap implementation must :

1. Define size

    Set initial size = 2^4 = 16

    For expanding HashMap, make size to its double using power, i.e. 2^5= 32

    For reducing HashMap, make size to its half using power, i.e. 2^3= 8

1. Need to store the key-value pairs

    Make an Entry class to store these pairs with variables : key, value and next pointer

    next is used to keep chain (linked list) of Entry objects with same hashcode (to avoid collision)

2. Have put() method to put new entries

    Identify the bucket using hash(hashcode%SIZE)

    a. If no element exists in that bucket : Put it as new Entry.

    b. If element already exists , 

        If element is duplicate, replace old one

       otherwise, find the last element in the chain and add new entry to next pointer of last element.

3. Return element from get() method

    Identify the element bucket by calculate the hash(hashcode%SIZE) of the key,

    and return the element using equals method.

Example

public class MyHashMap {

  private static final int SIZE = 16;

  private Entry table[] = new Entry[SIZE];

  /**

    * Map data structure with key and value.

    * It have linked list pointer 'next' to store multiple key-value pair

    * in same bucket with same hashcodes and different keys (collisions)

    */

    class Entry {

        final String key;

        String value;

        Entry next;

        Entry(String k, String v) {

            key = k;

            value = v;

        }

        public String getValue() {

            return value;

        }

        public void setValue(String value) {

            this.value = value;

        }

        public String getKey() {

            return key;

        }

      }

    /**

      * Returns the entry associated with the specified key in HashMap.

      * Returns null if the HashMap contains no mapping for the key.

      */

      public Entry get(String k) {

         int hash = k.hashCode() % SIZE;

         Entry e = table[hash];

         // If bucket is found then traverse through the linked list and

         // see if element is present

         while(e != null) {

            if(e.key.equals(k)) {

                return e;

            }

            e = e.next;

         }

         return null;

      }

      /**

       * Associates the specified value with specified key in HashMap.

       * If the map previously contained a mapping for the key, replace value.

       */

      public void put(String k, String v) {

         int hash = k.hashCode() % SIZE;

         Entry e = table[hash];

         if(e != null) {

            // If trying to insert duplicate key-value pair,

            // hence overwrite the current pair with the old pair

            if(e.key.equals(k)) {

                 e.value = v;

            } else {

                // Traverse to the end of the list and insert new element

                // in the same bucket

                while(e.next != null) {

                     e = e.next;

                }

                Entry entryInOldBucket = new Entry(k, v);

                e.next = entryInOldBucket;

            }

         } else {

                // New element in the map, hence creating new bucket

                Entry entryInNewBucket = new Entry(k, v);

                table[hash] = entryInNewBucket;

         }

    }

    // Test method

    public static void main(String[] args) {

        MyHashMap myHashMap = new MyHashMap();

        myHashMap.put("Shaan", "TA");

        myHashMap.put("Rahul", "SSE");

        myHashMap.put("Rajesh", "SE");

        myHashMap.put("Gaurav", "SE");

        Entry e = myHashMap.get("Rahul");

        System.out.println(""+e.getValue());

    }

}

Output : SSE