HashMap Implementation in Java

HashMap is a data structure used to store the key value pairs.
It uses the hash function for mapping the keys to values.

For More Info,Refer the wiki page.
en.wikipedia.org/wiki/Hash_table

Here I've given a sample implementation in Java.

Given very basic implentation which uses the simple collision avoiding technique known as Horizontal Chaining with list heads.

import java.util.LinkedList;


/**
 * Simple Implementation of a HashMap in Java
 * Hash Collision is handled using Chaining mechanism with the usage of LinkedList
 * @author hbalakrishnan
 *
 */
public class MyHashMap {
    int hash_bucket_size = 17;// default hashbucket size, Good to use prime numbers for random distribution
    HashEntry[] values; // An array to hold all the vertical references of HashEntry
   
    /**
     * Just a simple class which hold key and value,
     * Also it has the the horizontal chaining mechanism to avoid collision
     *
     * @author hbalakrishnan
     *
     */
    static class HashEntry {
        String key;
        String value;
        LinkedList<HashEntry> list=null;
       
        HashEntry() {
            list = new LinkedList<HashEntry>();
        }
       
        public String getKey() {
            return key;
        }

        public void setKey(String key) {
            this.key = key;
        }

        public String getValue() {
            return value;
        }

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

        public LinkedList<HashEntry> getList() {
            return list;
        }

        public void setList(LinkedList<HashEntry> list) {
            this.list = list;
        }

       
    }
   
    public MyHashMap() {
        values = new HashEntry[this.hash_bucket_size];
    }
   
    public MyHashMap(int size) {
        this.hash_bucket_size=size;
        values = new HashEntry[this.hash_bucket_size];
    }
   
    public int hash(int hashCode) {
        return hashCode % this.hash_bucket_size;
    }
   
    /**
     * This method is to add the key value pair to the HashMap
     * 1. Get the hashCode of the key
     * 2. Apply the hash function to the hashCode, Here we use modules function to get the position
     * 3. Check the existence of hashEntry from the array position
     * 4. If the hashEntry is not found
     *         then create a new HashEntry
     *         populate the key value pair
     *         add the hashEntry object to the array's position
     *
     * 5. If the hashEntry is found then we need to avoid the collision
     *         Each HashEntry has a linked list associated to it.
     *         create a new HashEntry
     *         populate the key value pair
     *      Add the hashEntry to the list.
     *     
     *
     * @param key
     * @param value
     */
   
    public void put(String key, String value) {
        int position = hash(key);
       
        System.out.println("Index for "+value+"::"+position);
       
        if(values[position] == null) {
            System.out.println("Bucket Entry with key::"+key+"::value::"+value);
            HashEntry hashEntry = new HashEntry();
            hashEntry.setKey(key);
            hashEntry.setValue(value);
            values[position] = hashEntry;
        } else {
            HashEntry hashEntry = values[position];
            // the position of the hashmap is filled, so use the horizontal chaining
            LinkedList list = hashEntry.getList();
            System.out.println("List Entry with key::"+key+"::value::"+value+"::Position::"+position);
            HashEntry hashEntryChain = new HashEntry();
            hashEntryChain.setKey(key);
            hashEntryChain.setValue(value);
            list.add(hashEntryChain);
        }
       
    }

    private int hash(String key) {
        int keyCode = key.hashCode();
        int position = keyCode % hash_bucket_size;
        return position;
    }
   
   
    /**
     * This method is to remove the values associated with a key
     * it follows the same procedure of get to remove the keys
     * We are making the hashEntry key and value as null in place of removing.
     * Later we need to do ReHash to build the hash again, because we need to reclaim the lot of empty storage.
     * @param key
     */
   
    public void remove(String key) {
        int position = hash(key);
        HashEntry hashEntry = values[position];
        if(hashEntry!= null) {
            if(key.equals(hashEntry.getKey())) {
                if(!hashEntry.getList().isEmpty())
                    values[position] = hashEntry.getList().removeFirst();
            } else {
                int j=-1;
                for(HashEntry hashEntryIndex : hashEntry.getList() ) {
                    if(key.equals(hashEntryIndex.getKey())) {
                        j++;
                        break;
                    }
                }
                hashEntry.getList().remove(j);

            }
        }
    }
   
    /**
     * This method is to get the value from the HashMap
     *
     * 1. Get the hashCode of the key
     * 2. Apply the hash function to the hashCode, Here we use modules function to get the position
     * 3. Check the existence of hashEntry from the array position
     * 4. If is found , then check whether the supplied key equals to the  hashEntry.getKey, If so return
     * 5. If not Iterate thro all the list associated with the hashEntry
     * 4. Follow the step 4
     *
     *
     * @param key
     * @return
     */
   
   
    public String get(String key) {
        int position = hash(key);
       
        if(values[position] == null)
                return null;
       
       
        HashEntry hashEntry =  values[position];
        if(key.equals(hashEntry.getKey()))
                return hashEntry.getValue();
       
        for(HashEntry hashEntryIndex : hashEntry.getList()) {
            if(key.equals(hashEntryIndex.getKey()))
                return hashEntryIndex.getValue();
        }
        return null;   
    }
   
   
    public static void main(String[] args) {
        MyHashMap hMap = new MyHashMap(16);
        hMap.put("venky", "venkatesh");
        hMap.put("hari", "HariB");
        hMap.put("Hari", "HariBK");
        hMap.put("sateesh", "Satish Gogi");
       
        System.out.println(hMap.get("venky"));
        System.out.println(hMap.get("hari"));
        System.out.println(hMap.get("Hari"));
        hMap.remove("Hari");
        System.out.println(hMap.get("Hari"));
       
    }
   
}