HashMap API:

put(K key, V value)

Value get(K key)

containsKey(K key)

containsValue(V value)

remove(K key)

isEmpty()

size()

Key points:

1. Single linked list array to store <key,value> pair
2. how to know which bucket the <key,value> pair should be in? ( hash code of the key % capacity. need to make sure have positive index key.hashCode() & 0x7FFFFFFF)
3. how to resize when load is higher than load factor(0.75)

Attentions:

1. need to provide empty input of constructor for flexibility.
2. equalsValue(V value1, V value2) and equalsKey(K key1, K key2) are handy helper function

/**
 * Created by LEI_D on 1/22/2017.
 */

import java.util.Arrays;

public class MyHashMap<K, V> {

    // Node is a static class of MyHashMap, since it is
    // very closely bonded to MyHashMap class
    // we probably need to access this class outside from MyHashMap

    public static class Node<K, V> {
        final K key;
        V value;
        Node<K, V> next;

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

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }
    }
    // define global constants variable for capacity and load factor
    public static final int DEFAULT_CAPACITY = 16;
    public static final float DEFAULT_LOAD_FACTOR = 0.75f;

    private Node<K, V>[] array;
    private int size; // how many key-value sets actually stored in the hashMap
    private float loadFactor; // determine when to rehash

    public MyHashMap() {

        this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    public MyHashMap(int cap, float loadFactor) {
        if (cap <= 0) {
            throw new IllegalArgumentException("cap can not be <= 0");
        }
        this.array = (Node<K, V>[]) (new Node[cap]);
        this.size = 0;
        this.loadFactor = loadFactor;
    }

    public int size() {
        return this.size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    public void clear () {
        Arrays.fill(this.array,null);
        this.size = 0;
    }

        // convert key into index in the array bucket
    private int hash(K key) {
        if (key == null) {
            return 0;
        }
        return key.hashCode() & 0x7FFFFFFF; // guarantee non-negative
        // because java % return remainder rather than modulus. the remainder can be negative
    }

    private int getIndex(K key) {
        return this.hash(key) % array.length;
    }

    private boolean equalsValue (V v1, V v2) {
        return v1 == v2 || v1 != null && v1.equals(v2);
    }

    public boolean containsValue(V value) {
        if (isEmpty()) {
            return false;
        }
        for(Node<K, V> node : array) {
            while(node != null) {
                if (equalsValue(node.value, value)) {
                    return true;
                }
                node = node.next;
            }
        }
        return false;
    }

    private boolean equalsKey(K key1, K key2) {
        return key1 == key2 || key1 != null && key1.equals(key2);
    }

    public boolean containsKey(K key) {
        int index = getIndex(key);
        Node<K, V> node = array[index];
        while (node != null) {
            if (equalsKey(node.key, key)) {
                return true;
            }
            node = node.next;
        }
        return false;
    }

    public V get(K key) {
        int index = getIndex(key);
        Node<K, V> node = array[index];
        while (node != null) {
            if (equalsKey(node.key, key)) {
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

    // if key already exists, return the old corresponding value
    // if the key not exists, return null
    public V put(K key, V value) {
        int index = getIndex(key);
        Node<K, V> head = array[index];
        Node<K, V> node = head;
        while (node != null) {
            if (equalsKey(node.key, key)) {
                V result = node.value;
                node.value = value;
                return result;
            }
            node = node.next;
        }

        //if key not exists, append new node to the head and update array
        Node<K, V> newNode = new Node(key, value);
        newNode.next = head;
        array[index] = newNode;
        size++;
        if (needRehashing()) {
            reshashing();
        }
        return null;
    }

    private boolean needRehashing() {
        float ratio = (size + 0.0f) / array.length;
        return ratio >= loadFactor;
    }

    private void reshashing() {
        Node<K, V>[] newArray = (Node<K, V>[])( new Node[array.length * 2]);
        Node<K, V>[] orgArray = array;
        this.array = newArray;
        for (Node<K, V> node : orgArray) {
            while(node != null) {
                put(node.key, node.value);
                node = node.next;
            }
        }
    }

    public boolean remove(K key) {
        int index = getIndex(key);
        Node<K, V> node =  array[index];
        Node<K, V> dummy = new Node(key, 0);
        dummy.next = node;
        Node<K, V> prev = dummy;
        while (node != null) {
            if (equalsKey(node.key,key)) {
                prev.next = node.next;
                node.next = null;
                array[index] = dummy.next;
                size--;
                return true;
            }

            prev = node;
            node = node.next;

        }
        dummy.next = null;
        return false;
    }

}