1 .定义接口

package com.gzz;

public interface Map<K, V> {
    V put(K k, V v);

    V get(K k);

    int size();

    interface Entry<K, V> {
        K getKey();

        V getValue();
    }
}

2. 实现类

package com.gzz;
public class HashMap<K, V> implements Map<K, V> {
    private int CAPACITY = 16;
    private int size = 0;
    private Node<K, V>[] table;
    @SuppressWarnings("unchecked")
    public HashMap(int CAPACITY) {
        this.CAPACITY = CAPACITY;
        this.table = new Node[CAPACITY];
    }
    @SuppressWarnings("unchecked")
    public HashMap() {
        this.table = new Node[CAPACITY];
    }
    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = myHash(key);
        int i = indexForTable(hash, CAPACITY);
        for (Node<K, V> e = table[i]; e != null; e = e.next) {
            if (e.hash == hash && (e.key == key || e.key.equals(key))) {
                V old = e.value;
                e.value = value;
                return old;
            }
        }
        addEntry(hash, key, value, i);
        return null;
    }
    public V get(K key) {
        if (key == null)
            return getForNullKey();
        int hash = myHash(key);
        int i = indexForTable(hash, CAPACITY);
        for (Node<K, V> e = table[i]; e != null; e = e.next) {
            if (e.hash == hash && (e.key == key || e.key.equals(key)))
                return e.value;
        }
        return null;
    }
    private V getForNullKey() {
        for (Node<K, V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }
    private void addEntry(int hash, K key, V value, int i) {
        Node<K, V> e = table[i];
        table[i] = new Node<K, V>(hash, key, value, e);
        if (size == CAPACITY)
            resize();
        size++;
    }
    private void resize() {
        CAPACITY = CAPACITY * 2;
        @SuppressWarnings("unchecked")
        Node<K, V>[] newtable = new Node[CAPACITY];
        for (Node<K, V> entry : table) {
            Node<K, V> e = entry; // 取得旧Entry数组的每个元素
            if (e != null) {
                entry = null;// 释放旧Entry数组的对象引用（循环后，旧的Entry数组不再引用任何对象）
                do {
                    Node<K, V> next = e.next;
                    int i = indexForTable(e.hash, CAPACITY); // 重新计算每个元素在数组中的位置
                    e.next = newtable[i];
                    newtable[i] = e; // 将元素放在数组上
                    e = next; // 访问下一个Entry链上的元素
                } while (e != null);
            }
        }
        table = newtable;
    }
    private int indexForTable(int hash, int CAPACITY) {
        return hash & (CAPACITY - 1);
    }
    private int myHash(K key) {
        if (key == null)
            return 0;
        int h = key.hashCode();
        h = h ^ (h >>> 16);
        return h;
    }
    private V putForNullKey(V value) {
        for (Node<K, V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V old = e.value;
                e.value = value;
                return old;
            }
        }
        addEntry(0, null, value, 0);
        return null;
    }
    @Override
    public int size() {
        return size;
    }
}
class Node<K, V> implements Map.Entry<K, V> {
    public int hash;
    public K key;
    public V value;
    public Node<K, V> next;
    public Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    @Override
    public K getKey() {
        return key;
    }
    @Override
    public V getValue() {
        return value;
    }
}

3 测试

package com.gzz;
public class Test {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();
        for (int i = 0; i < 10000; i++) {
            map.put("gzz" + i, "我是gzz" + i);
        }
        System.out.println(map);
    }
}