A HashMap is a class in java which implements Map Interface that gives you a feature to store key-value pair. HashMap uses a hashing algorithm in which key is hashed and stored in array to that hashed index, hence retrieval and storing takes constant times. But when a duplicate data is provided to HashMap it overrides the previous data.

HashMap allows you to store null elements as well.

The each key value pair class can be represented as :

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

The key in the class Entry stands for key , val stands for value and next is used in order to store other values of same hashed key;

let us understand it using an array of type Entry called bucket[]. and let size of this be 10(for easy understanding purpose).

We use put method in order to store that key value pair in Map, that return a boolean ie. true when added ,false when not added to Map

Initially the bucket is empty so lets add two data

ie put(45,”string1") and put(99,”String2");

Now in the hood 45 key is hashed with a hashing algorithm, Here we are gonna use a simple hashing algo which hashes a key like this : key%bucket.length

The bucket length is 10 and key is 45 hence the hash we get is 5, so at location 5 in bucket we store “string1” and same goes with key 99 and stored at index 9. So now our array looks like this :

So, everything works great until I add 55,65 or some other value whose hash value is 5, because at index 5 data is already present, this is called Hash Collision and we can tackle this using linear chaining technique. Now whatever data is provided it will be added to next of that object. So lets add 55 with “string3” and 65 with “string4”

Hence this can take O(L) complexity in order to fetch a data in this case, where L is length of linked list chain.

Here is the complete custom implementation of HashMap in Java

public class HashMapCustom<K, V> {

    private final int DEFAULT_CAPACITY = 17;
    private final Entry[] bucket = new Entry[DEFAULT_CAPACITY];
    private int size = 0;

    private class Entry<K, V> {

        K key;
        V val;
        Entry next;

        public Entry(K key, V val, Entry next) {
            this.key = key;
            this.val = val;
            this.next = next;
        }

    }

    private int hashCode(K key) {
        return key.toString().length() > 13 ? key.toString().length() % DEFAULT_CAPACITY : key.toString().length() % DEFAULT_CAPACITY % 10;
    }

    public boolean put(K key, V val) {
        int hash = hashCode(key);
        if (bucket[hash] == null) {
            bucket[hash] = new Entry(key, val, null);
            size++;
            return true;
        }
        Entry temp = bucket[hash];
        if (temp.key.equals(key)) {
            temp.val = val;
            return true;
        }
        while (temp.next != null) {
            if (temp.key.equals(key)) {
                temp.val = val;
                return true;
            }
            temp = temp.next;
        }
        size++;
        temp.next = new Entry(key, val, null);
        return true;
    }

    public V get(K key) {
        int hash = hashCode(key);
        Entry temp = bucket[hash];
        while (temp != null) {
            if (temp.key.equals(key)) {
                return (V) temp.val;
            }
            temp = temp.next;
        }
        return null;
    }

    public boolean containsKey(K key) {
        return get(key) != null;
    }

    public boolean containsValue(V val) {
        for (int i = 0; i < bucket.length; i++) {
            Entry temp = bucket[i];
            while (temp != null) {
                if (temp.val.equals(val)) {
                    return true;
                }
                temp = temp.next;
            }
        }
        return false;
    }

    public V remove(K key) throws Exception {
        int hash = hashCode(key);
        Entry temp = bucket[hash];
        if (temp == null) {
            throw new Exception("No such element exception");
        }
        if (temp.key.equals(key)) {
            V retval = (V) bucket[hash].val;
            bucket[hash] = temp.next;
            size--;
            return retval;
        }
        while (temp.next != null) {
            if (temp.next.key.equals(key)) {
                break;
            }
            temp = temp.next;
        }
        if (temp.next == null) {
            throw new Exception("No such element exception");
        }
        V retval = (V) temp.next.val;
        temp.next = temp.next.next;
        size--;
        return retval;
    }

    public V getOrDefault(K key, V defaultValue) {
        V value = get(key);
        if (value != null) {
            return value;
        }
        return defaultValue;
    }

    public void clear() {
        for (int i = 0; i < bucket.length; i++) {
            bucket[i] = null;
        }
    }

    @Override
    public String toString() {
        String str = "{ ";
        for (int i = 0; i < bucket.length; i++) {
            Entry temp = bucket[i];
            while (temp != null) {
                str += temp.key + "=" + temp.val + " ";
                temp = temp.next;
            }
        }
        str += "}";
        return str;
    }

    public int size() {
        return size;
    }

    public Object[] toKeyArray() {
        Object[] t = new Object[size()];
        int j = 0;
        for (int i = 0; i < bucket.length; i++) {
            Entry temp = bucket[i];
            while (temp != null) {
                t[j++] = temp.key;
                temp = temp.next;
            }
        }
        return t;
    }

}

You can check out complete implementation of HashMap on my github repo and you can find all other data structure there too.