Node节点

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

字段+构造

private static final int DEFAULT_SIZE = 16;
private static final float LOAD_FACTOR = 0.75f;
private Node<K, V>[] elementData;
private int size;
// 构造函数
public MyHashMap() {
    elementData = new Node[DEFAULT_SIZE];
    size = 0;
}
public MyHashMap(int cap) {
    if (cap < 1) {
        throw new RuntimeException("容量需大于0");
    }
    cap = findCap(cap);
    elementData = new Node[cap];
    size = 0;
}

Hash + 取模

private int getHashCode(K key) {
    return key.hashCode();
}
private int getIndex(K key, int len) {
    return getHashCode(key) & (len - 1);
}

put方法

public void put(K key, V value) {
    int len = elementData.length;
    int index = getIndex(key, len);
    Node<K, V> current = elementData[index];
    if (current == null) {
        elementData[index] = new Node<>(key, value);
    } else {
        Node<K, V> pre = current;
        while (current != null) {
            if (current.key.equals(key)) {
                current.value = value;
                return;
            }
            pre = current;
            current = current.next;
        }
        pre.next = new Node<>(key, value);
    }
    size++;
    if (size >= len * LOAD_FACTOR) {
        resize();
    }
}

get方法

public V get(K key) {
    int len = elementData.length;
    int index = getIndex(key, len);
    Node<K, V> target = elementData[index];
    while (target != null) {
        if (target.key.equals(key)) {
            return target.value;
        }
        target = target.next;
    }
    return null;
}

扩容方法

private void resize() {
    int oldCap = elementData.length;
    Node<K, V>[] newElementData = new Node[oldCap * 2];
    for (int i = 0; i < oldCap; i++) {
        Node<K, V> current = elementData[i];
        while (current != null) {
            int newIndex = (getHashCode(current.key) & oldCap) == 0 ? i : i + oldCap;
            // 保存下一个节点防止
            Node<K, V> next = current.next;
            // 头插法
            current.next = newElementData[newIndex];
            newElementData[newIndex] = current;
            current = next;
        }
    }
    // 指向新的数组
    elementData = newElementData;
}

容量设置

private int findCap(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return n < 0 ? 16 : n + 1;
}