/*support operations:
size();
isEmpty();
clear();
get(K key);
put(K key, V value);
remove(K key);
containsKey(K key);
containsValue(V value);*/

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

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

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }
    }

    public static final int DEFAULT_CAP = 16;
    public static final float DEFAULT_LOAD_FACTOR = 0.75f;

    private int size;
    private Node<K,V>[] array;
    private float loadFactor;

    MyHashMap(int cap, float loadFactor) {
        this.array =(Node<K,V>[])new Node[cap];
        this.size = 0;
        this.loadFactor = loadFactor;
    }

    MyHashMap() {
        this(DEFAULT_CAP,DEFAULT_LOAD_FACTOR);
    }

    public int size() {
        return size;
    }

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

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

    private int hash(K key) {
        if (key == null) {
            return 0;
        }
        return key.hashCode() & 0X7FFFFFFF;
    }

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

    private boolean equalsKey(K k1, K k2) {
        if (k1 == null && k2 == null) {
            return true;
        }
        if (k1 == null || k2 == null) {
            return false;
        }

        return k1.equals(k2);
    }

    private boolean equalsVaule(V v1, V v2) {
        if (v1 == null && v2 == null) {
            return true;
        }
        if (v1 == null || v2 == null) {
            return false;
        }
        return v1.equals(v2);
    }

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

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

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

    public V put(K key, V value) {
        int index = getIndex(key);
        Node<K,V> cur = array[index];
        while(cur != null) {
            if (equalsKey(cur.key,key)) {
                V result = cur.value;
                cur.setValue(value);
                return result;
            }
            cur = cur.next;
        }
        Node<K,V> newNode = new Node(key, value);
        newNode.next = array[index];
        array[index] = newNode;
        size++;

        if(needRehasing(size)) {
            array = rehashing();
        }
        return null;
    }

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

    private Node<K,V>[] rehashing() {
        int oldCap = array.length;
        int newCap = oldCap * 2;
        Node<K,V>[] newArray = (Node<K,V>[])new Node[newCap];

        for(Node<K,V> cur : array) {
            int index = getIndex(cur.key);
            newArray[index] = cur;
        }
        return newArray;
    }

    public Node<K,V> remove(K key) {

        int index= getIndex(key);
        Node<K,V> cur = array[index];
        Node<K,V> dummy = new Node(null,null);
        dummy.next = cur;
        cur = dummy;
        while(cur.next != null) {
            if (equalsKey(cur.next.key, key)) {
                cur.next = cur.next.next;
                size--;
                return dummy.next;
            }
            cur = cur.next;
        }
        return null;
    }
}

注意的点是： hashcode 有可能为负数， 所以需要和0X7FFFFFFF 相与。 equals。 size++ size--的时候。Generic 数组的新建。