/*
 * In this problem, I follow some basic settings in JDK, such as
 * DEFAULT_INITIAL_CAPACITY and DEFAULT_LOAD_FACTOR value. Inside
 * MyHashMap, there is an inner static class MyEntry to save the
 * key-value pair. MyEntry also serves as a linked list with its
 * next field. Following the JDK size modification, resize() is also
 * implemented to do the element moving operation. The hash()
 * method is directly copied from JDK source code for simplification.
 */

class MyHashMap<K, V> {
    private static final int DEFAULT_INITIAL_CAPACITY = 16;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    private MyEntry[] table;
    private int size;
    public static class MyEntry<K, V> {
        K key;
        V value;
        int hash;
        MyEntry<K, V> next;
        public MyEntry(K key, V value, int hash, MyEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }
    }
    public MyHashMap() {
        table = new MyEntry[DEFAULT_INITIAL_CAPACITY];
        size = 0;
    }
    public V get(K key) {
        if (key == null) {
            throw new RuntimeException("key is null");
        }
        int hash = hash(key.hashCode());
        int index = indexFor(hash, table.length);
        MyEntry<K, V> e = table[index];
        while (e != null) {
            if (hash == e.hash && (key == e.key || key.equals(e.key))) {
                return e.value;
            }
            e = e.next;
        }
        return null;
    }
    public V put(K key, V value) {
        if (key == null) {
            throw new RuntimeException("key is null");
        }
        int hash = hash(key.hashCode());
        int index = indexFor(hash, table.length);
        MyEntry<K, V> e = table[index];
        while (e != null) {
            if (e.hash == hash && (key == e.key || key.equals(e.key))) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
            e = e.next;
        }
        MyEntry<K, V> next = table[index];
        table[index] = new MyEntry<>(key, value, hash, next);
        if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {
            resize();
        }
        return null;
    }
    private void resize() {
        int newCapacity = table.length * 2;
        MyEntry[] newTable = new MyEntry[newCapacity];
        MyEntry[] src = table;
        for (int j = 0; j < src.length; j++) {
            MyEntry<K, V> e = src[j];
            src[j] = null;
            while (e != null) {
                MyEntry<K, V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
        table = newTable;
    }
    static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
    static int indexFor(int h, int length) {
        h = h > 0 ? h : -h;
        return h % length;
    }
}

public class q3 {
    public static void main(String[] args) {
        MyHashMap<String, String> map = new MyHashMap<>();
        map.put("Tom", "good");
        map.put("Bob", "bad");
        map.put("Ash", "fair");
        // return old value and save new value
        String oldValue = map.put("Ash", "good");
        System.out.println("value for " + "Tom: " + map.get("Tom"));
        System.out.println("value for " + "Bob: " + map.get("Bob"));
        System.out.println("old value for Ash:" + oldValue);
        System.out.println("new value for Ash:" + map.get("Ash"));
    }
}