public class MyHashMap<K, V>{

    class Node<K, V> {
        private K key;
        private V value;
        private Node<K, V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public Node(K key, V value, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    final int DEFAULT_CAPACITY = 16;
    float loadFactor = 0.75f;
    private int size;
    private Node<K, V>[] table;

    public MyHashMap() {
        table = new Node[DEFAULT_CAPACITY];
        size = 0;
    }

    public MyHashMap(int capacity) {
        table = new Node[capacity];
        size = 0;
    }

    private int getIndex(K key, int length) {
        int index = Math.abs(key.hashCode()) % length;
        return index;
    }

    public void put(K key, V value) {
        if(size >= table.length * loadFactor)  resize();
        putVal(key, value, table);
    }

    private void putVal(K key, V value, Node<K, V>[] table) {
        int index = getIndex(key, table.length);
        Node node = table[index];
        //插入的位置为空
        if(node == null) {
            table[index] = new Node<>(key, value);
            size ++ ;
            return ;
        }
        //插入位置不为空，使用链地址
        while(node != null) {
            //如果key相同，就覆盖掉
            if((node.key.hashCode() == key.hashCode())
                    && (node.key == key || node.key.equals(key))) {
                node.value = value;
                return ;
            }
            node = node.next;
        }
        //当前key不在链表，插入头部
        Node newNode = new Node(key, value, table[index]);
        table[index] = newNode;
        size ++ ;
    }

    private void resize() {
        int newCapacity = table.length * 2;
        Node<K, V>[] newTable = new Node[newCapacity];
        rehash(newTable);
        table = newTable;
    }

    private void rehash(Node<K, V>[] newTable) {
        size = 0;
        for(int i = 0; i < table.length; i++) {
            if(table[i] == null) {
                continue;
            }
            Node<K, V> node = table[i];
            while(node != null) {
                putVal(node.key, node.value, newTable);
                node = node.next;
            }
        }
    }

    public V get(K key) {
        int index = getIndex(key, table.length);
        if(table[index] == null) {
            return null;
        }
        Node<K, V> node = table[index];
        while(node != null) {
            if((node.key.hashCode() == key.hashCode())
            && (node.key == key || node.key.equals(key))) {
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

    public int size() {
        return size;
    }
}