HashMap Implementation

package pep.Day68;

import java.util.ArrayList;

public class HashMap_Implementation {
    private class Node {
        Integer key = 0;
        Integer value = 0;
        Node next = null;

        Node(Integer key, Integer value) {
            this.key = key;
            this.value = value;
        }
    }

    private class MyLinkedList {
        public Node head = null, tail = null;
        public int numberOfElements = 0;

        public int size() {
            return numberOfElements;
        }

        public void addLast(Node node) {
            if (head == null) {
                head = tail = node;
            } else {
                tail.next = node;
                tail = tail.next;
            }
            numberOfElements++;
        }

        public Node getFirst() {
            return head;
        }

        public Node removeFirst() {
            Node temp = head;
            if (numberOfElements == 0)
                head = tail = null;

            if (head != null) {
                head = head.next;
                numberOfElements--;
            }

            return temp;
        }
    }

    private MyLinkedList[] containers;
    private int sizeOfHashMap = 0;

    public void assignValues(int size) {
        containers = new MyLinkedList[size];
        sizeOfHashMap = 0;
        for (int i = 0; i < size; i++) {
            containers[i] = new MyLinkedList();
        }
    }

    HashMap_Implementation() {
        assignValues(5);
    }

    // jo bhi yeh return krega woh container ki range me hogi,
    // hence, mujhe unique container mil jaega
    private int hashCode(Integer key) {
        int val = key.hashCode();
        return val % containers.length;
    }

    // aab hum container nikalenge,
    // hashCode() method se jo key mile hai, usse konsa group ya container allot krenge
    private MyLinkedList group(Integer key) {
        int code = hashCode(key);

        return containers[code];
    }

    public int getOrDefault(Integer key, Integer defaultVal) {
        return containsKey(key) ? get(key) : defaultVal;
    }

    // iss baat ki guarantee nhi hai, ki jo user ne key daale hai woh exist krege

    public int get(Integer key) {
        // yeh krne se agr mere key mil jaege to humne apni key ko head pr daal diya hoga
        boolean isKey = containsKey(key);

        // yha se mujhe mere container ki linked list mil jaege
        MyLinkedList group = group(key);
        return isKey ? group.head.value : null;
    }

    public boolean containsKey(Integer key) {
        MyLinkedList group = group(key);
        int size = group.size();

        while (size-- > 0) {
            if (group.getFirst().key == key)
                return true;

            // agr first element me key nhi hai
            // first element ko remove krenge aur last me add kr denge
            group.addLast(group.removeFirst());
        }
        return false;

    }

    public boolean isEmpty() {
        return sizeOfHashMap == 0;
    }

    public Integer remove(Integer key) {
        boolean isKey = containsKey(key);

        if (!isKey) {
            return null;
        }

        MyLinkedList group = group(key);
        Node returnValue = group.removeFirst();
        sizeOfHashMap--;
        return returnValue.value;
    }

    public ArrayList<Integer> keySet() {
        ArrayList<Integer> keys = new ArrayList<>();
        for (int i = 0; i < containers.length; i++) {
            MyLinkedList group = containers[i];
            int size = group.size();
            while (size-- > 0) {
                Node node = group.removeFirst();
                keys.add(node.key);
                group.addLast(node);
            }
        }
        return keys;
    }

    public void put(Integer key, Integer value) {
        // isme check krna hoga ki pehle se exist krte hain value ya nahi
        boolean isKey = containsKey(key);
        if (isKey) {
            MyLinkedList group = group(key);
            group.head.value = value;
        } else {
            MyLinkedList group = group(key);
            group.addLast(new Node(key, value));
            sizeOfHashMap++;

            // humne starting me hashmap ke 10 containers liye the
            // but jese hi mera lambda 0.6 se jyada hoga toh hum REHASH kr denge
            double lambda = group.size() / (containers.length * 0.1);
            if (lambda > 0.6)
                rehash();
            // rehash hum islea kar rhe hain, taki linked list me search time kaam ho sake
        }
    }

    private void rehash() {
        // shallow copy bnn gae
        MyLinkedList[] backup = containers;
        // agr lambda cross hota hai to, main double size ka hashmap bnaunga
        // also, yha pr humne nya hashmap bna liya
        assignValues(2 * backup.length);
        for (int i = 0; i < backup.length; i++) {
            MyLinkedList group = backup[i];
            int size = group.size();

            while (size-- > 0) {
                Node node = group.removeFirst();
                put(node.key, node.value);
            }
        }
    }

    public void putIfAbsent(Integer key, Integer value) {
        if (!containsKey(key))
            put(key, value);
    }

    public void display() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");

        for (int i = 0; i < containers.length; i++) {
            MyLinkedList group = containers[i];
            int size = group.size();

            while (size-- > 0) {
                Node node = group.removeFirst();
                sb.append("(" + node.key + "->" + node.value + ") ");
                group.addLast(node);
            }
        }
        sb.append("]");

        System.out.println(sb.toString());
    }


}

class Client {
    public static void main(String[] args) {
        HashMap_Implementation hm = new HashMap_Implementation();

        // rehashing hogi as mere Hashmap ka size pehle 5 tha aur hum 8 values add kr rhe hain
        for (int i = 0; i < 8; i++) {
            hm.put(i, i * 10);
        }
        System.out.println(hm.getOrDefault(4, 400));
        System.out.println(hm.getOrDefault(40, 400));
        hm.display();
    }
}