A TreeMap that's values are backed by a fixed index array list and therefore allows faster iterative access

ArrayBackedTreeMap.class

import java.util.*;
import java.util.stream.Collectors;

class ArrayBackedTreeMap<K,V> extends AbstractMap<K, V> {

    private final Map<K, Integer> tree = new TreeMap<>();
    private final FixedIndexArrayList<V> values = new FixedIndexArrayList<>(10, 10);

    public V put(K k, V v) {
        Integer i = tree.get(k);
        if(i != null) {
            values.set(i, v);
            return v;
        }
        i = values.add(v);
        tree.put(k, i);
        return v;
    }

    public V remove(Object k) {
        Integer i = tree.get(k);
        if(i == null)
            return null;
        V v = values.get(i);
        values.remove(i);
        tree.remove(k);
        return v;
    }

    public V get(Object k) {
        Integer i = tree.get(k);
        if(i == null)
            return null;
        return values.get(i);
    }

    public boolean containsKey(Object key) {
        return tree.containsKey(key);
    }
    
    public boolean containsValue(Object value) {
        return values().contains(value);
    }

    public Set<Map.Entry<K, V>> entrySet() {
        return tree.entrySet().stream().map(e -> new AbstractMap.SimpleEntry<>(e.getKey(), values.get(e.getValue()))).collect(Collectors.toSet());
    }

    public Set<K> keySet() {
        return tree.keySet();
    }

    public Collection<V> values() {
        return new AbstractCollection<V>() {
            public Iterator<V> iterator() {
                return new Iterator<V>() {
                    private int i = 0;
                    public boolean hasNext() {
                        return i < values.lastElement;
                    }
                    public V next() {
                        do {
                            i++;
                        } while (i < values.lastElement && values.values[i] == null);
                        if(i > values.lastElement)
                            throw new NoSuchElementException("Iterator has no next element");
                        return values.get(i);
                    }
                };
            }
            public int size() {
                return values.size;
            }
        };
    }

    private static class FixedIndexArrayList<T> {

        private final int growthRate;
        private Object[] values;
        private int lastElement = -1;
        private int size = 0;

        public FixedIndexArrayList(int initialCapacity, int growthRate) {
            this.values = new Object[initialCapacity];
            this.growthRate = growthRate;
        }

        public T get(int index) {
            return (T) values[index];
        }

        public void set(int index, T value) {
            if(values[index] == null)
                throw new IllegalArgumentException("Index " + index + " is not a valid index");
            if(value == null)
                size--;
            values[index] = value;
            if(index == lastElement) {
                lastElement--;
                while (values[lastElement] == null)
                    lastElement--;
                if(values.length - lastElement - 1 == growthRate) {
                    Object[] newArray = new Object[values.length - growthRate];
                    System.arraycopy(values, 0, newArray, 0, newArray.length);
                    values = newArray;
                }
            }
        }

        public void remove(int index) {
            set(index, null);
        }

        public int add(T value) {
            size++;
            for(int i=0; i<=lastElement; i++) {
                if(values[i] == null) {
                    values[i] = value;
                    return i;
                }
            }
            if(lastElement == values.length - 1) {
                int i = values.length;
                Object[] newArray = new Object[values.length + growthRate];
                System.arraycopy(values, 0, newArray, 0, values.length);
                values = newArray;
                values[i] = value;
                return i;
            }
            lastElement++;
            values[lastElement] = value;
            return lastElement;
        }

    }

}