Fast and complete implementation of java.util.Map using open addressing.

Table.java

package java.util;

import java.io.Serial;
import java.io.Serializable;
import java.util.*;

public class Table<K, V> implements Map<K, V>, Serializable {
    @Serial
    private static final long serialVersionUID = -534207388696845484L;

    private K[] ks;
    private V[] vs;
    private int[] hs;

    private int cp;
    private int ln;

    private transient EntrySet entrySet;
    private transient KeySet keySet;
    private transient ValueCollection values;

    public Table() {
    }

    public Table(Table<? extends K, ? extends V> table) {
        if (table == null) {
            throw new NullPointerException("table cannot be null");
        }

        copyFrom(table);
    }

    public Table(Map<? extends K, ? extends V> map) {
        putAll(map);
    }

    private static int hash(Object kt) {
        int ht = kt.hashCode();

        ht = ((ht >>> 16) ^ ht) * 0x45D9F3B;
        ht = ((ht >>> 16) ^ ht) * 0x45D9F3B;
        ht = ((ht >>> 16) ^ ht);

        return ht;
    }

    private int find(Object kt, int ht) {
        final K[] ks = this.ks;
        final int[] hs = this.hs;

        final int m = cp - 1;
        int e = ht & m;
        int t = -1;

        for (;;) {
            final K ke = ks[e];
            final int he = hs[e];

            if (ke == null) {
                if (he == 0) {
                    return t < 0 ? e : t;
                } else if (t < 0) {
                    t = e;
                }
            } else if (he == ht && (ke == kt || ke.equals(kt))) {
                return e;
            }

            e = (e + 1) & m;
        }
    }

    @SuppressWarnings("unchecked")
    private void init() {
        ks = (K[]) new Object[16];
        vs = (V[]) new Object[16];
        hs = new int[16];
        cp = 16;
    }

    @SuppressWarnings("unchecked")
    private void resize() {
        final int ocp = cp;
        final int ncp = cp = ocp * 2;

        final K[] oks = ks;
        final K[] nks = ks = (K[]) new Object[ncp];

        final V[] ovs = vs;
        final V[] nvs = vs = (V[]) new Object[ncp];

        final int[] ohs = hs;
        final int[] nhs = hs = new int[ncp];

        for (int i = 0; i < ocp; i++) {
            final K ki = oks[i];

            if (ki == null) {
                continue;
            }

            final V vi = ovs[i];
            final int hi = ohs[i];

            final int e = find(ki, hi);

            nks[e] = ki;
            nvs[e] = vi;
            nhs[e] = hi;
        }
    }

    @Override
    public V put(K kt, V vt) {
        if (kt == null) {
            throw new NullPointerException("key cannot be null");
        }

        final int cp = this.cp;

        if (cp == 0) {
            init();
        } else if (ln + 1 > (cp >>> 1) + (cp >>> 2)) {
            resize();
        }

        final int ht = hash(kt);
        final int e = find(kt, ht);

        final K[] ks = this.ks;
        final V[] vs = this.vs;
        final int[] hs = this.hs;

        if (ks[e] == null) {
            ln++;
        }

        final V vp = vs[e];

        ks[e] = kt;
        vs[e] = vt;
        hs[e] = ht;

        return vp;
    }

    @Override
    public V remove(Object kt) {
        if (kt == null || ln == 0) {
            return null;
        }

        final int e = find(kt, hash(kt));

        final K[] ks = this.ks;

        if (ks[e] == null) {
            return null;
        }

        final V[] vs = this.vs;
        final int[] hs = this.hs;

        final V vp = vs[e];

        ks[e] = null;
        vs[e] = null;
        hs[e] = -1;

        ln--;

        return vp;
    }

    @Override
    public V get(Object kt) {
        if (kt == null || ln == 0) {
            return null;
        }

        return vs[find(kt, hash(kt))];
    }

    @Override
    public void clear() {
        ks = null;
        vs = null;
        hs = null;
        cp = 0;
        ln = 0;
    }

    @Override
    public int size() {
        return ln;
    }

    @Override
    public boolean isEmpty() {
        return ln == 0;
    }

    @Override
    public boolean containsKey(Object kt) {
        if (kt == null) {
            return false;
        }

        return ks[find(kt, hash(kt))] != null;
    }

    @Override
    public boolean containsValue(Object vt) {
        final int cp = this.cp;
        final K[] ks = this.ks;
        final V[] vs = this.vs;

        for (int i = 0; i < cp; i++) {
            if (ks[i] != null && Objects.equals(vs[i], vt)) {
                return true;
            }
        }

        return false;
    }

    @SuppressWarnings("unchecked")
    private void copyFrom(Table<? extends K, ? extends V> table) {
        final int ln = table.ln;

        if (ln == 0) {
            return;
        }

        final int cp = table.cp;

        final K[] ks = (K[]) new Object[cp];
        final V[] vs = (V[]) new Object[cp];
        final int[] hs = new int[cp];

        System.arraycopy(table.ks, 0, ks, 0, cp);
        System.arraycopy(table.vs, 0, vs, 0, cp);
        System.arraycopy(table.hs, 0, hs, 0, cp);

        this.ks = ks;
        this.vs = vs;
        this.hs = hs;
        this.cp = cp;
        this.ln = ln;
    }

    private void importFrom(Table<? extends K, ? extends V> table) {
        if (table.ln == 0) {
            return;
        }

        if (ln == 0) {
            copyFrom(table);
            return;
        }

        final int cp = table.cp;
        final K[] ks = table.ks;
        final V[] vs = table.vs;

        for (int i = 0; i < cp; i++) {
            final K ki = ks[i];

            if (ki != null) {
                put(ki, vs[i]);
            }
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void putAll(Map<? extends K, ? extends V> map) {
        if (map == null) {
            throw new NullPointerException("map cannot be null");
        }
        if (map instanceof Table) {
            importFrom((Table<? extends K, ? extends V>) map);
        } else {
            for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
                put(entry.getKey(), entry.getValue());
            }
        }
    }

    private static final class Entry<K, V> implements Map.Entry<K, V> {
        private final Table<K, V> table;
        private final K key;

        private Entry(Table<K, V> table, K key) {
            this.table = table;
            this.key = key;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return table.get(key);
        }

        @Override
        public V setValue(V value) {
            return table.put(key, value);
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == this) {
                return true;
            }
            if (!(obj instanceof Map.Entry<?, ?>)) {
                return false;
            }
            final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
            return (
                Objects.equals(getKey(), entry.getKey()) &&
                Objects.equals(getValue(), entry.getValue())
            );
        }

        @Override
        public int hashCode() {
            final K key = this.key;
            final V val = this.getValue();
            return (
                (key != null ? key.hashCode() : 0) ^
                (val != null ? val.hashCode() : 0)
            );
        }

        @Override
        public String toString() {
            return key + "=" + getValue();
        }
    }

    private static final class EntryIterator<K, V> implements Iterator<Map.Entry<K, V>> {
        private final Table<K, V> table;
        private final K[] ks;
        private final int cp;
        private final int ln;

        private int i;
        private int c;

        private EntryIterator(Table<K, V> table) {
            this.table = table;
            ks = table.ks;
            cp = table.cp;
            ln = table.ln;
        }

        @Override
        public boolean hasNext() {
            return c < ln;
        }

        @Override
        public Map.Entry<K, V> next() {
            if (hasNext()) {
                final int cp = this.cp;
                final K[] ks = this.ks;

                for (; i < cp; i++) {
                    final K ki = ks[i];
                    if (ki != null) {
                        c++;
                        i++;
                        return new Entry<>(table, ki);
                    }
                }
            }

            throw new NoSuchElementException();
        }
    }

    private static final class KeyIterator<K> implements Iterator<K> {
        private final K[] ks;
        private final int cp;
        private final int ln;

        private int i;
        private int c;

        private KeyIterator(Table<K, ?> table) {
            ks = table.ks;
            cp = table.cp;
            ln = table.ln;
        }

        @Override
        public boolean hasNext() {
            return c < ln;
        }

        @Override
        public K next() {
            if (hasNext()) {
                final int cp = this.cp;
                final K[] ks = this.ks;

                for (; i < cp; i++) {
                    final K ki = ks[i];
                    if (ki != null) {
                        c++;
                        i++;
                        return ki;
                    }
                }
            }

            throw new NoSuchElementException();
        }
    }

    private static final class ValueIterator<K, V> implements Iterator<V> {
        private final K[] ks;
        private final V[] vs;
        private final int cp;
        private final int ln;

        private int i;
        private int c;

        private ValueIterator(Table<K, V> table) {
            ks = table.ks;
            vs = table.vs;
            cp = table.cp;
            ln = table.ln;
        }

        @Override
        public boolean hasNext() {
            return c < ln;
        }

        @Override
        public V next() {
            if (hasNext()) {
                final int cp = this.cp;
                final K[] ks = this.ks;
                final V[] vs = this.vs;

                for (; i < cp; i++) {
                    if (ks[i] != null) {
                        c++;
                        return vs[i++];
                    }
                }
            }

            throw new NoSuchElementException();
        }
    }

    private final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
        @Override
        public Iterator<Map.Entry<K, V>> iterator() {
            return new EntryIterator<>(Table.this);
        }

        @Override
        public int size() {
            return Table.this.ln;
        }
    }

    private final class KeySet extends AbstractSet<K> {
        @Override
        public Iterator<K> iterator() {
            return new KeyIterator<>(Table.this);
        }

        @Override
        public int size() {
            return Table.this.ln;
        }
    }

    private final class ValueCollection extends AbstractCollection<V> {
        @Override
        public Iterator<V> iterator() {
            return new ValueIterator<>(Table.this);
        }

        @Override
        public int size() {
            return Table.this.ln;
        }
    }

    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        if (entrySet == null) {
            entrySet = new EntrySet();
        }
        return entrySet;
    }

    @Override
    public Set<K> keySet() {
        if (keySet == null) {
            keySet = new KeySet();
        }
        return keySet;
    }

    @Override
    public Collection<V> values() {
        if (values == null) {
            values = new ValueCollection();
        }
        return values;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        }

        if (!(obj instanceof Map<?, ?>)) {
            return false;
        }

        final Map<?, ?> map = (Map<?, ?>) obj;

        if (map.size() != ln) {
            return false;
        }

        final int cp = this.cp;
        final K[] ks = this.ks;
        final V[] vs = this.vs;

        try {
            for (int i = 0; i < cp; i++) {
                final K ki = ks[i];
                if (ki != null && !Objects.equals(vs[i], map.get(ki))) {
                    return false;
                }
            }
        } catch (ClassCastException err) {
            return false;
        } catch (NullPointerException err) {
            return false;
        }

        return true;
    }

    @Override
    public int hashCode() {
        final int cp = this.cp;
        final K[] ks = this.ks;
        final V[] vs = this.vs;

        int h = 0;

        for (int i = 0; i < cp; i++) {
            final K ki = ks[i];

            if (ki == null) {
                continue;
            }

            final V vi = vs[i];

            h += ki.hashCode() ^ (vi != null ? vi.hashCode() : 0);
        }

        return h;
    }

    @Override
    public String toString() {
        if (ln == 0) {
            return "{}";
        }

        final int cp = this.cp;
        final K[] ks = this.ks;
        final V[] vs = this.vs;

        final StringBuilder builder = new StringBuilder();

        builder.append('{');

        boolean nextItem = false;

        for (int i = 0; i < cp; i++) {
            final K ki = ks[i];

            if (ki == null) {
                continue;
            }

            if (nextItem) {
                builder.append(',');
                builder.append(' ');
            }
            nextItem = true;

            final V vi = vs[i];

            builder.append(ki == this ? "<this>" : ki);
            builder.append('=');
            builder.append(vi == this ? "<this>" : vi);
        }

        builder.append('}');

        return builder.toString();
    }

    @Override
    public Object clone() throws CloneNotSupportedException {
        throw new CloneNotSupportedException();
    }
}