Surely fastest and best implementation of Map (no)

OrderedMap.java

import lombok.AccessLevel;
import lombok.RequiredArgsConstructor;
import org.jetbrains.annotations.Contract;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;

import java.util.*;

@SuppressWarnings("SuspiciousMethodCalls")
@RequiredArgsConstructor(access = AccessLevel.PRIVATE)
public class OrderedMap<K, V> implements Map<K, V> {
    private final List<K> keys;
    private final List<V> values;

    public OrderedMap(int initialCapacity){
        this(new ArrayList<>(initialCapacity), new ArrayList<>(initialCapacity));
    }

    @Contract(" -> new")
    public static <K, V> @NotNull OrderedMap<K, V> linkedMap(){
        return new OrderedMap<>(new LinkedList<>(), new LinkedList<>());
    }

    /**
     * Creates new OrderedMap with initial capacity of ten
     */
    public OrderedMap(){
        this(10);
    }

    @Override
    public int size() {
        return keys.size();
    }

    @Override
    public boolean isEmpty() {
        return keys.isEmpty();
    }

    @Override
    public boolean containsKey(Object key) {
        try {
            return keys.contains(key);
        } catch (ClassCastException e) {
            return false;
        }
    }

    @Override
    public boolean containsValue(Object value) {
        try {
            return values.contains(value);
        } catch (ClassCastException e) {
            return false;
        }
    }

    private void ensureCorrect(){
        if (values.size() != keys.size()) {
            throw new IllegalStateException("keys.size() != values.size(). Broken map");
        }
    }

    private int indexOfKey(Object key){
        try {
            return keys.lastIndexOf(key);
        } catch (ClassCastException e){
            return -1;
        }
    }

    @Override
    public V get(Object key) {
        int i = indexOfKey(key);
        if (i == -1) return null;
        if (i >= values().size()) throw new IllegalStateException("keys.size() != values.size(). Broken map");
        return values.get(i);
    }

    @Nullable
    @Override
    public V put(K key, V value) {
        ensureCorrect();
        int i = indexOfKey(key);
        if (i != -1) {
            var old = values.remove(i);
            values.add(i, value);
            return old;
        } else {
            keys.add(key);
            values.add(value);
            return null;
        }
    }

    @Override
    public V remove(Object key) {
        ensureCorrect();
        var i = indexOfKey(key);
        if (i == -1) {
            return null;
        }
        keys.remove(i);
        return values.remove(i);
    }

    @Override
    public void putAll(@NotNull Map<? extends K, ? extends V> m) {
        ensureCorrect();
        for (var e : m.entrySet()){
            put(e.getKey(), e.getValue());
        }
    }

    @Override
    public void clear() {
        keys.clear();
        values.clear();
    }

    @NotNull
    @Override
    public Set<K> keySet() {
        return Set.copyOf(keys);
    }

    /**
     * returns a values of map, not backed up by map
     * @return copy of values
     */
    @NotNull
    @Override
    public Collection<V> values() {
        return Collections.unmodifiableList(values);
    }

    @NotNull
    @Override
    public Set<Entry<K, V>> entrySet() {
        ensureCorrect();
        var ret = new HashSet<Entry<K, V>>(keys.size());
        for (var k : keys){
            var v = get(k);
            ret.add(new OrderedMapEntry(this, k, v));
        }
        return ret;
    }

    @AllArgsConstructor
    public class OrderedMapEntry implements Entry<K, V> {
        private final OrderedMap<K, V> map;
        private final K key;
        private final V value;

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

        @Override
        public V getValue() {
            return value;
        }

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